<p><a href="https://mathoverflow.net/questions/267038/complexity-of-extending-p-4-partition-of-cubic-graphs">This is a question</a> I posted on MathOverflow before but never got an answer. I am cross-posting it here.</p>

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

<p>For instance, Konig-Hall theorem states that all cubic bipartite graphs
are 3-edge colorable but the <a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.10088/full" rel="nofollow noreferrer">extendability version becomes $NP$-complete</a> if we are given the colors of some edges.</p>

<p>It is a fact that the edges of any bridgeless cubic graph can be partitioned into edge-disjoint paths $P_4$ (follows from <a href="https://en.wikipedia.org/wiki/Petersen%27s_theorem" rel="nofollow noreferrer">Petersen's theorem</a>). 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.</p>

<blockquote>
  <p>Is this extendibility problem NP-complete? </p>
</blockquote>

<p><strong>Extendibility problem</strong></p>

<p>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$ </p>

<p>QUERY: Is there a partition of the edge set $E$ into edge-disjoint paths $P_4$ that include the input paths</p>

CC BY-SA 4.0
2018-06-30T22:03:00.917Z
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.
Saeed
CC BY-SA 4.0
2018-07-01T02:32:55.193Z
@Saeed, purported proof is sketched [here](https://en.wikipedia.org/wiki/Petersen%27s_theorem#Applications).  "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.
Neal Young
<cc.complexity-theory><graph-theory>
Complexity of extending $P_4 $-partition of cubic graphs
Mohammad Al-Turkistany
# Complexity of extending $P_4 $-partition of cubic graphs

(Asked by: username_0 on 2018-06-30)

[This is a question](https://mathoverflow.net/questions/267038/complexity-of-extending-p-4-partition-of-cubic-graphs) 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](http://onlinelibrary.wiley.com/doi/10.1002/jgt.10088/full) 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](https://en.wikipedia.org/wiki/Petersen%27s_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

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: @username_1, purported proof is sketched [here](https://en.wikipedia.org/wiki/Petersen%27s_theorem#Applications).  "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.  

---

## 0 answers

