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


Barnette's 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.



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


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



> 
> For general connected cubic graph decomposition problems, under which conditions does the existence of a non-decomposable graph (in some class) imply the $NP$-completeness of the decomposition decision problem? Is there a subclass of connected bridgeless cubic graphs where a non-decomposable graphs exist but it is polynomial time to decide the existence of a (edge) decomposition? 
> 
> 
> 


The decomposition decision problem should be non-trivial.


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


The problem was posted on [TCS SE](https://cstheory.stackexchange.com/questions/30817/is-it-np-complete-to-decompose-bridgeless-cubic-bipartite-graph-into-edge-disj).



Connection between Barnette conjecture and hardness of cubic graph decomposition
It is easy to prove the following result: 


Proposition. Every bridgeless cubic graph admits a decomposition into paths of length 3.


Petersen (1891) proved that every bridgeless bipartite graph contains a perfect matching (<http://en.wikipedia.org/wiki/Petersen%27s_theorem>).


Koztig (57) proved that a cubic graph G admits a decomposition into paths of length 3 if and only if G contains a perfect matching. 


