0
$\begingroup$

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

Is it possible then to find the Hamiltonian cycle as a single cycle which as the vertex-disjoint cycle cover using a bipartite graph matching algorithm?

$\endgroup$
  • $\begingroup$ Do you have a reference for the claim in the first paragraph? It seems too good to be true. $\endgroup$ – Peter Taylor Aug 12 at 17:27
  • $\begingroup$ Ah, is this assuming a directed graph? $\endgroup$ – Peter Taylor Aug 12 at 18:47
0
$\begingroup$

Probably not: the problem of finding a Hamiltonian cycle is NP-hard, while there are polynomial time algorithms for bipartite matching. So answering YES to your question implies P = NP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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