# Algorithm for finding a 3-cycle cover

Given: An undirected, unweighted graph

Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges

Is there any algorithm that solves this problem, possibly with some heuristics? Can the bipartite representation of the graph used for finding perfect matching be leveraged here?

• I think that you are mixing up results for the undirected and for the directed version of the problem. May 11, 2020 at 21:25
• Now that you have edited your question, could you explain to us why you think that your problem is NP-hard? May 13, 2020 at 9:58
• Because I have not seen an actual algorithm that can solve this problem in polynomial time. May 16, 2020 at 11:23
• What I am doing right now is using the Hopcroft–Karp algorithm to obtain a maximum matching on the bipartite representation of the original graph. This maximum matching on the bipartite graph is a cycle cover when mapped to the original graph, but it may contain paths. What I didn't fully understand is if this method gives any guarantee reagrding cycle lengths. May 16, 2020 at 11:29

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).

• Nice summary of problem's complexity. May 11, 2020 at 22:12
• BTW, Do you know analogous results for cubic graphs (undirected and directed)? May 13, 2020 at 14:55
• Very interesting. 5-UCC should be added to the list of problems between P and NPC. May 14, 2020 at 18:58