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.

$\endgroup$
2
  • $\begingroup$ Related question (without a definitive answer), for Eulerian graphs: math.stackexchange.com/questions/2419271/… $\endgroup$
    – a3nm
    Mar 13, 2023 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, 2023 at 7:52

0

Your Answer

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

Browse other questions tagged or ask your own question.