# The complexity of P4-decomposition of regular graphs and multigraphs

Ajit Diwan, Justine Dion, David Mendell, Michael Plantholt, Shailesh Tipnis

► To cite this version:

Ajit Diwan, Justine Dion, David Mendell, Michael Plantholt, Shailesh Tipnis. The complexity of P4-decomposition of regular graphs and multigraphs. Discrete Mathematics and Theoretical Computer Science, 2015, Vol. 17 no.2 (2), pp.63-76. 10.46298/dmtcs.2128. hal-01349042

HAL Id: hal-01349042

https://inria.hal.science/hal-01349042

Submitted on 26 Jul 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The complexity of $P_4$-decomposition of regular graphs and multigraphs

Ajit A. Diwan<fnref n="1" />*

Justine E. Dion<fnref n="2" />†

David J. Mendell<fnref n="2" />‡

Michael J. Plantholt<fnref n="2" />§

Shailesh K. Tipnis<fnref n="2" />¶

received 27th Aug. 2014, revised 15th May 2015, accepted 25th Aug. 2015.

Let $G$ denote a multigraph with edge set $E(G)$, let $\mu(G)$ denote the maximum edge multiplicity in $G$, and let $P_k$ denote the path on $k$ vertices. Heinrich et al. (1999) showed that $P_4$ decomposes a connected 4-regular graph $G$ if and only if $|E(G)|$ is divisible by 3. We show that $P_4$ decomposes a connected 4-regular multigraph $G$ with $\mu(G) \le 2$ if and only if no 3 vertices of $G$ induce more than 4 edges and $|E(G)|$ is divisible by 3. Oksimets (2003) proved that for all integers $k \ge 3$, $P_4$ decomposes a connected 2k-regular graph $G$ if and only if $|E(G)|$ is divisible by 3. We prove that for all integers $k \ge 2$, the problem of determining if $P_4$ decomposes a (2k + 1)-regular graph is NP-Complete. El-Zanati et al. (2014) showed that for all integers $k \ge 1$, every 6k-regular multigraph with $\mu(G) \le 2k$ has a $P_4$-decomposition. We show that unless $P = \text{NP}$, this result is best possible with respect to $\mu(G)$ by proving that for all integers $k \ge 3$ the problem of determining if $P_4$ decomposes a 2k-regular multigraph with $\mu(G) \le \lfloor \frac{2k}{3} \rfloor + 1$ is NP-Complete.

**Keywords:** $P_4$-decomposition, multigraphs, NP-complete

## 1 Introduction

For integers $i$ and $j$ with $i \le j$, let $[i, j]$ denote the set $\{i, i+1, \dots, j\}$. A graph has no multiple edges or loops while a multigraph is allowed to have multiple edges but has no loops. Let $G$ be a multigraph with vertex set $V(G)$ and edge set $E(G)$. The multiplicity of an edge $(u, v) \in E(G)$ is defined to be the number of edges joining $u$ and $v$ and is denoted by $\mu(uv, G)$ and the maximum edge-multiplicity of $G$ is denoted by $\mu(G)$. We denote by $\lambda G$ the multigraph obtained from $G$ by replacing each edge of $G$ by $\lambda$ parallel edges. A path consisting of 3 edges $(x, y), (y, z)$, and $(z, w)$ is denoted by $P_4$ and the edge $(y, z)$ is called the central edge of $P_4$. A decomposition of a multigraph $G$ is a partition of its edge set into

<footnote n="1">¹Department of Computer Science and Engineering, Indian Institute of Technology, Mumbai, India</footnote>

<footnote n="2">²Department of Mathematics, Illinois State University, USA</footnote>

<footnote>*Email: aad@cse.iitb.ac.in</footnote>

<footnote>†Email: jlessen@ilstu.edu</footnote>

<footnote>‡Email: djmende@ilstu.edu</footnote>

<footnote>§Email: mikep@ilstu.edu</footnote>

<footnote>¶Email: tipnis@ilstu.edu</footnote>
edge disjoint subgraphs $H_1, H_2, \dots, H_k$ of $G$; if each $H_i$, $i \in [1, k]$ is isomorphic to a graph $H$ then we have an *H-decomposition* of $G$ and we say that *H decomposes G*. It is well known that every connected multigraph $G$ with the degree of each of its vertices being even has an Euler tour; we say that such a multigraph is *Eulerian*. We will denote an Euler tour in $G$ by the sequence of vertices visited by the tour. An Euler tour in a multigraph $G$ is said to be a *triangle-free Euler tour* if no three consecutive edges in the Euler tour form a triangle in $G$. A $(C_2, C_3)$-free Euler tour in a multigraph $G$ is a triangle-free Euler tour in which no two consecutive edges are a parallel pair in $G$.

We refer the reader to [2] for all terminology and notation that is not defined in this paper.

The following conjecture by Graham and Häggkvist [8] is the genesis of much of what we discuss in this paper.

**Conjecture 1** [8] Every tree on *m* edges decomposes every 2*m*-regular graph.

In [8] Häggkvist described a method to prove the above conjecture for $m = 3$, i.e. that $P_4$ decomposes every 6-regular graph. M. Kouider and Z. Lonc [11] obtained a generalization of this result by showing that any path on $m$ edges decomposes every 2*m*-regular graph $G$ of girth $g$ with $m \le 2g - 3$.

The following theorem independently due to Kotzig [10] and Bouchet and Fouquet [3] gives a necessary and sufficient condition for a cubic graph to have a $P_4$-decomposition.

**Theorem 1** [3] A cubic graph $G$ has a $P_4$-decomposition if and only if $G$ has a 1-factor.

Heinrich et al. [9] proved the following theorem as a corollary of a theorem on triangle-free Euler tours in connected 4-regular graphs.

**Theorem 2** [9] A connected 4-regular graph $G$ has a $P_4$-decomposition if and only if $|E(G)|$ is divisible by 3.

In Section 2 of this paper we extend Theorem 2 by proving that a connected 4-regular multigraph $G$ with $\mu(G) \le 2$ has a $P_4$-decomposition if and only if no 3 vertices of $G$ induce more than 4 edges and $|E(G)|$ is divisible by 3.

Bondy [1] proved that if we double the edges of a cubic graph then $P_4$ decomposes the resulting multigraph.

**Theorem 3** [1] Let $G$ be a cubic graph. Then $^2G$ has a $P_4$-decomposition.

The following generalization of Theorem 3 was obtained in [6].

**Theorem 4** [6] Every 6-regular multigraph with $\mu(G) \le 2$ has a $P_4$-decomposition.

Theorem 4 was further generalized to multigraphs with higher multiplicity in [6].

**Theorem 5** [6] For all integers $k \ge 1$, every $6k$-regular multigraph $G$ with $\mu(G) \le 2k$ has a $P_4$-decomposition.

In section 3 of this paper we prove the NP-Completeness of some $P_4$-decomposition problems. Dor and Tarsi [5] proved the following classic NP-Completeness theorem about decompositions of graphs

**Theorem 6** [5] For a fixed graph $H$ that has at least one component with at least 3 edges, the problem of determining if there exists an $H$-decomposition of an arbitrary graph $G$ is NP-Complete.

Bryś and Lonc [4] proved that if every component of $H$ has at most 2 edges, then there is a polynomial time algorithm to determine if a graph $G$ has an $H$-decomposition.
**Theorem 7** [4] For a fixed graph $H$ with each component having at most 2 edges, the problem of determining if there exists an $H$-decomposition of an arbitrary graph $G$ can be solved in polynomial time.

Theorem 6 implies that the problem of determining if $P_4$ decomposes an arbitrary graph $G$ is NP-Complete. Teypaz and Rapine [13] proved that this remains true even under the restricted case where $G$ is bipartite.

**Theorem 8** [13] The problem of determining if there exists a $P_4$-decomposition of an arbitrary bipartite graph $G$ is NP-Complete.

Oksimets [12] obtained the following theorem as a corollary of a result on triangle-free Euler tours in even-regular graphs.

**Theorem 9** [12] For all integers $k \ge 3$, every connected $2k$-regular graph $G$ with $|E(G)|$ being divisible by 3 has a $P_4$-decomposition.

In section 3 of this paper we use a construction similar to the one used in the proof of Theorem 8 to prove that for all integers $k \ge 2$, the problem of determining if $P_4$ decomposes a $(2k+1)$-regular graph is NP-Complete. We also prove that for all integers $k \ge 3$, the problem of determining if $P_4$ decomposes a $2k$-regular multigraph $G$ with $\mu(G) \le \lfloor \frac{2k}{3} \rfloor + 1$ is NP-Complete. This shows that with respect to the maximum multiplicity of the multigraph, unless $P = \text{NP}$, Theorems 4 and 5 are best possible. In particular, in contrast to Theorem 4, this shows that the problem of determining if $P_4$ decomposes a $6$-regular multigraph with maximum multiplicity 3 is NP-Complete.

## 2 $P_4$-decomposition of 4-regular multigraphs of maximum multiplicity 2

A (2,4)-multigraph is a multigraph whose vertices have degree 2 or 4. Let $\mathcal{G}$ be the family of connected (2,4)-graphs shown in Figure 1 where $H$ is any graph with appropriate degrees. Heinrich et al.[9] proved that the graphs in $\mathcal{G}$ are the only connected (2,4)-graphs that do not admit a triangle-free Euler tour.

**Theorem 10** [9] A connected (2,4)-graph $G$ admits a triangle-free Euler tour if and only if $G \notin \mathcal{G}$.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Family $\mathcal{G}$ of (2,4)-graphs with no triangle-free Euler tour.</figcaption></figure>

Clearly, if $G \notin \mathcal{G}$ is a connected, (2,4)-graph with $|E(G)|$ divisible by 3 then we can obtain a $P_4$-decomposition of $G$ by properly segmenting a triangle-free Euler tour in $G$. More significantly, Heinrich et al. [9] proved Theorem 2 mentioned in the Introduction as a consequence of Theorem 10.

We now prove extensions of these results by Heinrich et al. [9] to multigraphs $G$ with $\mu(G) \le 2$. Let $\mathcal{F}$ be
the family of connected (2,4)-multigraphs shown in Figure 2 where $H$ is any multigraph with appropriate degrees.

**Theorem 11** A connected (2,4)-multigraph $G$ with $\mu(G) \le 2$ admits a $(C_2, C_3)$-free Euler tour if and only if $G \notin \mathcal{F}$.

**Proof:** If $G \in \mathcal{F}$, it is easy to check that $G$ does not admit a $(C_2, C_3)$-free Euler tour. Let $G \notin \mathcal{F}$ be a connected (2,4)-multigraph with $\mu(G) \le 2$ and let $p(G)$ be the number of parallel edge pairs in $G$. We prove the theorem by induction on $p(G)$. The base case $p(G) = 0$ follows from Theorem 10 because in that case $G$ has no multiple edges and the family $\mathcal{G}$ of graphs in Figure 1 is contained in the family $\mathcal{F}$ in Figure 2. Suppose inductively that the theorem is true for $0 \le p(G) \le k$. Let $G \notin \mathcal{F}$ be a connected (2,4)-multigraph with $\mu(G) \le 2$ and $p(G) = k+1$.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Family $\mathcal{F}$ of multigraphs with no $(C_2, C_3)$-free Euler tour.</figcaption></figure>

Let $u$ and $v$ be adjacent vertices of $G$ with $\mu(u, v) = 2$, and let $G^*$ be the graph obtained from $G$ by subdividing one of the edges $(u, v)$ by inserting a new vertex $w$. Clearly, $G^*$ is a connected (2,4)-multigraph with $p(G^*) = k$. We claim that $G^* \notin \mathcal{F}$. If $G^* \in \mathcal{F}$ then the inserted vertex $w$ of degree two must be a depicted vertex of one of the multigraphs in Figure 2. But note that the multigraph obtained
by deleting any depicted vertex $x$ of degree two from any of the multigraphs in Figure 2 and joining the neighbors of $x$ by an edge results in a multigraph in $\mathcal{F}$ or an edge of multiplicity three or a loop. For example, performing this operation on the multigraph XIII in Figure 2 results in multigraph X. Hence, since $G \notin \mathcal{F}$, we have that $G^* \notin \mathcal{F}$ as claimed.

By the induction hypothesis we have that $G^*$ has $(C_2, C_3)$-free Euler tour $E^*$ and we may assume without loss of generality that $u, w, v$ is a subsequence of $E^*$. Let $E$ be the Euler tour of $G$ obtained from $E^*$ by replacing its subsequence $u, w, v$ by $u, v$. Since $E^*$ is $(C_2, C_3)$-free, $E$ is $C_2$-free and we are done if in addition $E$ is $C_3$-free. So, assume that some 3 consecutive vertices in $E$ form a triangle in $G$ which must clearly contain the edge $(u, v)$ and hence we can assume that $E$ starts with the subsequence $u, v, t, u$ for some vertex $t \neq u, v$. Because $E$ is $C_2$-free, it cannot end with the subsequence $v, u$, and hence we can further assume that $E$ starts with the subsequence $u, v, t, u, v$. But then, $E^*$ must contain either the subsequence $u, w, v, t, u, v$ or $u, v, t, u, w, v$. In either case, this implies that $E^*$ contains a $C_3$-subsequence which is a contradiction. The result follows. $\square$

**Theorem 11** directly yields the corollary below by appropriately segmenting a $(C_2, C_3)$-free Euler tour into 3-edge segments.

**Corollary 1** Let $G$ be a connected (2,4)-multigraph with $\mu(G) \le 2$. If $G \notin \mathcal{F}$ and $|E(G)|$ is divisible by 3 then $G$ admits a $P_4$ decomposition.

We are now ready to prove the main result of this section.

**Theorem 12** A connected 4-regular multigraph $G$ with $\mu(G) \le 2$ admits a $P_4$ decomposition if and only if no 3 vertices of $G$ induce more than 4 edges and $|E(G)|$ is divisible by 3.

**Proof:** Clearly, if $G$ has a $P_4$-decomposition then $|E(G)|$ is divisible by 3 and no three vertices of $G$ induce more than 4 edges.

Let $G$ be a connected 4-regular multigraph with $\mu(G) \le 2$, with $|E(G)|$ divisible by 3, and such that no three vertices of $G$ induce more than 4 edges. If $G \notin \mathcal{F}$, the result follows from Corollary 1. So assume $G \in \mathcal{F}$. Clearly, $G$ must be a type IX, X, or XIV graph (and perhaps, all three) in $\mathcal{F}$.

We will construct from $G$ a connected (2,4)-multigraph $G^* \notin \mathcal{F}$ and with $|E(G^*)|$ divisible by 3. Theorem 11 will then imply that $G^*$ admits a $(C_2, C_3)$-free Euler tour, and hence a $P_4$ decomposition. We will then show how this $P_4$ decomposition of $G^*$ yields a $P_4$ decomposition of $G$.

We construct $G^*$ by replacing the subgraph induced by the 4 vertices shown in Figure 2 in type IX or type X structures in $G$ by paths of length 4, and, the subgraph induced by the 5 vertices shown in Figure 2 in type XIV structures in $G$ by paths of length 3. Note that the lengths of these paths mod 3 is equal to the number of edges mod 3 in the induced subgraphs that they replace.

Clearly, $G^* \notin \mathcal{F}$ is a connected (2,4)-multigraph with $\mu(G^*) \le 2$, and $|E(G^*)|$ divisible by 3, and hence by Theorem 11 has a $(C_2, C_3)$-free Euler tour, $T^*$. We now use $T^*$ to construct an Euler tour, $T$, in $G$ which will provide a $P_4$-decomposition of $G$.

Begin by traversing $T^*$ until the next vertex to be reached is contained in a replacement path. Let $m$ be the number of edges traversed until now reduced modulo 3. Remove the replacement path added in the construction of $G^*$, and reinstate the original induced subgraph on 4 or 5 vertices that was replaced by it. In Figures 3, 4, and 5, the directions in which these edges should be traversed are indicated with arrows, and the order in which the edges are to be traversed have been indicated by labels that occur in sets of
three, which also indicate which edges will be partitioned together in the final $P_4$-decomposition of $G$. Note that we lose no generality by assuming that the reinstated subgraph is entered from the left-hand side in Figures 3, 4, and 5. Even in the case of a type IX graph in $\mathcal{F}$, which is not strictly symmetric, it is easy to confirm a symmetry between the labelings given in Figures 3(a), (b), and (c), 4(a), (b), and (c), and 5(a), (b), and (c). For each reinstated subgraph, the labeling of the edges chosen depends on $m$, as well as the type of structure replaced. If $m$ is equivalent to 0 modulo 3, the labeling is given by Figure 3(a), 4(a), or 5(a), if $m$ is equivalent to 1 modulo 3, the labeling is given by Figure 3(b), 4(b), or 5(b), and, if $m$ is equivalent to 2 modulo 3, the labeling is given by Figure 3(c), 4(c), or 5(c). Note that in all cases, no edges with equal labels induce a $C_3$ or a $C_2$.

<figure><img src="image_4.png" /><figcaption>Fig. 3: Labelings for type IX subgraphs being reinstated.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4: Labelings for type X subgraphs being reinstated.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Fig. 5: Labelings for type XIV subgraphs being reinstated.</figcaption></figure>

Continue traversing the edges of $T^*$ after leaving the reinstated subgraph and iterate this process until all subgraphs that were replaced by paths when $G^*$ was constructed have been reinstated, and all edges of $G$ have been traversed.

This completes the construction of $T$, which is not necessarily $(C_2, C_3)$-free but such that for $i \in [1, |E(G)|]$ if we label the $i$-th edge encountered in $T$ by $e_i$, then the edges $e_{3j-2}, e_{3j-1}, e_{3j}$ form a $P_4$ for $j \in [1, \lfloor \frac{|E(G)|}{3} \rfloor]$, thus providing a $P_4$-decomposition of $G$. $\square$

### 3 NP-Completeness of some regular graph/multigraph decomposition problems

For an integer $m \ge 3$, **X3C**($m$) is the following exact 3-cover problem.

**X3C**($m$)

**Given:** A finite ground set $X$ and a collection of subsets $S = \{S_i\}_{i=1}^k$ of $X$ with $|S_i| = 3$ for each $i \in [1, k]$ and each element of $X$ contained in exactly $m$ sets in $S$.

**Question:** Is there a subcollection $Q \subseteq S$ such that each element of $X$ is contained in exactly one set in $Q$?

If for some instance I of **X3C**($m$), the subcollection $Q$ in the above question exists, we say that I has an exact cover consisting of $Q$.

Gonzalez [7] proved that Exact 3-cover is NP-complete if each element of the ground set is contained in exactly 3 subsets.

**Theorem 13** [7] **X3C**($3$) is NP-complete.

We first prove the following more general form of Theorem 13.

**Theorem 14** For every integer $m \ge 3$, **X3C**($m$) is NP-complete.
**Proof:** Clearly, the problem is in NP. Theorem 13 verifies the case $m = 3$. Suppose we have an instance I of $\mathbf{X3C}(n)$ with ground set $X$ and a collection of subsets $S$ of $X$, for some integer $n \ge 3$. We will construct an instance I' of $\mathbf{X3C}(n+1)$ with ground set $X'$ and a collection of subsets $S'$ of $X'$ such that I has an exact cover if and only if I' has an exact cover.

Without loss of generality suppose that $|X| = 3q$, otherwise trivially, no exact cover exists for instance I. Partition the elements in $X$ arbitrarily into $q$ sets $X_s = \{x_1^{(s)}, x_2^{(s)}, x_3^{(s)}\}$, for each $s \in [1, q]$. Let $X' = X \cup (\cup_{s=1}^q \{a_1^{(s)}, a_2^{(s)}, \dots, a_{3(n+1)}^{(s)}\})$, where $a_i^{(s)}$ is a new element not contained in $X$ for each $i \in [1, 3(n+1)]$ and $s \in [1, q]$. The collection of subsets $S'$ of $X'$ is better described by first constructing a collection of subsets $S''$ and then amending $S''$ to get $S'$. Let $S'' = S \cup (\cup_{s=1}^q \{\{a_{3i+1}^{(s)}, a_{3i+2}^{(s)}, a_{3j+3}^{(s)}\} : 0 \le i, j \le n\})$. Note that for each $i \in [1, 3(n+1)]$ and $s \in [1, q]$, $a_i^{(s)}$ is contained in exactly $(n+1)$ subsets of $S''$. Now, to construct the collection of subsets $S'$ we amend $S''$ as follows: Delete the $3q$ sets $\{a_{3n+1}^{(s)}, a_{3n+2}^{(s)}, a_{3j+3}^{(s)}\}$ for each $0 \le j < 3$ and each $s \in [1, q]$, add the sets $\{a_3^{(s)}, a_6^{(s)}, a_9^{(s)}\}$ for each $s \in [1, q]$, and, replace the element $a_{3n+3}^{(s)}$ in the sets $\{a_{3i+1}^{(s)}, a_{3i+2}^{(s)}, a_{3n+3}^{(s)}\}$ for $0 \le i < 3$ by the element $a_{3n+1}^{(s)}$ for each $s \in [1, q]$. Now all new elements except $a_{3n+2}^{(s)}$ and $a_{3n+3}^{(s)}$ for each $s \in [1, q]$ are contained in $(n+1)$ sets and these are contained in exactly $(n-2)$ sets. Finally, add the sets $\{x_i^{(s)}, a_{3n+2}^{(s)}, a_{3n+3}^{(s)}\}$ for each $i \in [1, 3]$ and each $s \in [1, q]$. We now have the collection of subsets $S'$ of $X'$ of cardinality $3$ each and such that each element of $X'$ is contained in exactly $(n+1)$ sets in $S'$. Now if I has an exact cover $Q$ then $Q' = Q \cup (\cup_{s=1}^q \{\{a_{3i+1}^{(s)}, a_{3i+2}^{(s)}, a_{3i+3}^{(s)}\} : i \in [0, n]\})$ is an exact cover for I'. Conversely, if $Q'$ is an exact cover of I', then no set of the form $\{x_i^{(s)}, a_{3n+2}^{(s)}, a_{3n+3}^{(s)}\}$ for $i \in [1, 3]$ and $s \in [1, q]$ can be $Q'$, since if so, it is impossible to cover the elements $a_i^{(s)}$ for $i \in [1, 3(n+1)] \setminus \{3n+2, 3(n+1)\}$ and $s \in [1, q]$. Hence, in I', the elements of the ground set $X$ of I must be covered by sets in $S$ which gives an exact cover for I. $\square$

We now use Theorem 13 to prove that the problem of determining if $P_4$ decomposes a 5-regular graph is NP-complete, and point out that Theorem 14 can be used to prove more generally that for all integers $k \ge 2$, the problem of determining if $P_4$ decomposes a $(2k+1)$-regular graph is NP-complete.

**Theorem 15** *Given a 5-regular graph $G$, the problem of determining if $P_4$ decomposes $G$ is NP-Complete.*

**Proof:** Clearly the problem is in NP. We will prove the theorem by reduction from the NP-Complete problem **X3C(3)**. Consider an arbitrary instance I of **X3C(3)** with ground set $X$ and a collection of subsets $S = \{S_i\}_{i=1}^k$ of $X$ with $|S_i| = 3$ for each $i \in [1, k]$ and each element of $X$ contained in exactly 3 sets in $S$. Without loss of generality assume that $|X| = |S| = 3q$ and let $X = \{x_1, x_2, \dots, x_{3q}\}$. We will construct a 5-regular graph $G$ such that $P_4$ decomposes $G$ if and only if I has an exact cover. For each element $x_i \in X$, we have a vertex $v_i \in V(G)$, $i \in [1, 3q]$. For each set $S_i \in S$, we will construct a *set-gadget* graph $G_i$, $i \in [1, 3q]$. If $S_i = \{x_j, x_k, x_l\}$ then $G_i$ has 3 vertices $w_j^{(i)}, w_k^{(i)}$, and $w_l^{(i)}$ of degree 4 each and 6 vertices $a_i, b_i, c_i, d_i, e_i$, and $f_i$ of degree 5 each, so that $|E(G_i)| = 21 = 0 \pmod 3$. In addition we choose $G_i$ and $G_i \setminus T$ to be $P_4$-decomposable, where $T$ is a set of 6 edges consisting of edge-disjoint paths of length 2 starting at each of the 3 vertices of degree 4. Figure 6 shows an example of $G_i$ with these properties. The letters by the edges indicate a $P_4$-decomposition of the gadget. Also note that if you remove the edges $(w_j^i, d_i)$, $(d_i, b_i)$, $(w_k^i, f_i)$, $(f_i, d_i)$, $(w_l^i, a_i)$, and $(a_i, d_i)$ the letters on the edges continue to indicate a $P_4$-decomposition of the remaining edges
<figure><img src="image_7.png" /><figcaption>Fig. 6: Set gadget graph $G_i$ for set $S_i = \{x_j, x_k, x_l\}$</figcaption></figure>

In $G$, if $x_i \in S_j$, vertex $v_i$ is joined to vertices $w_i^{(j)}$, for each $i, j \in [1, 3q]$. For each element $x_i \in X$, we construct two disjoint copies $H_i^{(1)}, H_i^{(2)}$ of an element-gadget graph, $i \in [1, 3q]$. For $j = 1$ and $2$, graph $H_i^{(j)}$ has one vertex $u_i^{(j)}$ of degree 4 and 8 vertices of degree 5, so that $|E(H_i^{(j)})| = 22 = 1$ (mod 3). In addition, we choose $H_i^{(j)}$ such that $H_i^{(j)}$-e is $P_4$ decomposable, where e is an edge incident on the vertex of degree 4. Figure 7 shows an example of $H_1^1$ with these properties. The letters to the right or above the edges indicate a $P_4$-decomposition of the gadget with the exception of one edge incident on the vertex of degree 4. In $G$, for each $i \in [1, 3q]$, vertex $v_i$ is joined by an edge to vertices $u_i^{(1)}$ and $u_i^{(2)}$. This completes the construction of the graph $G$.

Suppose that the instance I of **X3C(3)** has an exact cover **Q**. If for $i \in [1, 3q]$ set $S_i = \{x_j, x_k, x_l\} \in \mathcal{Q}$, we use 3 edge-disjoint paths of length 2 in $G_i$ starting at $w_j^{(i)}$, $w_k^{(i)}$ and $w_l^{(i)}$ together with the edges $v_j w_j^{(i)}$, $v_k w_k^{(i)}$ and $v_l w_l^{(i)}$ that are external to $G_i$ as 3 $P_4$ s in a decomposition of $G$. The rest of the 15 edges in $G_i$ decompose internally into $P_4$ s. For $S_i \not\in \mathcal{Q}$ we decompose all the 21 edges in $G_i$ internally into $P_4$ s. Since $\mathcal{Q}$ is an exact cover of I, for each $i \in [1, 3q]$, this leaves uncovered exactly 2 edges joining $v_i$ to vertices corresponding to 2 sets in $S \setminus \mathcal{Q}$. We use these 2 uncovered edges together with the edges $v_i u_i^{(1)}$, $v_i u_i^{(2)}$ and two internal edges in $H_i^{(1)}$ and $H_i^{(2)}$ incident on $u_i^{(1)}$ and $u_i^{(2)}$ as 2 $P_4$ s in the decomposition of $G$. The remaining 21 edges in each of $H_i^{(1)}$ and $H_i^{(2)}$ decompose internally into $P_4$ s for each $i \in [1, 3q]$.

Conversely suppose that $G$ has a $P_4$-decomposition. For $i \in [1, 3q]$, the $P_4$ s that are internal to $H_i^{(1)}$ and $H_i^{(2)}$ in the decomposition leave exactly one internal edge uncovered incident on each of $u_i^{(1)}$ and $u_i^{(2)}$. In any $P_4$-decomposition of $G$ these uncovered edges must be covered by $P_4$ s that include the
<figure><img src="image_8.png" /><figcaption>Fig. 7: Element gadget $H_i^1$ for element $x_i$</figcaption></figure>

edges $u_i^{(1)}v_i$ and $u_i^{(2)}v_i$ together with 2 edges joining $v_i$ to corresponding vertices $w_i^{(j)}$ and $w_i^{(k)}$ for some $j, k \in [1, 3q]$. For each $i \in [1, 3q]$, this leaves exactly one edge incident on $v_i$ uncovered that joins $v_i$ to a corresponding vertex $w_i^{(l)}$ for some $l \in [1, 3q]$.

For each $i \in [1, 3q]$, let $X_i = \{v_j w_j^{(i)}, v_k w_k^{(i)}, v_l w_l^{(i)}\}$ be the set of edges that have exactly one endpoint in $V(G_i)$. We claim that in any $P_4$-decomposition of $G$, for each $i \in [1, 3q]$ the $P_4$ s that cover the edges in $G_i$ include all three or none of the edges in $X_i$. To see this, note that if exactly one of the edges in $X_i$ is included in the $P_4$ s that cover the edges in $G_i$, then that edge must be in a $P_4$ that includes 2 edges in $E(G_i)$ and that leaves the remaining 19 edges in $E(G_i)$ to be covered internally, which is impossible. If exactly two of the edges in $X_i$ are included in the $P_4$ s that cover the edges in $G_i$, then, clearly, this leaves either 17 or 20 edges in $E(G_i)$ to be covered internally, which is impossible.

Now, it is easy to see that the sets corresponding to those set-gadget graphs $G_i$, $i \in [1, 3q]$, for which the $P_4$ s that cover the edges in $G_i$ include all three edges in $X_i$ form an exact cover of $I$. $\square$

We point out that by using the more general Theorem 14, a proof similar to that of Theorem 15 yields the NP-Completeness of the problem of determining if a $(2k + 1)$-regular graph has a $P_4$-decomposition for all $k \ge 2$.

**Theorem 16** For all $k \ge 2$, given a $(2k + 1)$-regular graph $G$, the problem of determining if $P_4$ decomposes $G$ is NP-Complete.

**Proof:** Clearly the problem is in NP. Theorem 14 gives that $\mathbf{X3C}(k+1)$ is NP-Complete for all $k \ge 2$. We prove the theorem by reduction from $\mathbf{X3C}(k+1)$ for $k \ge 2$. Given an arbitrary instance $I$ of $\mathbf{X3C}(k+1)$ for $k \ge 2$, we will only describe the set-gadget graphs, the element-gadget graphs, and the graph $G$ which
is $(2k+1)$-regular and such that I has an exact cover if and only if $P_4$ decomposes $G$. As in the proof of Theorem 15 we have a set-gadget graph for each subset of the ground set. The set-gadget graph $G_i$ has 3 vertices of degree $2k$ each, all other vertices of $G_i$ have degree $(2k+1)$ each, $|E(G_i)| = 0 \pmod 3$, $G_i$ is $P_4$ decomposable, and $G_i \setminus T$ is decomposable where $T$ is a set of 6 edges consisting of edge-disjoint paths of length 2 starting at each of the 3 vertices of degree $2k$. Corresponding to each element $x_i$ of the ground set we have a vertex $v_i$ and $k$ copies of an element gadget graph $H_i^{(j)}$, $j \in [1, k]$. Each element-gadget graph $H_i^{(j)}$ has one vertex of degree $2k$, all other vertices of $H_i^{(j)}$ have degree $(2k+1)$ each, $|E(H_i^{(j)})| = 1 \pmod 3$, and $H_i^{(j)}$ - $e$ is $P_4$ decomposable, where $e$ is an edge incident on the vertex of degree $2k$. For each element $x_i$ in the ground set, the corresponding vertex $v_i$ is joined to the $k$ vertices of degree $2k$ in each of the associated element-gadget graphs $H_i^{(j)}$, $j \in [1, k]$, and $v_i$ is joined to one of the 3 vertices of degree $2k$ in each of the associated set-gadget graphs that correspond to the $(k+1)$ subsets that contain $x_i$. Now, an argument similar to that in the proof of Theorem 15 shows that I has an exact cover if and only if $P_4$ decomposes $G$. $\square$

We will now use Theorem 16 to prove the NP-Completeness of the problem of determining if $P_4$ decomposes certain regular multigraphs.

**Theorem 17** For all integers $k \ge 1$, the problem of determining if $P_4$ decomposes a $6k$-regular multigraph $G$ with $\mu(G) \le (2k+1)$ is NP-Complete.

**Proof:** Clearly, the problem is in NP. Theorem 16 gives that the problem of determining if $P_4$ decomposes a $(6k-1)$-regular graph is NP-Complete for all integers $k \ge 1$. We will prove our theorem by reduction from this NP-Complete problem.

For $k \ge 1$, given a $(6k-1)$-regular graph $G$, we will construct a $6k$-regular multigraph $G'$ with $\mu(G') \le (2k+1)$ such that $P_4$ decomposes $G$ if and only if $P_4$ decomposes $G'$. If $|V(G)| = n$, we will use $n$ copies of the following gadget graph $H$ in our construction of $G'$. To construct the gadget $H$, take 3 disjoint cliques $Q_1, Q_2$, and $Q_3$ on $2k$ vertices each and remove a perfect matching from $Q_1$ and $Q_2$. Add $2k$ disjoint triangles, each containing one vertex from each of the 3 cliques. The edges of these triangles joining a vertex in $Q_1$ to a vertex in $Q_2$ have multiplicity $(2k+1)$, and all other edges of these triangles have multiplicity $2k$. This completes the construction of the gadget graph $H$ which is $(6k-1)$-regular and has $\mu(H) \le (2k+1)$. In the construction of $G'$ we will add one edge between each vertex of a copy of $H$ and the rest of $G'$.

Now, given a $(6k-1)$-regular graph $G$ on $n$ vertices $v_i$, $i \in [1, n]$, make $6k$ disjoint copies $G_i$, $i \in [1, 6k]$ of $G$, and $n$ disjoint copies $H_i$, $i \in [1, n]$ of $H$. Join each vertex of $H_i$ to a different copy of $v_i \in \bigcup_{j=1}^{6k} V(G_j)$ for $i \in [1, n]$. This completes the construction of the graph $G'$.

Suppose $P_4$ decomposes $G$. We decompose each $G_i$, $i \in [1, 6k]$ separately. It is easy to check that each $H_i$, $i \in [1, n]$ together with the $6k$ edges between a vertex of $H_i$ and a vertex not in $V(H_i)$ can be decomposed into $P_4$ s separately. This yields a $P_4$-decomposition of $G'$.

Conversely, suppose $P_4$ decomposes $G'$. We claim that the edges in each $H_i$, $i \in [1, n]$ together with the $6k$ edges between a vertex of $H_i$ and a vertex not in $V(H_i)$ must be decomposed into $P_4$ s without using any other edges. To prove this claim note that the total number of edges contained in the $2k$ disjoint triangles added to the 3 cliques in $H_i$ is $(2k)(6k+1)$. Any $P_4$ can contain at most 2 edges from these triangles and hence in any decomposition of $G'$ there are at least $(k)(6k+1) = (6k^2 + k) P_4$'s that contain edges from these triangles. In addition, any of these $(6k^2 + k) P_4$'s must use an edge from one of the cliques $Q_i$, $i \in [1, 3]$ or an edge joining a clique vertex to the rest of the graph $G'$. Since there are
exactly $(6k^2 + k)$ such edges, the claim follows. Now, the $P_4$-decomposition of any $G_i$, $i \in [1, 6k]$ in the
decomposition of $G'$ gives a $P_4$-decomposition of $G$.
□

We now prove a strengthening of Theorem 17 above.

**Theorem 18** For all integers $k \ge 3$, the problem of determining if $P_4$ decomposes a 2k-regular multigraph $G$ with $\mu(G) \le \lfloor \frac{2k}{3} \rfloor + 1$ is NP-Complete.

**Proof:** Clearly, the problem is in NP. If $k$ is a multiple of 3 then the theorem follows from Theorem 17 above.

So, suppose that $k = 3m + 1$ for some integer $m \ge 1$. For $m \ge 1$, given a (6$m$ + 1)-regular graph $G$, we will construct a (6$m$ + 2)-regular multigraph $G'$ with $\mu(G') \le (2m + 1)$ such that $P_4$ decomposes $G$ if and only if $P_4$ decomposes $G'$. This will prove the theorem for this case because by Theorem 16 the problem of determining if $P_4$ decomposes a (6$m$ + 1)-regular graph is NP-Complete for all $m \ge 1$. If $|V(G)| = n$, we will use $n$ copies of the following gadget graph $H$ in our construction of $G'$. To construct the gadget $H$, take 3 disjoint copies of the clique $K_{2m}$ and add $2m$ disjoint triangles, each containing one vertex from each of the 3 cliques with the multiplicity of each edge of these triangles being $(2m+1)$. This completes the construction of the gadget graph $H$ which is (6$m$ + 1)-regular and has $\mu(H) \le (2m + 1)$. In the construction of $G'$ we will add one edge between each vertex of a copy of $H$ and the rest of $G'$.

Now, given a (6m + 1)-regular graph G on n vertices $v_i$, $i \in [1, n]$, make 6m disjoint copies $G_i$, $i \in [1, 6m]$ of G, and n disjoint copies $H_i$, $i \in [1, n]$ of H. Join each vertex of $H_i$ to a different copy of $v_i \in \bigcup_{j=1}^{6m} V(G_j)$ for $i \in [1, n]$. This completes the construction of the graph $G'$. Now, as in the proof of Theorem 17, we can argue that the edges in each $H_i$, $i \in [1, n]$ together with the 6m edges between a vertex of $H_i$ and a vertex not in $V(H_i)$ must be decomposed into $P_4$ s without using any other edges. The rest of the proof is similar to that of Theorem 17.

To complete the proof, suppose that $k = 3m + 2$ for some integer $m \ge 1$. For $m \ge 1$, given a (6$m$ + 3)-regular graph $G$, we will construct a (6$m$ + 4)-regular multigraph $G'$ with $\mu(G') \le (2m + 2)$ such that $P_4$ decomposes $G$ if and only if $P_4$ decomposes $G'$. This will prove the theorem for this case because by Theorem 16 the problem of determining if $P_4$ decomposes a (6$m$ + 3)-regular graph is NP-Complete for all $m \ge 1$. If $|V(G)| = n$, we will use $n$ copies of the following gadget graph $H$ in our construction of $G'$. To construct the gadget $H$, take 3 disjoint copies $Q_1, Q_2$, and $Q_3$ of the clique $K_{2m}$ and add $2m$ disjoint triangles, each containing one vertex from each of the 3 cliques with the multiplicity of the edges between a vertex of $Q_1$ and a vertex of $Q_2$ being (2$m$ + 1) and the multiplicity of all other edges of the added triangles being (2$m$ + 2). Now, add a perfect matching with $2m$ edges between cliques $Q_1$ and $Q_2$ making sure that none of the edges in the matching are parallel to any edge of the triangles added earlier. This completes the construction of the gadget graph $H$ which is (6$m$ + 3)-regular and has $\mu(H) \le (2m + 2)$. In the construction of $G'$ we will add one edge between each vertex of a copy of $H$ and the rest of $G'$.

Now, given a (6m + 3)-regular graph G on n vertices $v_i$, $i \in [1, n]$, make 6m disjoint copies $G_i$, $i \in [1, 6m]$ of G, and n disjoint copies $H_i$, $i \in [1, n]$ of H. Join each vertex of $H_i$ to a different copy of $v_i \in \bigcup_{j=1}^{6m} V(G_j)$ for $i \in [1, n]$. This completes the construction of the graph $G'$. The rest of the proof is similar to the proof of Theorem 17.
□

We note that the proof of Theorem 18 used gadgets for a 2k-regular multigraph G that contain triangles
with (2k + 1) edges. In view of this we offer the following conjecture which is verified by Theorem 12 in
the case when k = 2 and which implies Theorem 5 when k is a multiple of 3.
**Conjecture 2** Let $G$ be a connected $2k$-regular multigraph $G$ with $\mu(G) \le \lfloor \frac{2k}{3} \rfloor + 1$ and such that any three vertices in $G$ induce at most $2k$ edges. Then $P_4$ decomposes $G$ if and only if $|E(G)|$ is divisible by 3.

## Acknowledgements

We would like to thank the anonymous referee for a careful reading of our paper and in particular for pointing out an error in our original proof of Theorem 11.

## References

[1] J.A. Bondy. Perfect path double covers of graphs. *J. Graph Theory*, 14:259–272, 1990.

[2] J.A. Bondy and U.S.R. Murty. *Graph Theory*. Springer, 2008.

[3] A. Bouchet and J. L. Fouquet. Trois types de decompositions d'un graphe en chaines. *Ann. Discrete Math.*, 17:131–141, 1983.

[4] K. Bryś and Z. Lonc. Polynomial cases of graph decomposition: A complete solution of holyer's problem. *Discrete Mathematics*, 309:1294–1326, 2009.

[5] D. Dor and M. Tarsi. Graph decomposition is np-complete: A complete proof of holyer's conjecture. *SIAM Journal on Computing*, 26:1166–1187, 1997.

[6] Saad El-Zanati, Michael Plantholt, and Shailesh Tipnis. On decomposing even regular multigraphs into small isomorphic trees. *Discrete Mathematics*, 325:47–51, 2014.

[7] Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. *Theoretical Computer Science*, 38:293–306, 1985.

[8] R. Häggkvist. Decompositions of complete bipartite graphs. *London Math. Soc. Lecture Note Ser. C. U. P.*, 141:115–147, 1989.

[9] K. Heinrich, J. Liu, and M. Yu. $P_4$-decompositions of regular graphs. *J. Graph Theory*, 31:135–143, 1999.

[10] A. Kotzig. Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades. *Časopis Pěst. Mat.*, 82:76–92, 1957.

[11] M. Kouider and Z. Lonc. Path decompositions and perfect path double covers. *Australas. J. Combin.*, 19:261–274, 1999.

[12] Natalia Oksimets. A characterization of Eulerian graphs with trianglefree Euler tours. Technical Report 1, Department of Mathematics, Umeå University, 2003.

[13] N. Teypaz and C. Rapine. Graph decomposition into paths under length constraints. Technical Report 165, Les Cahiers Leibniz, 2008.