Edge-partitioning cubic graphs into claws and paths

Question

Again an edge-partitioning problem whose complexity I'm curious about, motivated by a previous question of mine.

---

Input: a cubic graph $G=(V,E)$

Question: is there a partition of $E$ into $E_1, E_2, \ldots, E_s$, such that the subgraph induced by each $E_i$ is either a claw (i.e. $K_{1,3}$, often called a star) or a $3$-path (i.e. $P_4$)?

---

I think I saw a paper one day where this problem was proven to be NP-complete, but I cannot find it anymore, and I don't remember whether that result applied to cubic graphs. On a related matter, I'm aware that edge-partitioning a bipartite graph into claws is NP-complete (see Dyer and Frieze). Does anyone have a reference for the problem I describe, or something related (i.e. the same problem on another graph class, that I could then try to reduce to cubic graphs)?

Answer 1

This isn't an answer to the complexity of the problem, but it at least shows that the complexity has a chance at being nontrivial: it's an example of a cubic graph that cannot be partitioned into paths and claws.

_{(source: uci.edu)}

Within each of its three lobes, any partition into paths and claws can only use six of the seven edges. The remaining six central edges take the form of a claw with each edge subdivided, which cannot be partitioned into paths and claws.

ETA: The graph shown above is more famous as an example of a cubic graph without a perfect matching. But every cubic graph with a perfect matching has a decomposition into paths (not even using any claws). By König's theorem this includes all cubic bipartite graphs and by Petersen's theorem this includes all bridgeless cubic graphs, answering a question of Joseph Malkevitch in the comments.

The proof is very simple: if M is a perfect matching in a cubic graph, the removal of M leaves a 2-regular graph, that is, a disjoint union of cycles. Orient each cycle arbitrarily, and attach each edge uv of M to the cycle edges that follow u and v in the orientations of their cycles.

In the other direction, if there exists a decomposition into paths, then there exists a perfect matching: the middle edges of each path must be a matching since no two middle edges can share a degree-three vertex.

(Disclaimer: this idea may have already been present in Carsten Thomassen's invited talk at GD 2010, which was about this sort of graph decomposition problem.)

(addition to disclaimer (by Anthony Labarre): the "orientation idea" for going from a perfect matching to a partition into paths appears in this paper by Jünger, Reinelt and Pulleyblank, who attribute it to W. H. Cunningham.)

Answer 2

It seems I had missed this other paper by Dyer and Frieze, where they prove that partitioning the edges of a planar bipartite graph into connected components with $k$ edges is NP-complete for any fixed $k\geq 3$ (Theorem 3.1 p. 145). They then comment that the problem can be shown to remain NP-complete for $k=3$ if all vertices have degree $2$ or $3$, which unless I parsed this the wrong way includes my problem (since the input is bipartite, the graph contains no odd cycle and in particular no triangle, which means that the only subgraphs we can use are claws and paths).

This wasn't actually the end of the story: if the cubic graph is bipartite, then it's easy to partition its edge set using only claws, by selecting one set of the bipartition and making it a set of "claw centers". The general problem is indeed hard, which can be proved using a reduction from CUBIC PLANAR MONOTONE 1-IN-3 SATISFIABILITY. All details are freely accessible on arxiv.

Answer 3

Perhaps this paper may be of interest:

Kleinschmidt, Peter Regular partitions of regular graphs. Canad. Math. Bull. 21 (1978), no. 2, 177–181.

It deals with graphs which can be written as the union of "Z-paths" of length 3. (Specifically, planar, 3-valent, 3-connected graphs-cubic 3-polytopes.)