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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.