<p>The problem is polynomial-time solvable.</p>

<p>Say that a vertex is <em>balanced</em> if its in-degree equals its out-degree.</p>

<p>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.</p>

<ul>
<li>Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
<a href="http://dx.doi.org/10.1007/s00453-012-9667-x">Parameterized Complexity of Eulerian Deletion Problems</a>. Algorithmica 68(1): 41-61 (2014).</li>
</ul>

CC BY-SA 3.0
2016-03-09T14:37:13.523Z
2016-03-09T14:37:13.523Z
Serge Gaspers
<p>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.</p>

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

<p>This problem is related to the <a href="http://dx.doi.org/10.1137/S0097539794267255" rel="noreferrer">minimum cycle cover of a graph</a> 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.</p>

<p>More specifically, I am interested in complexity results related to the following problems:</p>

<ul>
<li>Given an integer $k$, is there an edge-disjoint cycle decomposition covering more than $k$ edges?</li>
<li>Is there an edge-disjoint cycle decomposition covering all edges?</li>
</ul>

<p><strong>Edit:</strong></p>

<ul>
<li>The second question has been answered in comments and appears to be polynomial.</li>
<li>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."</li>
</ul>

CC BY-SA 3.0
2016-03-07T13:57:41.830Z
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
CC BY-SA 3.0
2016-03-07T15:03:06.470Z
Fair enough. I hadn't thought of that.
Abdallah
CC BY-SA 3.0
2016-03-07T16:54:08.480Z
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
<cc.complexity-theory><reference-request><graph-theory><covering-problems>
Complexity of the edge-disjoint cycle covers
Abdallah
# Complexity of the edge-disjoint cycle covers

(Asked by: username_0 on 2016-03-07)

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](http://dx.doi.org/10.1137/S0097539794267255) 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."

**Tags:** cc.complexity-theory, reference-request, graph-theory, covering-problems

> **Comments:**
> **username_1**: 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)$).  
> **username_0**: Fair enough. I hadn't thought of that.  
> **username_2**: 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).  

---

## 1 answers

### Answer by username_3 on 2016-03-09. Score: 9 | Accepted answer

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](http://dx.doi.org/10.1007/s00453-012-9667-x). Algorithmica 68(1): 41-61 (2014).


---

