# Is it $NP$-complete to decompose bridgeless cubic bipartite graph into edge-disjoint paths of length 3?

Motivated by this post on 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 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

• Very interesting question...care to share the polynomial time reduction from an NP-complete problem to the bicubic planar graph decomposition problem (for vertex-disjoint paths of length 2)? – Philip White Mar 17 '15 at 16:27
• @Philip White Here is the reduction link.springer.com/chapter/10.1007/11752578_121#page-1 – Mohammad Al-Turkistany Mar 17 '15 at 16:56
• It's behind a paywall, can you just tell me what problem it's a reduction from? – Philip White Mar 17 '15 at 18:21
• @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 Mar 17 '15 at 18:31
• 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 Mar 19 '15 at 11:09

## 1 Answer

As pointed out by David Eppstein 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.

• 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 Mar 20 '15 at 21:35
• 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 Mar 21 '15 at 9:51