Finding a Hamiltonian Cycle from a perfect matching on a the bipartite graph

260 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.