The cycle cover problem (CC) is the problem of finding a spanning set of cycles in a given directed or undirected input graph.
If all the cycles in the cover must consist of at least $k$ edges/arcs, the resulting restriction of the problem is denoted $k$-UCC (in undirected graphs) and $k$-DCC (in directed graphs).
The complexity of the directed version is fully understood:
- Markus Bläser and Bodo Siebert ("Computing Cycle Covers without Short Cycles", in Proceedings of ESA 2001, LNCS 2161, pp 368--379) have proved that $k$-DCC is NP-complete for any fixed $k\ge3$.
The complexity landscape of the undirected version is more diverse, and there are some open questions:
$3$-UCC is polynomially solvable. This is a folklore result that follows from a reduction of Tutte ("A short proof of the factor theorem for finite graphs", Canadian Journal of Mathematics 6, pp 347–352, 1954) to the classical unrestricted matching problem.
David Hartvigsen (in his PhD thesis "An Extension of Matching Theory", Carnegie-Mellon University, 1984) has shown that $4$-UCC is polynomially solvable.
The complexity status of $5$-UCC is open. David Hartvigsen has some positive results on special cases of this problem ("The square-free 2-factor problem in bipartite graphs", in Proceedings of IPCO 1999, LNCS 1610, pp 234–241).
Papadimitriou has proved that $k$-UCC is NP-complete for any fixed $k\ge6$. His proof is sketched in the 1980 paper "A matching problem with side conditions" by Gerard Cornuejols and Bill Pulleyblank (Discrete Mathematics 29, pp 135--159).