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.

$\endgroup$
6
$\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.

$\endgroup$
  • $\begingroup$ thank you. Do you have a link for the second reference? $\endgroup$ – Mohammad Al-Turkistany Mar 20 '15 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 Mar 20 '15 at 15:04
  • $\begingroup$ Yes, I believe this is the correct paper. $\endgroup$ – Fabio Botler Mar 21 '15 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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