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?

Extendibility problem

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

  • $\begingroup$ Is the original theorem computationally easy? I.e. is it possible to provide that partition at all (in P)? If yes, then provide a reference. $\endgroup$ – Saeed Jun 30 '18 at 22:03
  • 1
    $\begingroup$ @Saeed, purported proof is sketched here. "In a cubic graph with a perfect matching, the edges that are not in the perfect matching form a 2-factor. By orienting the 2-factor, the edges of the perfect matching can be extended to paths of length three, say by taking the outward-oriented edges. This shows that every cubic, bridgeless graph decomposes into edge-disjoint paths of length three." That does seem computationally easy. $\endgroup$ – Neal Young Jul 1 '18 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.