<p>This isn't an answer to the complexity of the problem, but it at least shows that the complexity has a chance at being nontrivial: it's an example of a cubic graph that cannot be partitioned into paths and claws.</p>

<p><a href="https://i.sstatic.net/fT5xZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fT5xZ.png" alt="alt text"></a><br>
<sub>(source: <a href="https://www.ics.uci.edu/~eppstein/0xDE/cubic-unmatchable.png" rel="nofollow noreferrer">uci.edu</a>)</sub>  </p>

<p>Within each of its three lobes, any partition into paths and claws can only use six of the seven edges. The remaining six central edges take the form of a claw with each edge subdivided, which cannot be partitioned into paths and claws.</p>

<p><strong>ETA</strong>: The graph shown above is more famous as an example of a cubic graph without a perfect matching. But every cubic graph with a perfect matching has a decomposition into paths (not even using any claws). By König's theorem this includes all cubic bipartite graphs and by Petersen's theorem this includes all bridgeless cubic graphs, answering a question of Joseph Malkevitch in the comments.</p>

<p>The proof is very simple: if M is a perfect matching in a cubic graph, the removal of M leaves a 2-regular graph, that is, a disjoint union of cycles. Orient each cycle arbitrarily, and attach each edge uv of M to the cycle edges that follow u and v in the orientations of their cycles.</p>

<p>In the other direction, if there exists a decomposition into paths, then there exists a perfect matching: the middle edges of each path must be a matching since no two middle edges can share a degree-three vertex.</p>

<p>(Disclaimer: this idea may have already been present in Carsten Thomassen's invited talk at GD 2010, which was about this sort of graph decomposition problem.)</p>

<p>(addition to disclaimer (by Anthony Labarre): the "orientation idea" for going from a perfect matching to a partition into paths appears in <a href="http://dx.doi.org/10.1002/jgt.3190090416" rel="nofollow noreferrer">this paper by Jünger, Reinelt and Pulleyblank</a>, who attribute it to W. H. Cunningham.)</p>

CC BY-SA 2.5
2010-11-09T18:27:02.337Z
This nice example while plane is not 2-connected. A next step might be to look at plane 2-connected graphs.
Joseph Malkevitch
CC BY-SA 2.5
2010-11-10T08:25:00.197Z
Thanks for your valuable comments and this counterexample, I can stop looking for one ;-)
Anthony Labarre
CC BY-SA 2.5
2010-11-10T15:47:18.967Z
You might find it useful that these lobes (the unique graph with degree sequence 1,3,3,3,3,3) can (I think) be used in place of a loop-on-an-edge in a multigraph generalization of your problem.
Colin McQuillan
CC BY-SA 4.0
2010-11-09T17:45:38.973Z
2019-02-18T10:10:28.450Z
2019-02-18T10:10:28.450Z
David Eppstein
<p>Perhaps this paper may be of interest:</p>

<p>Kleinschmidt, Peter
Regular partitions of regular graphs.
Canad. Math. Bull. 21 (1978), no. 2, 177–181. </p>

<p>It deals with graphs which can be written as the union of "Z-paths" of length 3. (Specifically, planar, 3-valent, 3-connected graphs-cubic 3-polytopes.)</p>

CC BY-SA 2.5
2010-11-09T02:50:43.617Z
2010-11-09T02:50:43.617Z
Joseph Malkevitch
<p><strike>It seems I had missed <a href="http://dx.doi.org/10.1016/0166-218X(85)90008-3" rel="nofollow">this other paper by Dyer and Frieze</a>, where they prove that partitioning the edges of a planar bipartite graph into connected components with $k$ edges is NP-complete for any fixed $k\geq 3$ (Theorem 3.1 p. 145). They then comment that the problem can be shown to remain NP-complete for $k=3$ if all vertices have degree $2$ or $3$, which unless I parsed this the wrong way includes my problem (since the input is bipartite, the graph contains no odd cycle and in particular no triangle, which means that the only subgraphs we can use are claws and paths).</strike></p>

<p>This wasn't actually the end of the story: if the cubic graph is bipartite, then it's easy to partition its edge set using only claws, by selecting one set of the bipartition and making it a set of "claw centers". The general problem is indeed hard, which can be proved using a reduction from CUBIC PLANAR MONOTONE 1-IN-3 SATISFIABILITY. All details are <a href="http://arxiv.org/abs/1604.08603" rel="nofollow">freely accessible on arxiv</a>.</p>

CC BY-SA 3.0
2010-11-11T09:27:53.930Z
2016-05-02T16:12:06.610Z
2016-05-02T16:12:06.610Z
Anthony Labarre
<p>Again an edge-partitioning problem whose complexity I'm curious about, motivated by <a href="https://cstheory.stackexchange.com/questions/2307/an-edge-partitioning-problem-on-cubic-graphs">a previous question of mine</a>.</p>

<hr>

<p><strong>Input:</strong> a cubic graph $G=(V,E)$</p>

<p><strong>Question:</strong> is there a partition of $E$ into $E_1, E_2, \ldots, E_s$, such that the subgraph induced by each $E_i$ is either a claw (i.e. $K_{1,3}$, often called a star) or a $3$-path (i.e. $P_4$)?</p>

<hr>

<p>I think I saw a paper one day where this problem was proven to be NP-complete, but I cannot find it anymore, and I don't remember whether that result applied to cubic graphs. On a related matter, I'm aware that edge-partitioning a bipartite graph into claws is NP-complete (see <a href="http://dx.doi.org/10.1016/0196-6774(86)90002-7" rel="nofollow noreferrer">Dyer and Frieze</a>). Does anyone have a reference for the problem I describe, or something related (i.e. the same problem on another graph class, that I could then try to reduce to cubic graphs)?</p>

CC BY-SA 2.5
2010-11-08T20:03:28.843Z
This may help you: Edge Partition into $K_3$ and $K_{1,3}$ is $NP$-Complete.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-08T20:15:08.347Z
turkistany, could you add a reference for that to your comment?
Anthony Labarre
CC BY-SA 2.5
2010-11-08T20:28:34.633Z
Anthony, Here is the link 
(http://www.andrew.cmu.edu/user/jblocki/K-Anonymity.pdf)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-08T20:41:06.597Z
Oh, right. That's the paper I remembered, which I wrongly thought tackled exactly my problem. Well, thanks anyway for the reminder, maybe I can indeed do something with it...
Anthony Labarre
CC BY-SA 2.5
2010-11-09T16:39:28.267Z
Do you have an example of a cubic graph that cannot be partitioned in this way?
David Eppstein
CC BY-SA 2.5
2010-11-09T17:18:27.193Z
No. I'm currently trying to find such counterexamples using Meringer's list (http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html), but haven't implemented anything to automate that verification yet.
Anthony Labarre
CC BY-SA 2.5
2010-11-09T17:55:45.870Z
@Anthony, is $s$ part of the input, or is it fixed, or are you simply wanting to know if a partition exists (for some $s$) as David suggests?
András Salamon
CC BY-SA 2.5
2010-11-09T21:02:07.510Z
What do you mean by the subgraph induced by a set of edges?  Is it simply the graph formed by the set of edges together with all the endpoints of the edges in the set?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-09T22:48:19.667Z
András: since both kinds of subgraph have exactly three edges, s can only be m/3 = n/2.
David Eppstein
CC BY-SA 2.5
2010-11-10T08:22:43.227Z
Tsuyoshi: yes, this is what I meant. András: see David's reply. And I'm interested in obtaining an actual partition, not just knowing that I can get one.
Anthony Labarre
CC BY-SA 4.0
2024-01-24T20:54:34.373Z
The link by @MohammadAl-Turkistany above is dead, but fortunately Wayback machine has it: https://web.archive.org/web/20150414064939/https://www.andrew.cmu.edu/user/jblocki/K-Anonymity.pdf
Antoine Amarilli 'a3nm'
<cc.complexity-theory><graph-theory><np-hardness><co.combinatorics>
Edge-partitioning cubic graphs into claws and paths
Anthony Labarre
# Edge-partitioning cubic graphs into claws and paths

(Asked by: username_0 on 2010-11-08)

Again an edge-partitioning problem whose complexity I'm curious about, motivated by [a previous question of mine](https://cstheory.stackexchange.com/questions/2307/an-edge-partitioning-problem-on-cubic-graphs).

---

**Input:** a cubic graph $G=(V,E)$

**Question:** is there a partition of $E$ into $E\_1, E\_2, \ldots, E\_s$, such that the subgraph induced by each $E\_i$ is either a claw (i.e. $K\_{1,3}$, often called a star) or a $3$-path (i.e. $P\_4$)?

---

I think I saw a paper one day where this problem was proven to be NP-complete, but I cannot find it anymore, and I don't remember whether that result applied to cubic graphs. On a related matter, I'm aware that edge-partitioning a bipartite graph into claws is NP-complete (see [Dyer and Frieze](http://dx.doi.org/10.1016/0196-6774(86)90002-7)). Does anyone have a reference for the problem I describe, or something related (i.e. the same problem on another graph class, that I could then try to reduce to cubic graphs)?

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

> **Comments:**
> **username_1**: This may help you: Edge Partition into $K_3$ and $K_{1,3}$ is $NP$-Complete.  
> **username_0**: turkistany, could you add a reference for that to your comment?  
> **username_1**: Anthony, Here is the link  (http://www.andrew.cmu.edu/user/jblocki/K-Anonymity.pdf)  
> **username_0**: Oh, right. That's the paper I remembered, which I wrongly thought tackled exactly my problem. Well, thanks anyway for the reminder, maybe I can indeed do something with it...  
> **username_2**: Do you have an example of a cubic graph that cannot be partitioned in this way?  
> **username_0**: No. I'm currently trying to find such counterexamples using Meringer's list (http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html), but haven't implemented anything to automate that verification yet.  
> **username_3**: @Anthony, is $s$ part of the input, or is it fixed, or are you simply wanting to know if a partition exists (for some $s$) as David suggests?  
> **username_4**: What do you mean by the subgraph induced by a set of edges?  Is it simply the graph formed by the set of edges together with all the endpoints of the edges in the set?  
> **username_2**: András: since both kinds of subgraph have exactly three edges, s can only be m/3 = n/2.  
> **username_0**: Tsuyoshi: yes, this is what I meant. András: see David's reply. And I'm interested in obtaining an actual partition, not just knowing that I can get one.  
> **username_5**: The link by @MohammadAl-Turkistany above is dead, but fortunately Wayback machine has it: https://web.archive.org/web/20150414064939/https://www.andrew.cmu.edu/user/jblocki/K-Anonymity.pdf  

---

## 3 answers

### Answer by username_0 on 2010-11-11. Score: 9 | Accepted answer

It seems I had missed [this other paper by Dyer and Frieze](http://dx.doi.org/10.1016/0166-218X(85)90008-3), where they prove that partitioning the edges of a planar bipartite graph into connected components with $k$ edges is NP-complete for any fixed $k\geq 3$ (Theorem 3.1 p. 145). They then comment that the problem can be shown to remain NP-complete for $k=3$ if all vertices have degree $2$ or $3$, which unless I parsed this the wrong way includes my problem (since the input is bipartite, the graph contains no odd cycle and in particular no triangle, which means that the only subgraphs we can use are claws and paths).

This wasn't actually the end of the story: if the cubic graph is bipartite, then it's easy to partition its edge set using only claws, by selecting one set of the bipartition and making it a set of "claw centers". The general problem is indeed hard, which can be proved using a reduction from CUBIC PLANAR MONOTONE 1-IN-3 SATISFIABILITY. All details are [freely accessible on arxiv](http://arxiv.org/abs/1604.08603).


---

### Answer by username_2 on 2010-11-09. Score: 15

This isn't an answer to the complexity of the problem, but it at least shows that the complexity has a chance at being nontrivial: it's an example of a cubic graph that cannot be partitioned into paths and claws.

[![alt text](https://i.sstatic.net/fT5xZ.png)](https://i.sstatic.net/fT5xZ.png)  
(source: [uci.edu](https://www.ics.uci.edu/~eppstein/0xDE/cubic-unmatchable.png))

Within each of its three lobes, any partition into paths and claws can only use six of the seven edges. The remaining six central edges take the form of a claw with each edge subdivided, which cannot be partitioned into paths and claws.

**ETA**: The graph shown above is more famous as an example of a cubic graph without a perfect matching. But every cubic graph with a perfect matching has a decomposition into paths (not even using any claws). By König's theorem this includes all cubic bipartite graphs and by Petersen's theorem this includes all bridgeless cubic graphs, answering a question of username_6 in the comments.

The proof is very simple: if M is a perfect matching in a cubic graph, the removal of M leaves a 2-regular graph, that is, a disjoint union of cycles. Orient each cycle arbitrarily, and attach each edge uv of M to the cycle edges that follow u and v in the orientations of their cycles.

In the other direction, if there exists a decomposition into paths, then there exists a perfect matching: the middle edges of each path must be a matching since no two middle edges can share a degree-three vertex.

(Disclaimer: this idea may have already been present in Carsten Thomassen's invited talk at GD 2010, which was about this sort of graph decomposition problem.)

(addition to disclaimer (by username_0): the "orientation idea" for going from a perfect matching to a partition into paths appears in [this paper by Jünger, Reinelt and Pulleyblank](http://dx.doi.org/10.1002/jgt.3190090416), who attribute it to W. H. Cunningham.)

> **Comments:**
> **username_6**: This nice example while plane is not 2-connected. A next step might be to look at plane 2-connected graphs.  
> **username_0**: Thanks for your valuable comments and this counterexample, I can stop looking for one ;-)  
> **username_7**: You might find it useful that these lobes (the unique graph with degree sequence 1,3,3,3,3,3) can (I think) be used in place of a loop-on-an-edge in a multigraph generalization of your problem.  

---

### Answer by username_6 on 2010-11-09. Score: 6

Perhaps this paper may be of interest:

Kleinschmidt, Peter
Regular partitions of regular graphs.
Canad. Math. Bull. 21 (1978), no. 2, 177–181.

It deals with graphs which can be written as the union of "Z-paths" of length 3. (Specifically, planar, 3-valent, 3-connected graphs-cubic 3-polytopes.)


---

