1

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?

Ganapati Natarajan
  • 13
  • 2

1 Answers1

2

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.
M.Monet
  • 1,429
  • 7
  • 19
  • 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 07: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