Finding complementary cycles in locally semicomplete digraphs

It is well known that the problem of deciding whether a given digraph has a k-cycle factor for some constant k (i.e. a collection of k disjoint cycles that cover all vertices of the digraph) is NP-complete as this is a generalization of the Hamilton cycle problem. In this paper, we show that for the class of locally semicomplete digraphs the existence of a 2-cycle factor can be decided, and a 2-cycle factor found if it exists, in time O(n3), where n is the order of the digraph.