<p>Some standard terminology:</p>

<ul>
<li>A set of cycles that spans all nodes is called a <strong>cycle cover</strong> (or "<a href="http://en.wikipedia.org/wiki/Vertex_cycle_cover" rel="nofollow">vertex-disjoint cycle cover</a>").</li>
<li>Cycle covers and perfect matchings are special cases of <strong><a href="http://en.wikipedia.org/wiki/Graph_factorization" rel="nofollow">graph factors</a></strong>: cycle covers are 2-factors (spanning 2-regular subgraphs) and perfect matchings are 1-factors (spanning 1-regular subgraphs).</li>
</ul>

<p>Polynomial-time algorithms:</p>

<ul>
<li>As Tsuyoshi pointed out, finding a cycle cover in a given graph can be reduced to the problem of finding a perfect matching in a bipartite graph.</li>
<li>More generally, <a href="http://www.ams.org/mathscinet-getitem?mr=63008" rel="nofollow">Tutte (1954)</a> shows the following: for any graph $G$ and any integer $f$ it is possible to construct a graph $G'$ such that $G'$ has a 1-factor (perfect matching) if and only if $G$ has an $f$-factor.</li>
</ul>

<p>As is well known, there are polynomial-time algorithms for perfect matchings.</p>

CC BY-SA 2.5
2010-09-24T10:48:36.797Z
Jukka: Nice answer!
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-23T20:06:18.087Z
2010-09-23T20:11:48.543Z
2010-09-23T20:11:48.543Z
Jukka Suomela
<p>You might find the methods that Joe Mitchell (CS-Stony Brook) has developed for treating a wide variety of geometrical problems that generalize the TSP to be of interest. Some of these papers can be obtained at the link below:</p>

<p><a href="http://www.ams.stonybrook.edu/~jsbm/publications.html" rel="nofollow">http://www.ams.stonybrook.edu/~jsbm/publications.html</a></p>

CC BY-SA 2.5
2010-09-23T21:25:45.640Z
2010-09-23T21:25:45.640Z
Joseph Malkevitch
<p>The problem is as follows:</p>

<blockquote>
  <p>Given a graph $G$, find a (vertex)
  disjoint set of cycles $C$ on $G$ such
  that every vertex is visited by a
  cycle exactly once.</p>
</blockquote>

<p>My question is then: what is the complexity of this problem? Is it NP-hard, in P or something else?</p>

<p>If we modify the problem to require $|C| = 1$, we end up with the standard Hamiltonian Cycle problem. It's easy to see that for any $k$, if we require $|C| = k$ or $|C| \leq k$, then the problem is NP-hard: given an instance for the Hamiltonian Cycle problem, we simply copy this graph $k$ times.</p>

<p>An equivalent definition of the problem is as follows:</p>

<blockquote>
  <p>Given a graph $G$, have every vertex
  $v$ 'choose' some other vertex $u$
  such that $(u,v) \in E$, and that
  every vertex is chosen exactly once.</p>
</blockquote>

<p>If you prove the above problem NP-hard, then for any $k$, if we modify the problem so that every vertex chooses $k$ vertices and every vertex is chosen exactly $k$ times, then the resulting problem is NP-hard as well: you can reduce the problem for any $k$ to the Hamiltonian Subcycle problem by 'eating up' the number of choices each vertex has by attaching certain gadgets to them.</p>

<p>I came across this problem when I believed a certain problem was in fact equivalent to the above problem. That later turned out to be wrong, but the problem interested me nonetheless.</p>

<p>I've developed an algorithm that sometimes finds the correct answer, but often doesn't end at all. It's based on using Lagrangian relaxation on the TSP variant of the above problem, which is simply TSP where more than one cycle is allowed (as long as the cycles are disjoint). I doubt it's possible to fix the algorithm so it works all the time, so I haven't included it in this question, though I could always do that if needed.</p>

CC BY-SA 2.5
2010-09-23T18:22:00.927Z
From the second formulation, it seems that the problem is easily solvable in P by reducing it to finding a perfect matching in a bipartite graph.  What am I missing?  If each cycle has to be length at least 3, the situation is probably different.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-23T19:01:46.447Z
I somehow managed to completely overlook that, that indeed solves my problem... Should I delete my question or leave it here to save people from the same fate?
Alex ten Brink
CC BY-SA 2.5
2010-09-23T19:46:29.887Z
I don't think there is any need to delete it. Let's write an answer that summarises what is known about this problem, so this question serves a useful purpose.
Jukka Suomela
<cc.complexity-theory><np-hardness><hamiltonian-paths>
Complexity of the Hamiltonian Subcycle problem
Alex ten Brink
# Complexity of the Hamiltonian Subcycle problem

(Asked by: username_0 on 2010-09-23)

The problem is as follows:

> Given a graph $G$, find a (vertex)
> disjoint set of cycles $C$ on $G$ such
> that every vertex is visited by a
> cycle exactly once.

My question is then: what is the complexity of this problem? Is it NP-hard, in P or something else?

If we modify the problem to require $|C| = 1$, we end up with the standard Hamiltonian Cycle problem. It's easy to see that for any $k$, if we require $|C| = k$ or $|C| \leq k$, then the problem is NP-hard: given an instance for the Hamiltonian Cycle problem, we simply copy this graph $k$ times.

An equivalent definition of the problem is as follows:

> Given a graph $G$, have every vertex
> $v$ 'choose' some other vertex $u$
> such that $(u,v) \in E$, and that
> every vertex is chosen exactly once.

If you prove the above problem NP-hard, then for any $k$, if we modify the problem so that every vertex chooses $k$ vertices and every vertex is chosen exactly $k$ times, then the resulting problem is NP-hard as well: you can reduce the problem for any $k$ to the Hamiltonian Subcycle problem by 'eating up' the number of choices each vertex has by attaching certain gadgets to them.

I came across this problem when I believed a certain problem was in fact equivalent to the above problem. That later turned out to be wrong, but the problem interested me nonetheless.

I've developed an algorithm that sometimes finds the correct answer, but often doesn't end at all. It's based on using Lagrangian relaxation on the TSP variant of the above problem, which is simply TSP where more than one cycle is allowed (as long as the cycles are disjoint). I doubt it's possible to fix the algorithm so it works all the time, so I haven't included it in this question, though I could always do that if needed.

**Tags:** cc.complexity-theory, np-hardness, hamiltonian-paths

> **Comments:**
> **username_1**: From the second formulation, it seems that the problem is easily solvable in P by reducing it to finding a perfect matching in a bipartite graph.  What am I missing?  If each cycle has to be length at least 3, the situation is probably different.  
> **username_0**: I somehow managed to completely overlook that, that indeed solves my problem... Should I delete my question or leave it here to save people from the same fate?  
> **username_2**: I don't think there is any need to delete it. Let's write an answer that summarises what is known about this problem, so this question serves a useful purpose.  

---

## 2 answers

### Answer by username_2 on 2010-09-23. Score: 6 | Accepted answer

Some standard terminology:

* A set of cycles that spans all nodes is called a **cycle cover** (or "[vertex-disjoint cycle cover](http://en.wikipedia.org/wiki/Vertex_cycle_cover)").
* Cycle covers and perfect matchings are special cases of **[graph factors](http://en.wikipedia.org/wiki/Graph_factorization)**: cycle covers are 2-factors (spanning 2-regular subgraphs) and perfect matchings are 1-factors (spanning 1-regular subgraphs).

Polynomial-time algorithms:

* As Tsuyoshi pointed out, finding a cycle cover in a given graph can be reduced to the problem of finding a perfect matching in a bipartite graph.
* More generally, [Tutte (1954)](http://www.ams.org/mathscinet-getitem?mr=63008) shows the following: for any graph $G$ and any integer $f$ it is possible to construct a graph $G'$ such that $G'$ has a 1-factor (perfect matching) if and only if $G$ has an $f$-factor.

As is well known, there are polynomial-time algorithms for perfect matchings.

> **Comments:**
> **username_1**: Jukka: Nice answer!  

---

### Answer by username_3 on 2010-09-23. Score: 0

You might find the methods that Joe Mitchell (CS-Stony Brook) has developed for treating a wide variety of geometrical problems that generalize the TSP to be of interest. Some of these papers can be obtained at the link below:

<http://www.ams.stonybrook.edu/~jsbm/publications.html>


---

