<p>A partition into vertex-disjoint cycles is the same thing as a 2-regular subgraph, more commonly known as a 2-factor. It can be found (if it exists) in polynomial time by an algorithm based on matching. <s>E.g. see <a href="http://books.google.com/books?id=-X39_rA3VSQC&amp;pg=PA572" rel="noreferrer">this link</a>.</s></p>

<p>ETA Nov 2013: It seems from comments below that the reduction from the source linked above is wrong. However, the statement that the problem can be reduced to perfect matching remains correct. The correct reduction is in W. T. Tutte (1954), "A short proof of the factor theorem for finite graphs", <a href="http://dx.doi.org/10.4153/CJM-1954-033-3" rel="noreferrer">Canadian J. Math. 6: 347–352</a>.</p>

<p>Replace each vertex $v$ with degree $d$ by a complete bipartite graph $G_v=K_{d,\,d-2}$, and represent each edge $uv$ of the original graph by an edge from one vertex of $G_u$ to one vertex of $G_v$ (on the side of the bipartition with $d$ vertices) in such a way that each vertex of $G_v$ on that side of the bipartition has exactly one such edge incident to it.</p>

<p>Then a perfect matching in the modified graph has to match the $d-2$ vertices on their side of the bipartition of $G_v$ with $d-2$ out of the $d$ vertices on the other side, leaving exactly two free vertices that need to be matched with their neighbors in other subgraphs $G_u$. In this way, the perfect matchings of the modified graph correspond 1-for-1 with cycle covers of the original graph.</p>

CC BY-SA 3.0
2013-11-15T18:54:37.737Z
I don't get it. All the mentions I've found, of this algorithm, start by computing an euler tour. However there are lots of graphs that are cycle coverable without having an euler tour. Is it also in P if we don't require all edges to be used?
Thomas Ahle
CC BY-SA 3.0
2013-11-15T21:35:12.180Z
Did you read the article I linked to? I see no mention of Euler tours there.
David Eppstein
CC BY-SA 3.0
2013-11-15T23:17:13.047Z
It's just a bit hard to understand. When you construct $E'$ by changing each edge $(i,j)$ to an edge from $V$ to $V'$ ($(i,j')$) how do you know which end to put in $V$ and which to put in $V'$? The paper seems to "just take the second one", but it's not a directed graph..
Thomas Ahle
CC BY-SA 3.0
2013-11-18T07:28:34.683Z
I mean, I could also convert every undirected edge into a directed edge in each direction, but then the matching might just give me a lot of "length 2" cycles, no?
Thomas Ahle
CC BY-SA 3.0
2013-11-18T14:15:48.907Z
I read the section in 'Algorithmic graph theory' as well, and they also seem to just imply that the matching obviously gives a 2-factor. Even though the matching obviously could 'collapse' into a 1-factor.
Thomas Ahle
CC BY-SA 3.0
2013-11-20T11:04:45.677Z
Sweet! I love this new reduction. Works perfectly. Thanks :)
Thomas Ahle
CC BY-SA 3.0
2013-11-20T19:14:22.060Z
For values of "new" meaning published in 1954... You're welcome, anyway. Sorry for the confusion re the other reduction.
David Eppstein
CC BY-SA 4.0
2019-01-16T10:55:54.967Z
That approach can apparently also be used to find optimal k-regular spanners, albeit not necessarily connected ones.
Manfred Weis
CC BY-SA 4.0
2019-12-13T10:35:11.847Z
@ManfredWeis What is a k-regular spanner? Usually, graph spanners preserve paths, so they have to be connected. It seems that the approach can find k-regular spanning subgraphs, is that what you mean?
Thomas Ahle
CC BY-SA 4.0
2019-12-13T22:04:52.047Z
@ThomasAhle apparently mixed up terms; what I meant is a $k$-regular *spanning* graph, a.k.a $k$-factor
Manfred Weis
CC BY-SA 4.0
2019-12-14T13:29:05.340Z
@ManfredWeis Right. And that's actually pretty cool, since finding a regular subgraph is NP hard for $k\ge 3$(!) https://www.sciencedirect.com/science/article/pii/0012365X84901134
Thomas Ahle
CC BY-SA 4.0
2019-12-14T16:04:06.990Z
@ThomasAhle that can't be true for simple undirected graphs, see e.g.  [An Algorithm for Calculating k-Factors](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=2ahUKEwjrlLnmvrXmAhVjxcQBHaNaAVoQFjAAegQIBhAC&url=http%3A%2F%2Fwww.cs.queensu.ca%2Fhome%2Fdaver%2FMyPDF%2FOn_k_Factors_IPL.pdf&usg=AOvVaw2iQxVm9zbeeSMirYLizvRq) by Meijer, Nunez-Rodriguez, and D. Rappaport; Tutte als provided a reduction to the matching problem.
Manfred Weis
CC BY-SA 4.0
2022-02-02T00:41:02.617Z
Just want to note down for anyone who reads this in the future that the original reduction *does* work for directed graphs, but indeed fails for undirected ones.
inavda
CC BY-SA 4.0
2022-05-13T14:46:52.323Z
I didn't get the construction... Can you explain it using an example, say K_3 (complete 3 vertex graph)?
nutella_eater
CC BY-SA 3.0
2011-10-11T04:31:48.030Z
2013-11-19T00:49:33.380Z
2013-11-19T00:49:33.380Z
David Eppstein
<p><strong>Related problem:</strong> Veblen’s Theorem states that "A graph admits a cycle decomposition if and only if it is even". The cycles are edge disjoint, but not necessarily node disjoint. Put another way, "The edge set of a graph can be partitioned into cycles if and only if every vertex has even degree."</p>

<p><strong>My Problem:</strong> I wonder has anybody studied the partition a graph into node-disjoint cycles. That is, partition the vertices $V$ of a graph $G$ into $V_1, V_2, \cdots, V_k$, and each subgraph induced by $V_i$ is hamiltonian. </p>

<p>Is it NP-hard or easy?</p>

<p><strong>More related problem:</strong> 
Partition into triangle is NP-complete. (Page 68 of "Computers and intractability")</p>

<p>Thank you for your advise in advance. ^^</p>

CC BY-SA 3.0
2011-10-11T04:27:29.077Z
There is an easy reduction to matching. Well known exercise in algorithms.
Chandra Chekuri
CC BY-SA 3.0
2013-11-15T17:58:05.763Z
Is this your problem: http://en.wikipedia.org/wiki/Vertex_cycle_cover ?
Thomas Ahle
CC BY-SA 3.0
2014-03-21T09:43:54.040Z
@ThomasAhle Thanks, I was unaware of that wiki page. It is called 'disjoint cycle cover' mentioned in that wiki page.
Peng Zhang
<cc.complexity-theory><graph-theory><co.combinatorics>
Partition a graph into node-disjoint cycles
Peng Zhang
# Partition a graph into node-disjoint cycles

(Asked by: username_0 on 2011-10-10)

**Related problem:** Veblen’s Theorem states that "A graph admits a cycle decomposition if and only if it is even". The cycles are edge disjoint, but not necessarily node disjoint. Put another way, "The edge set of a graph can be partitioned into cycles if and only if every vertex has even degree."

**My Problem:** I wonder has anybody studied the partition a graph into node-disjoint cycles. That is, partition the vertices $V$ of a graph $G$ into $V\_1, V\_2, \cdots, V\_k$, and each subgraph induced by $V\_i$ is hamiltonian.

Is it NP-hard or easy?

**More related problem:**
Partition into triangle is NP-complete. (Page 68 of "Computers and intractability")

Thank you for your advise in advance. ^^

**Tags:** cc.complexity-theory, graph-theory, co.combinatorics

> **Comments:**
> **username_1**: There is an easy reduction to matching. Well known exercise in algorithms.  
> **username_2**: Is this your problem: http://en.wikipedia.org/wiki/Vertex_cycle_cover ?  
> **username_0**: @ThomasAhle Thanks, I was unaware of that wiki page. It is called 'disjoint cycle cover' mentioned in that wiki page.  

---

## 1 answers

### Answer by username_3 on 2011-10-11. Score: 25 | Accepted answer

A partition into vertex-disjoint cycles is the same thing as a 2-regular subgraph, more commonly known as a 2-factor. It can be found (if it exists) in polynomial time by an algorithm based on matching. ~~E.g. see [this link](http://books.google.com/books?id=-X39_rA3VSQC&pg=PA572).~~

ETA Nov 2013: It seems from comments below that the reduction from the source linked above is wrong. However, the statement that the problem can be reduced to perfect matching remains correct. The correct reduction is in W. T. Tutte (1954), "A short proof of the factor theorem for finite graphs", [Canadian J. Math. 6: 347–352](http://dx.doi.org/10.4153/CJM-1954-033-3).

Replace each vertex $v$ with degree $d$ by a complete bipartite graph $G\_v=K\_{d,\,d-2}$, and represent each edge $uv$ of the original graph by an edge from one vertex of $G\_u$ to one vertex of $G\_v$ (on the side of the bipartition with $d$ vertices) in such a way that each vertex of $G\_v$ on that side of the bipartition has exactly one such edge incident to it.

Then a perfect matching in the modified graph has to match the $d-2$ vertices on their side of the bipartition of $G\_v$ with $d-2$ out of the $d$ vertices on the other side, leaving exactly two free vertices that need to be matched with their neighbors in other subgraphs $G\_u$. In this way, the perfect matchings of the modified graph correspond 1-for-1 with cycle covers of the original graph.

> **Comments:**
> **username_2**: I don't get it. All the mentions I've found, of this algorithm, start by computing an euler tour. However there are lots of graphs that are cycle coverable without having an euler tour. Is it also in P if we don't require all edges to be used?  
> **username_3**: Did you read the article I linked to? I see no mention of Euler tours there.  
> **username_2**: It's just a bit hard to understand. When you construct $E'$ by changing each edge $(i,j)$ to an edge from $V$ to $V'$ ($(i,j')$) how do you know which end to put in $V$ and which to put in $V'$? The paper seems to "just take the second one", but it's not a directed graph..  
> **username_2**: I mean, I could also convert every undirected edge into a directed edge in each direction, but then the matching might just give me a lot of "length 2" cycles, no?  
> **username_2**: I read the section in 'Algorithmic graph theory' as well, and they also seem to just imply that the matching obviously gives a 2-factor. Even though the matching obviously could 'collapse' into a 1-factor.  
> **username_2**: Sweet! I love this new reduction. Works perfectly. Thanks :)  
> **username_3**: For values of "new" meaning published in 1954... You're welcome, anyway. Sorry for the confusion re the other reduction.  
> **username_4**: That approach can apparently also be used to find optimal k-regular spanners, albeit not necessarily connected ones.  
> **username_2**: @ManfredWeis What is a k-regular spanner? Usually, graph spanners preserve paths, so they have to be connected. It seems that the approach can find k-regular spanning subgraphs, is that what you mean?  
> **username_4**: @ThomasAhle apparently mixed up terms; what I meant is a $k$-regular *spanning* graph, a.k.a $k$-factor  
> **username_2**: @ManfredWeis Right. And that's actually pretty cool, since finding a regular subgraph is NP hard for $k\ge 3$(!) https://www.sciencedirect.com/science/article/pii/0012365X84901134  
> **username_4**: @ThomasAhle that can't be true for simple undirected graphs, see e.g.  [An Algorithm for Calculating k-Factors](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=2ahUKEwjrlLnmvrXmAhVjxcQBHaNaAVoQFjAAegQIBhAC&url=http%3A%2F%2Fwww.cs.queensu.ca%2Fhome%2Fdaver%2FMyPDF%2FOn_k_Factors_IPL.pdf&usg=AOvVaw2iQxVm9zbeeSMirYLizvRq) by Meijer, Nunez-Rodriguez, and D. Rappaport; Tutte als provided a reduction to the matching problem.  
> **username_5**: Just want to note down for anyone who reads this in the future that the original reduction *does* work for directed graphs, but indeed fails for undirected ones.  
> **username_6**: I didn't get the construction... Can you explain it using an example, say K_3 (complete 3 vertex graph)?  

---

