This is a question I posted on MathOverflow before but never got an answer. I am cross-posting it here.
Surprising phenomena occurs when we want to extend a partial solution of some easy problems. We are given part of the solution and we want to decide whether we can extend it to a complete solution. Extendability problem can transform an easy problem to hard one.
For instance, Konig-Hall theorem states that all cubic bipartite graphs are 3-edge colorable but the extendability version becomes $NP$-complete if we are given the colors of some edges.
It is a fact that the edges of any bridgeless cubic graph can be partitioned into edge-disjoint paths $P_4$ (follows from Petersen's theorem). Given a set of paths $P_4$ (of three edges), I suspect that it is hard to decide the existence of edge partition into $P_4$ paths that include the given paths.
Is this extendibility problem NP-complete?
INPUT: Bridgeless cubic graph $G(V,E)$ and set of paths $P_4=(e_i,e_j,e_k)$ where $e_i,e_j,e_k \in E$
QUERY: Is there a partition of the edge set $E$ into edge-disjoint paths $P_4$ that include the input paths