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)?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Nice, I didn't think to look for literature on triangle covers. What are some good references on this problem? $\endgroup$ Commented 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$– JimNCommented Jan 9 at 23:29