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