4

Motivated by this post on cubic graphs decompositions, I am interested in decomposing a connected bridgeless graph into edge-disjoint paths of length 3 (P4). My intuition is that it should be NP-complete but did not find a reduction.

I am aware that it is $NP$-complete to decide whether a cubic bipartite planar graph is decomposable into vertex-disjoint paths of length 2 (P3).

Is it $NP$-complete to decide whether a bridgeless cubic bipartite graph is decomposable into edge-disjoint paths of length 3 (P4)?

In a related note, Barnette conjecture states that every 3-connected cubic bipartite planar graph is Hamiltonian. This is equivalent to decomposing every such graph into Hamiltonian cycle and a perfect matching. Feder and Subi proved that if there is a single graph in the class of the conjecture which does not admit such decomposition then deciding the existence of Hamiltonian cycle in $NP$-complete in that class.

For general connected cubic graph decomposition problems, under which conditions does the existence of a non-decomposable graph imply the $NP$-completeness of the decomposition problem?

EDIT For the second question, Is there a subclass of connected bridgeless cubic graphs where non-decomposable graphs exist but it is polynonial time to decide the existence of a (edge) decomposition?

The linked post on MthOverflow provides some interesting examples of connected cubic graph decomposition problems.

EDIT The problem is posted on MathOverflow: Connection between Barnette conjecture and hardness of cubic graph decomposition

Community
  • 1
Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • Very interesting question...care to share the polynomial time reduction from an NP-complete problem to the bicubic planar graph decomposition problem (for vertex-disjoint paths of length 2)? –  Mar 17 '15 at 16:27
  • @Philip White Here is the reduction http://link.springer.com/chapter/10.1007/11752578_121#page-1 – Mohammad Al-Turkistany Mar 17 '15 at 16:56
  • It's behind a paywall, can you just tell me what problem it's a reduction from? –  Mar 17 '15 at 18:21
  • 1
    @PhilipWhite They proved that perfect P3-matching in cubic bipartite planar 2-connected graphs is NP-complete. The reduction is from 3D matching for planar instances. – Mohammad Al-Turkistany Mar 17 '15 at 18:31
  • For edge decomposition what are the known results? Is it NPC to find an edge disjoint P4 decomposition on cubic bipartite graphs? (i.e. dropping the "bridgless" constraint) – Marzio De Biasi Mar 19 '15 at 11:09
  • @MarzioDeBiasi I am not aware of such result. I know that edge-disjoint claw decomposition of graphs in your class is polynomial time since every such graph has claw decomposition. – Mohammad Al-Turkistany Mar 19 '15 at 11:27
  • @MohammadAl-Turkistany: ok, I thought that if you asked for bridgeless then the problem was known for the more general class. Another trivial question: what is exactly a vertex-disjoint decomposition of a graph in P3 paths? (if you fix the size of the elements used to decompose the graph and ask for a vertex-disjoint decomposition then the problem should be polynomial time solvable) – Marzio De Biasi Mar 19 '15 at 13:39

1 Answers1

5

As pointed out by David Eppstein when I asked a related question a while ago: you can do that in polynomial time.

The idea is to find a perfect matching $M$ (which exists and can be found in polynomial time since your graph is cubic and bridgeless), and then to use the edges of $M$ as middle edges of the $P_4$'s.

To complete the construction, remove the edges of $M$ and orient the remaining cycles arbitrarily. Then attach to each edge $\{u, v\}$ of $M$ the arcs going out from $u$ and $v$, and you are done.

Community
  • 1
Anthony Labarre
  • 3,264
  • 1
  • 25
  • 33
  • From MathOverflow answer, all graphs in the class are decomposable into edge-disjoint paths of length 3 (P4). It would be very interesting to find a class where deciding the decomposition existence is not trivial and polynomial time solvable. – Mohammad Al-Turkistany Mar 20 '15 at 21:35
  • Yes, because all you need is a perfect matching and those graphs are known to admit one. 2) It's actually a necessary and sufficient condition (see again David's original answer).
    • – Anthony Labarre Mar 21 '15 at 09:51