Decomposition of edges of eulerian graph into maximum number of cycles

Question

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?

Answer 1

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

• krumpelstiltskin: 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.