# 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)$). – Klaus Draeger Mar 7 '16 at 13:57
• Fair enough. I hadn't thought of that. – Abdallah Mar 7 '16 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). – chazisop Mar 7 '16 at 16:54