# Finding a Hamiltonian cycle from perfect matching of a bipartite graph

A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H, constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original graph edges replaced by corresponding L-> R edges.

Is it possible to find a Hamiltonian cycle in G (assuming it exists) as one realization of the vertex-disjoint cycle cover from the bipartite graph, H, using a matching algorithm?

## 1 Answer

If $$G$$ has a disjoint vertex cycle cover then I agree that $$H$$ must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define $$H$$ exactly). I think the construction you were thinking of is the one described in this answer: https://cstheory.stackexchange.com/a/8570/38111.

As for your question (assuming that $$H$$ is now the bipartite graph constructed in the answer I linked), I think it depends on what you are asking exactly:

• if you are asking "if there is a Hamiltonian cycle in $$G$$, then is there a perfect matching in $$H$$ that 'corresponds' to this cycle" then yes, since, as David Eppstein points out in his answer, the perfect matchings of $$H$$ correspond 1-for-1 with cycle covers of $$G$$, and a Hamiltonian cycle is in particular a vertex disjoint cycle cover.
• if you are asking "can we use the same kind of trick to efficiently find such a Hamiltonian cycle", then probably no, since finding a Hamiltonian cycle is NP-hard.
• I am defining H in the same way as mentioned in the answer of David Eppstein. If finding a perfect matching on H can give the (disjoint)vertex cycle covers of G in polynomial time, including any Hamiltonian cycles, would this not also imply that a Hamiltonian cycle can be identified in polynomial time. – Ganapati Natarajan May 17 '19 at 7:27
• Yes. But with a PTIME algorithm $A$ for perfect matching on $H$, you are only guarantied to find a perfect matching of $H$, not all of them, so there is no contradiction here. In other words, you cannot expect that the perfect matchings that $A$ outputs will contain one that corresponds to a Hamiltonian cycle of $G$, unless P=NP. Now, maybe this technique works if you restrict the class of graphs $G$ that you consider in the first place. – M.Monet May 17 '19 at 15:11