Minimum cycle factors in quasi-transitive digraphs

We consider the minimum cycle factor problem  : given a digraph DD, find the minimum number kmin(D)kmin(D) of vertex disjoint cycles covering all vertices of DD or verify that DD has no cycle factor. There is an analogous problem for paths, known as the minimum path factor problem. Both problems are NPNP-hard for general digraphs as they include the Hamilton cycle and path problems, respectively.In 1994 Gutin [G. Gutin, Polynomial algorithms for finding paths and cycles in quasi-transitive digraphs, Australas. J. Combin. 10 (1994) 231–236] proved that the minimum path factor problem is solvable in polynomial time, for the class of quasi-transitive digraphs, and so is the Hamilton cycle problem.As the minimum cycle factor problem is analogous to the minimum path factor problem and is a generalization of the Hamilton cycle problem, it is therefore a natural question whether this problem is also polynomially solvable, for quasi-transitive digraphs.We conjecture that the problem of deciding, for a fixed kk, whether a quasi-transitive digraph DD has a cycle factor with at most kk cycles is polynomial, and we verify this conjecture for k=3k=3.We introduce the notion of an irreducible cycle factor and show how to convert a given cycle factor into an irreducible one in polynomial time when the input digraph is quasi-transitive. Finally, we show that even though this process will often reduce the number of cycles considerably, it does not always yield a minimum cycle factor.