Complexity of the Hamiltonian Subcycle problem 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.
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.