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
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.