<p><a href="https://cstheory.stackexchange.com/a/2818/775">As pointed out by David Eppstein</a> when I asked a related question a while ago: you can do that in polynomial time. </p>

<p>The idea is to find a perfect matching $M$ (which exists and can be found in polynomial time since your graph is cubic and bridgeless), and then to use the edges of $M$ as middle edges of the $P_4$'s.</p>

<p>To complete the construction, remove the edges of $M$ and orient the remaining cycles arbitrarily. Then attach to each edge $\{u, v\}$ of $M$ the arcs going out from $u$ and $v$, and you are done.</p>

CC BY-SA 3.0
2015-03-20T21:35:00.130Z
From MathOverflow answer, all graphs in the class are decomposable into edge-disjoint paths of length 3 (P4). It would be very interesting to find a class where deciding the decomposition existence is not trivial and polynomial time solvable.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-21T09:51:14.893Z
1) Yes, because all you need is a perfect matching and those graphs are known to admit one. 2) It's actually a necessary and sufficient condition (see again David's original answer).
Anthony Labarre
CC BY-SA 3.0
2015-03-19T19:51:04.317Z
2015-03-19T19:51:04.317Z
2017-04-13T12:32:28.077Z
Anthony Labarre
<p>Motivated by this post on <a href="https://mathoverflow.net/questions/156455/cubic-graphs-decompositions">cubic graphs decompositions</a>, I am interested in decomposing a connected bridgeless graph into edge-disjoint paths of length 3 (P4). My intuition is that it should be NP-complete but did not find a reduction. </p>

<p>I am aware that it is $NP$-complete to decide whether a cubic bipartite planar graph is decomposable into vertex-disjoint paths of length 2 (P3).</p>

<blockquote>
  <p>Is it $NP$-complete to decide whether a bridgeless cubic bipartite graph is decomposable into edge-disjoint paths of length 3 (P4)?</p>
</blockquote>

<p>In a related note, Barnette conjecture states that every 3-connected cubic bipartite planar graph is Hamiltonian. This is equivalent to decomposing every such graph into Hamiltonian cycle and a perfect matching. <a href="http://theory.stanford.edu/~tomas/barnew.pdf" rel="nofollow noreferrer">Feder and Subi</a> proved that if there is a single graph in the class of the conjecture which does not admit such decomposition then deciding the existence of Hamiltonian cycle in $NP$-complete in that class.</p>

<blockquote>
  <p>For general connected cubic graph decomposition problems, under which conditions does the existence of a non-decomposable graph imply the $NP$-completeness of the decomposition problem?</p>
</blockquote>

<p><strong>EDIT</strong> For the second question, Is there a subclass of connected bridgeless cubic graphs where non-decomposable graphs exist but it is polynonial time to decide the existence of a (edge) decomposition? </p>

<p>The linked post on MthOverflow provides some interesting examples of connected cubic graph decomposition problems.</p>

<p><strong>EDIT</strong> The problem is posted on MathOverflow: <a href="https://mathoverflow.net/questions/200421/connection-between-barnette-conjecture-and-hardness-of-cubic-graph-decomposition">Connection between Barnette conjecture and hardness of cubic graph decomposition</a></p>

CC BY-SA 3.0
2015-03-17T16:56:28.133Z
@Philip White Here is the reduction http://link.springer.com/chapter/10.1007/11752578_121#page-1
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-17T18:31:16.627Z
@PhilipWhite They proved that perfect P3-matching in cubic bipartite planar 2-connected graphs is NP-complete. The reduction is from 3D matching for planar instances.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-19T11:09:17.080Z
For edge decomposition what are the known results? Is it NPC to find an edge disjoint P4 decomposition on cubic bipartite graphs? (i.e. dropping the "bridgless" constraint)
Marzio De Biasi
CC BY-SA 3.0
2015-03-19T11:27:23.693Z
@MarzioDeBiasi I am not aware of such result. I know that edge-disjoint claw decomposition of graphs in your class is polynomial time since every such graph has claw decomposition.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-19T13:39:38.390Z
@MohammadAl-Turkistany: ok, I thought that if you asked for bridgeless then the problem was known for the more general class. Another trivial question: what is exactly a *vertex-disjoint* decomposition of a graph in P3 paths? (if you fix the size of the elements used to decompose the graph and ask for a *vertex-disjoint* decomposition then the problem should be polynomial time solvable)
Marzio De Biasi
<cc.complexity-theory><graph-theory>
Is it $NP$-complete to decompose bridgeless cubic bipartite graph into edge-disjoint paths of length 3?
Mohammad Al-Turkistany
# Is it $NP$-complete to decompose bridgeless cubic bipartite graph into edge-disjoint paths of length 3?

(Asked by: username_0 on 2015-03-15)

Motivated by this post on [cubic graphs decompositions](https://mathoverflow.net/questions/156455/cubic-graphs-decompositions), I am interested in decomposing a connected bridgeless graph into edge-disjoint paths of length 3 (P4). My intuition is that it should be NP-complete but did not find a reduction.

I am aware that it is $NP$-complete to decide whether a cubic bipartite planar graph is decomposable into vertex-disjoint paths of length 2 (P3).

> Is it $NP$-complete to decide whether a bridgeless cubic bipartite graph is decomposable into edge-disjoint paths of length 3 (P4)?

In a related note, Barnette conjecture states that every 3-connected cubic bipartite planar graph is Hamiltonian. This is equivalent to decomposing every such graph into Hamiltonian cycle and a perfect matching. [Feder and Subi](http://theory.stanford.edu/~tomas/barnew.pdf) proved that if there is a single graph in the class of the conjecture which does not admit such decomposition then deciding the existence of Hamiltonian cycle in $NP$-complete in that class.

> For general connected cubic graph decomposition problems, under which conditions does the existence of a non-decomposable graph imply the $NP$-completeness of the decomposition problem?

**EDIT** For the second question, Is there a subclass of connected bridgeless cubic graphs where non-decomposable graphs exist but it is polynonial time to decide the existence of a (edge) decomposition?

The linked post on MthOverflow provides some interesting examples of connected cubic graph decomposition problems.

**EDIT** The problem is posted on MathOverflow: [Connection between Barnette conjecture and hardness of cubic graph decomposition](https://mathoverflow.net/questions/200421/connection-between-barnette-conjecture-and-hardness-of-cubic-graph-decomposition)

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

> **Comments:**
> **username_0**: @Philip White Here is the reduction http://link.springer.com/chapter/10.1007/11752578_121#page-1  
> **username_0**: @PhilipWhite They proved that perfect P3-matching in cubic bipartite planar 2-connected graphs is NP-complete. The reduction is from 3D matching for planar instances.  
> **username_1**: For edge decomposition what are the known results? Is it NPC to find an edge disjoint P4 decomposition on cubic bipartite graphs? (i.e. dropping the "bridgless" constraint)  
> **username_0**: @MarzioDeBiasi I am not aware of such result. I know that edge-disjoint claw decomposition of graphs in your class is polynomial time since every such graph has claw decomposition.  
> **username_1**: @MohammadAl-Turkistany: ok, I thought that if you asked for bridgeless then the problem was known for the more general class. Another trivial question: what is exactly a *vertex-disjoint* decomposition of a graph in P3 paths? (if you fix the size of the elements used to decompose the graph and ask for a *vertex-disjoint* decomposition then the problem should be polynomial time solvable)  

---

## 1 answers

### Answer by username_2 on 2015-03-19. Score: 5 | Accepted answer

[As pointed out by David Eppstein](https://cstheory.stackexchange.com/a/2818/775) when I asked a related question a while ago: you can do that in polynomial time.

The idea is to find a perfect matching $M$ (which exists and can be found in polynomial time since your graph is cubic and bridgeless), and then to use the edges of $M$ as middle edges of the $P\_4$'s.

To complete the construction, remove the edges of $M$ and orient the remaining cycles arbitrarily. Then attach to each edge $\{u, v\}$ of $M$ the arcs going out from $u$ and $v$, and you are done.

> **Comments:**
> **username_0**: From MathOverflow answer, all graphs in the class are decomposable into edge-disjoint paths of length 3 (P4). It would be very interesting to find a class where deciding the decomposition existence is not trivial and polynomial time solvable.  
> **username_2**: 1) Yes, because all you need is a perfect matching and those graphs are known to admit one. 2) It's actually a necessary and sufficient condition (see again David's original answer).  

---

