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