4
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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)? $\endgroup$
    – user1338
    Mar 17, 2015 at 16:27
  • $\begingroup$ @Philip White Here is the reduction link.springer.com/chapter/10.1007/11752578_121#page-1 $\endgroup$
    – Mohammad Al-Turkistany
    Mar 17, 2015 at 16:56
  • $\begingroup$ It's behind a paywall, can you just tell me what problem it's a reduction from? $\endgroup$
    – user1338
    Mar 17, 2015 at 18:21
  • 1
    $\begingroup$ @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. $\endgroup$
    – Mohammad Al-Turkistany
    Mar 17, 2015 at 18:31
  • $\begingroup$ 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) $\endgroup$
    – Marzio De Biasi
    Mar 19, 2015 at 11:09

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Mohammad Al-Turkistany
    Mar 20, 2015 at 21:35
  • $\begingroup$ 1) 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). $\endgroup$
    – Anthony Labarre
    Mar 21, 2015 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.