1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.
Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Ganapati Natarajan
    May 17, 2019 at 7:27
  • $\begingroup$ 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. $\endgroup$
    – M.Monet
    May 17, 2019 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.