Complexity of the edge-disjoint cycle covers

Question

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

Answer 1

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.

• Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter: Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68(1): 41-61 (2014).