<p>Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard?</p>
<p>Without the degree condition, the problem is the &quot;cycle packing problem&quot;, which is claimed to be NP-hard (page 2 <a href="https://citeseerx.ist.psu.edu/document?repid=rep1&amp;type=pdf&amp;doi=1fc63aebacb686916172a9b7e48caf50a031f672" rel="noreferrer">here</a>), although I could not track down where this claim originates from. With the degree condition, the difference is that now we can put every edge into some cycle, but it is unclear that this makes the problem any easier.</p>

CC BY-SA 4.0
2023-03-13T22:05:43.317Z
Related question (without a definitive answer), for Eulerian graphs: https://math.stackexchange.com/questions/2419271/decomposition-of-edges-of-eulerian-graph-into-maximum-number-of-cycles
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-03-14T07:52:07.560Z
In fact the answer to that question shows NP-hardness of finding the best cycle cover (i.e., covering with triangles), but for (Eulerian) undirected graphs.
Antoine Amarilli 'a3nm'
<graph-theory><np-hardness>
Cycle packing with degree condition
TZM
# Cycle packing with degree condition

(Asked by: username_0 on 2023-03-13)

Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard?

Without the degree condition, the problem is the "cycle packing problem", which is claimed to be NP-hard (page 2 [here](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=1fc63aebacb686916172a9b7e48caf50a031f672)), although I could not track down where this claim originates from. With the degree condition, the difference is that now we can put every edge into some cycle, but it is unclear that this makes the problem any easier.

**Tags:** graph-theory, np-hardness
> **Comments:**
> **username_1**: Related question (without a definitive answer), for Eulerian graphs: https://math.stackexchange.com/questions/2419271/decomposition-of-edges-of-eulerian-graph-into-maximum-number-of-cycles  
> **username_1**: In fact the answer to that question shows NP-hardness of finding the best cycle cover (i.e., covering with triangles), but for (Eulerian) undirected graphs.  

---

## 0 answers

