7
$\begingroup$

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."
$\endgroup$
  • 3
    $\begingroup$ 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)$). $\endgroup$ – Klaus Draeger Mar 7 '16 at 13:57
  • $\begingroup$ Fair enough. I hadn't thought of that. $\endgroup$ – Abdallah Mar 7 '16 at 15:03
  • 2
    $\begingroup$ 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). $\endgroup$ – chazisop Mar 7 '16 at 16:54
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.