Partition a graph into node-disjoint cycles
A partition into vertex-disjoint cycles is the same thing as a 2-regular subgraph, more commonly known as a 2-factor. It can be found (if it exists) in polynomial time by an algorithm based on matching. E.g. see this link.

ETA Nov 2013: It seems from comments below that the reduction from the source linked above is wrong. However, the statement that the problem can be reduced to perfect matching remains correct. The correct reduction is in W. T. Tutte (1954), "A short proof of the factor theorem for finite graphs", Canadian J. Math. 6: 347–352.

Replace each vertex $v$ with degree $d$ by a complete bipartite graph $G_v=K_{d,\,d-2}$, and represent each edge $uv$ of the original graph by an edge from one vertex of $G_u$ to one vertex of $G_v$ (on the side of the bipartition with $d$ vertices) in such a way that each vertex of $G_v$ on that side of the bipartition has exactly one such edge incident to it.

Then a perfect matching in the modified graph has to match the $d-2$ vertices on their side of the bipartition of $G_v$ with $d-2$ out of the $d$ vertices on the other side, leaving exactly two free vertices that need to be matched with their neighbors in other subgraphs $G_u$. In this way, the perfect matchings of the modified graph correspond 1-for-1 with cycle covers of the original graph.