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