6
$\begingroup$

Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard?

Without the degree condition, the problem is the "cycle packing problem", which is claimed to be NP-hard (page 2 here), although I could not track down where this claim originates from. With the degree condition, the difference is that now we can put every edge into some cycle, but it is unclear that this makes the problem any easier.

Improve this question
$\endgroup$
2
  • $\begingroup$ Related question (without a definitive answer), for Eulerian graphs: math.stackexchange.com/questions/2419271/… $\endgroup$
    – a3nm
    Mar 13 at 22:05
  • $\begingroup$ In fact the answer to that question shows NP-hardness of finding the best cycle cover (i.e., covering with triangles), but for (Eulerian) undirected graphs. $\endgroup$
    – a3nm
    Mar 14 at 7:52

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.