2
$\begingroup$

I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this problem in general and in restricted graph classes (e.g., $k$-regular)?

$\endgroup$

1 Answer 1

2
$\begingroup$

Well, if there is a disjoint triangle cover of $G$ then this would be the cycle cover of maximum cardinality. And it is NP-hard to determine if there is a disjoint triangle cover.

$\endgroup$
2
  • $\begingroup$ Nice, I didn't think to look for literature on triangle covers. What are some good references on this problem? $\endgroup$
    – delete000
    Jan 9 at 13:06
  • 1
    $\begingroup$ @delete000 there is a lot, so it really depends on what direction you want to go into ... FPT exact algorithms, approximation algorithms, heuristics, etc. I don't know if there are results on $k$-regular graphs, and I'm not yet convinced it remains hard on $k$-regular graphs. $\endgroup$
    – JimN
    Jan 9 at 23:29

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.