<p>This paper may be helpful with regard to the question you raised:
<a href="https://pdfs.semanticscholar.org/32a0/821e384e726819155065f7bc26e2d57329e5.pdf" rel="nofollow noreferrer">https://pdfs.semanticscholar.org/32a0/821e384e726819155065f7bc26e2d57329e5.pdf</a></p>

CC BY-SA 4.0
2021-04-16T16:01:22.340Z
The suggested paper shows the NP-hardness of the problem.  For solutions to a restricted version of the problem, see: "Sorting Permutations by Reversals Through Branch-and-Price" by the same author.
krumpelstiltskin
CC BY-SA 3.0
2017-09-11T23:24:13.303Z
2017-09-11T23:24:13.303Z
Joseph Malkevitch
<p>I'm interested in the following problem.</p>

<p>Given an eulerian graph $G=(V,E)$, we are to find a partition of its edges $C_1, C_2, \ldots, C_k$ ($\cup_i C_i=E$ and $i \neq j \leftrightarrow C_i \cap C_j = \varnothing$), such that each $C_i$ forms a simple cycle in $G$ and $k$ is maximum possible.</p>

<p>In other words, we are to cover every edge of an eulerian graph with a maximum number of edge-disjoint simple cycles.</p>

<p>Is this problem well-known? Is there a known approach to solve it?</p>

<graph-theory><graph-algorithms>
Decomposition of edges of eulerian graph into maximum number of cycles
Dan
# Decomposition of edges of eulerian graph into maximum number of cycles

(Asked by: username_0 on 2017-09-07)

I'm interested in the following problem.

Given an eulerian graph $G=(V,E)$, we are to find a partition of its edges $C\_1, C\_2, \ldots, C\_k$ ($\cup\_i C\_i=E$ and $i \neq j \leftrightarrow C\_i \cap C\_j = \varnothing$), such that each $C\_i$ forms a simple cycle in $G$ and $k$ is maximum possible.

In other words, we are to cover every edge of an eulerian graph with a maximum number of edge-disjoint simple cycles.

Is this problem well-known? Is there a known approach to solve it?

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2017-09-11. Score: 2

This paper may be helpful with regard to the question you raised:
<https://pdfs.semanticscholar.org/32a0/821e384e726819155065f7bc26e2d57329e5.pdf>

> **Comments:**
> **username_2**: The suggested paper shows the NP-hardness of the problem.  For solutions to a restricted version of the problem, see: "Sorting Permutations by Reversals Through Branch-and-Price" by the same author.  

---

