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.
