<p>Well, if there is a disjoint triangle cover of <span class="math-container">$G$</span> then this would be the cycle cover  of maximum cardinality. And it is NP-hard to determine if there is a disjoint triangle cover.</p>

CC BY-SA 4.0
2024-01-09T13:06:51.267Z
Nice, I didn't think to look for literature on *triangle* covers. What are some good references on this problem?
delete000
CC BY-SA 4.0
2024-01-09T23:29:07.693Z
@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.
JimN
CC BY-SA 4.0
2024-01-08T07:45:25.967Z
2024-01-08T07:45:25.967Z
JimN
<p>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., <span class="math-container">$k$</span>-regular)?</p>

<ds.algorithms><graph-algorithms><optimization><time-complexity>
Maximum cardinality disjoint cycle cover in undirected graphs
delete000
# Maximum cardinality disjoint cycle cover in undirected graphs

(Asked by: username_0 on 2023-12-29)

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)?

**Tags:** ds.algorithms, graph-algorithms, optimization, time-complexity

---

## 1 answers

### Answer by username_1 on 2024-01-08. Score: 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.

> **Comments:**
> **username_0**: Nice, I didn't think to look for literature on *triangle* covers. What are some good references on this problem?  
> **username_1**: @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.  

---

