<p>The <em>cycle cover</em> 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 <span class="math-container">$k$</span> edges/arcs, the resulting restriction of the problem is denoted <span class="math-container">$k$</span>-UCC (in undirected graphs) and <span class="math-container">$k$</span>-DCC (in directed graphs).</p>

<p>The complexity of the directed version is fully understood:</p>

<ul>
<li>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 <span class="math-container">$k$</span>-DCC is <strong>NP-complete</strong> for any fixed <span class="math-container">$k\ge3$</span>.</li>
</ul>

<p>The complexity landscape of the undirected version is more diverse, and there are some open questions: </p>

<ul>
<li><p><span class="math-container">$3$</span>-UCC is <strong>polynomially solvable</strong>. 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.</p></li>
<li><p>David Hartvigsen (in his PhD thesis "An Extension of Matching Theory", Carnegie-Mellon University, 1984) has shown that <span class="math-container">$4$</span>-UCC is <strong>polynomially solvable</strong>. </p></li>
<li><p>The complexity status of <span class="math-container">$5$</span>-UCC is <strong>open</strong>. 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). </p></li>
<li><p>Papadimitriou has proved that <span class="math-container">$k$</span>-UCC is <strong>NP-complete</strong> for any fixed <span class="math-container">$k\ge6$</span>. 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).</p></li>
</ul>

CC BY-SA 4.0
2020-05-11T22:12:28.150Z
Nice summary of problem's complexity.
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-05-13T14:55:45.733Z
BTW, Do you know analogous results for cubic graphs (undirected and directed)?
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-05-14T18:58:38.997Z
Very interesting.  5-UCC should be added to the [list of problems between P and NPC](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc).
Hsien-Chih Chang 張顯之
CC BY-SA 4.0
2020-05-11T21:27:40.227Z
2020-05-11T21:33:42.403Z
2020-05-11T21:33:42.403Z
Gamow
<p><strong>Given:</strong> An undirected, unweighted graph</p>

<p><strong>Looking for:</strong> A disjoint vertex cycle cover where every cycle has at least 3 edges</p>

<p>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? </p>

CC BY-SA 4.0
2020-05-11T21:25:45.597Z
I think that you are mixing up results for the undirected and for the directed version of the problem.
Gamow
CC BY-SA 4.0
2020-05-13T09:58:03.543Z
Now that you have edited your question, could you explain to us why you think that your problem is NP-hard?
Gamow
CC BY-SA 4.0
2020-05-16T11:23:01.217Z
Because I have not seen an actual algorithm that can solve this problem in polynomial time.
Ben Bezos
CC BY-SA 4.0
2020-05-16T11:29:39.193Z
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.
Ben Bezos
<graph-theory><graph-algorithms><implementation>
Algorithm for finding a 3-cycle cover
Ben Bezos
# Algorithm for finding a 3-cycle cover

(Asked by: username_0 on 2020-05-11)

**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?

**Tags:** graph-theory, graph-algorithms, implementation

> **Comments:**
> **username_1**: I think that you are mixing up results for the undirected and for the directed version of the problem.  
> **username_1**: Now that you have edited your question, could you explain to us why you think that your problem is NP-hard?  
> **username_0**: Because I have not seen an actual algorithm that can solve this problem in polynomial time.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2020-05-11. Score: 23

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

> **Comments:**
> **username_2**: Nice summary of problem's complexity.  
> **username_2**: BTW, Do you know analogous results for cubic graphs (undirected and directed)?  
> **username_3**: Very interesting.  5-UCC should be added to the [list of problems between P and NPC](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc).  

---

