3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 23 '10 at 18:22
  • $\begingroup$ 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? $\endgroup$ – Alex ten Brink Sep 23 '10 at 19:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Jukka Suomela Sep 23 '10 at 19:46
6
$\begingroup$

Some standard terminology:

  • A set of cycles that spans all nodes is called a cycle cover (or "vertex-disjoint cycle cover").
  • Cycle covers and perfect matchings are special cases of graph factors: 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) 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.

$\endgroup$
  • 1
    $\begingroup$ Jukka: Nice answer! $\endgroup$ – Tsuyoshi Ito Sep 24 '10 at 10:48
0
$\begingroup$

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

$\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.