<p>If <span class="math-container">$G$</span> has a disjoint <a href="https://en.wikipedia.org/wiki/Vertex_cycle_cover" rel="nofollow noreferrer">vertex cycle cover</a> then I agree that <span class="math-container">$H$</span> must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define <span class="math-container">$H$</span> exactly). I think the construction you were thinking of is the one described in this answer: <a href="https://cstheory.stackexchange.com/a/8570/38111">https://cstheory.stackexchange.com/a/8570/38111</a>.</p>

<p>As for your question (assuming that <span class="math-container">$H$</span> is now the bipartite graph constructed in the answer I linked), I think it depends on what you are asking exactly:</p>

<ul>
<li>if you are asking "if there is a Hamiltonian cycle in <span class="math-container">$G$</span>, then is there a perfect matching in <span class="math-container">$H$</span> that 'corresponds' to this cycle" then yes, since, as David Eppstein points out in his answer, the perfect matchings of <span class="math-container">$H$</span> correspond 1-for-1 with cycle covers of <span class="math-container">$G$</span>, and a Hamiltonian cycle is in particular a vertex disjoint cycle cover.</li>
<li>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.</li>
</ul>

CC BY-SA 4.0
2019-05-17T07:27:20.033Z
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
CC BY-SA 4.0
2019-05-17T15:11:31.360Z
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
CC BY-SA 4.0
2019-05-17T04:26:01.773Z
2019-05-17T04:26:01.773Z
M.Monet
<p>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.</p>

<p>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?</p>

<graph-theory><graph-algorithms><hamiltonian-paths><bipartite-graphs>
Finding a Hamiltonian cycle from perfect matching of a bipartite graph
Ganapati Natarajan
# Finding a Hamiltonian cycle from perfect matching of a bipartite graph

(Asked by: username_0 on 2019-05-17)

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?

**Tags:** graph-theory, graph-algorithms, hamiltonian-paths, bipartite-graphs

---

## 1 answers

### Answer by username_1 on 2019-05-17. Score: 2 | Accepted answer

If $G$ has a disjoint [vertex cycle cover](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  

---

