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?


1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$ Apr 16, 2021 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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