2
$\begingroup$

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

Barnette's 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.

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

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

For general connected cubic graph decomposition problems, under which conditions does the existence of a non-decomposable graph (in some class) imply the $NP$-completeness of the decomposition decision problem? Is there a subclass of connected bridgeless cubic graphs where a non-decomposable graphs exist but it is polynomial time to decide the existence of a (edge) decomposition?

The decomposition decision problem should be non-trivial.

(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))

The problem was posted on TCS SE.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

It is easy to prove the following result:

Proposition. Every bridgeless cubic graph admits a decomposition into paths of length 3.

Petersen (1891) proved that every bridgeless bipartite graph contains a perfect matching (http://en.wikipedia.org/wiki/Petersen%27s_theorem).

Koztig (57) proved that a cubic graph G admits a decomposition into paths of length 3 if and only if G contains a perfect matching.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thank you. Do you have a link for the second reference? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Mar 20, 2015 at 6:26
  • $\begingroup$ Has to be this: @article {MR0090815, AUTHOR = {Kotzig, Anton}, TITLE = {Aus der {T}heorie der endlichen regul\"aren {G}raphen dritten und vierten {G}rades}, JOURNAL = {\v Casopis P\v est. Mat.}, FJOURNAL = {\v Ceskoslovensk\'a Akademie V\v ed. \v Casopis Pro P\v estov\'an\'\i\ Matematiky}, VOLUME = {82}, YEAR = {1957}, PAGES = {76--92}, ISSN = {0528-2195}, MRCLASS = {55.0X}, MRNUMBER = {0090815 (19,876c)}, MRREVIEWER = {M. Fiedler}, } $\endgroup$
    – Flo Pfender
    Commented Mar 20, 2015 at 15:04
  • $\begingroup$ Yes, I believe this is the correct paper. $\endgroup$
    – Fabio Botler
    Commented Mar 21, 2015 at 0:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .