4
$\begingroup$

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 transforms 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$

OUTPUT: Is there a partition of the edge set $E$ into edge-disjoint paths $P_4$ that include the input paths

$\endgroup$

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.