# Complexity of the edge-disjoint cycle covers

I am interested in decompositions of a directed graph $G=(V,E)$ into non-intersecting Eulerian subgraphs $G_i=(V_i, E_i)$. I want to find the decomposition that covers the largest number of edges.

I believe that the best case is when a "Eulerian decomposition" exists, that is, the union of $E_i$ gives back $E$.

This problem is related to the minimum cycle cover of a graph but distinct. The minimum cycle cover wants to find cycles covering all edges with minimum overlap, whereas I want find cycles with no overlap covering as many edges as possible.

More specifically, I am interested in complexity results related to the following problems:

• Given an integer $k$, is there an edge-disjoint cycle decomposition covering more than $k$ edges?
• Is there an edge-disjoint cycle decomposition covering all edges?

Edit:

• The second question has been answered in comments and appears to be polynomial.
• The first question seems to be equivalent to "What is the smallest number of edges that can be removed from a graph so that each vertex has the same in-degree as its out-degree."
• You might as well require the $G_i$ to be vertex-disjoint (since any $G_i,G_j$ which share vertices but no edges can be combined into a single Eulerian graph $(V_i\cup V_j,E_i\cup E_j)$). Mar 7, 2016 at 13:57
• Fair enough. I hadn't thought of that. Mar 7, 2016 at 15:03
• From @KlausDraeger 's observation, it's easy to see that the second problem is equivalent to asking if the graph is Eulerian (in non-connected graphs one can work on each component independently). Mar 7, 2016 at 16:54

The problem is polynomial-time solvable.

Say that a vertex is balanced if its in-degree equals its out-degree.

Note that a directed graph is Eulerian iff every vertex is balanced and its underlying undirected graph is connected. Now, a directed graph is a vertex-disjoint union of Eulerian graphs iff every vertex is balanced. So, the problem amounts to deleting a smallest number of arcs so that each vertex becomes balanced. In Theorem 2 of the following paper, this problem is solved in polynomial time using network flows.