Laurent Bulteau

Guillaume Fertin

Anthony Labarre

Romeo Rizzi

Irena Rusu

Decomposing Subcubic Graphs into Claws, Paths or Triangles *

Keywords: decomposition, edge partition, NP-completeness, subcubic graph

Let S = {K1,3, K3, P4} be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph G into graphs taken from any non-empty S ⊆ S. The problem is known to be NP-complete for any possible choice of S in general graphs. In this paper, we assume that the input graph is subcubic (i.e. all its vertices have degree at most 3), and study the computational complexity of the problem of partitioning its edge set for any choice of S . We identify all polynomial and NP-complete problems in that setting.

Introduction

Given a graph G and a set S of graphs, the S-decomposition problem asks whether G can be represented as an edge-disjoint union of subgraphs, each of which is isomorphic to a graph in S. The problem has a long history that can be traced back to Kirkman [START_REF] Kirkman | On a problem in combinatorics[END_REF] and has been intensively studied ever since, both from pure mathematical and algorithmic points of view. One of the most notable results in the area is the answer of Dor and Tarsi [START_REF] Dor | Graph decomposition is NP-complete: A complete proof of Holyer's conjecture[END_REF] to the long-standing "Holyer conjecture", which stated that "the problem of edge-partitioning a graph into subgraphs isomorphic to a fixed graph H is NP-complete for all graphs H with at least 3 edges" [START_REF] Holyer | The NP-completeness of some edge-partition problems[END_REF]. Dor and Tarsi note that this conjecture as stated is false, and prove that a slightly modified version holds: Theorem 1.1. [START_REF] Dor | Graph decomposition is NP-complete: A complete proof of Holyer's conjecture[END_REF] For every graph H, the {H}-decomposition problem is NP-complete whenever H contains a connected component with three edges or more.

Theorem 1.1 leaves open the cases where all connected components of H contain at most two edges, which were eventually all shown to be tractable Theorem 1.2. Let s, t ∈ N. There is a polynomial time algorithm to decide if an instance graph has an {sP 2 ∪ tP 3 }-decomposition (see Lonc [START_REF] Lonc | Edge decomposition into isomorphic copies of sK 1,2 is polynomial[END_REF] for the case s = 0, Priesler and Tarsi [START_REF] Priesler | On the decomposition of graphs into copies of P 3 ∪tK 2[END_REF] for the case s = 1 and t ≥ 1, and Bryś and Lonc [START_REF] Bryś | Polynomial cases of graph decomposition: A complete solution of Holyer's problem[END_REF] for all other cases).

Note that single-vertex components can be safely ignored, provided the input graph is large enough, since we only consider edge-disjoint (not vertex-disjoint) decompositions. Many variants of the S-decomposition problem have been studied while attempting to prove Holyer's conjecture or to obtain polynomial-time algorithms in restricted cases [START_REF] Yuster | Combinatorial and computational aspects of graph packing and graph decomposition[END_REF], and applications arise in such diverse fields as traffic grooming [START_REF] Muñoz | Edge-partitioning regular graphs for ring traffic grooming with a priori placement of the ADMs[END_REF] and graph drawing [START_REF] Fusy | Transversal structures on triangulations: A combinatorial study and straight-line drawings[END_REF]. In particular, Dyer and Frieze [START_REF] Dyer | On the complexity of partitioning graphs into connected subgraphs[END_REF] studied a variant where S is the set of all connected graphs with k edges for some natural k, and proved the NP-completeness of the S-decomposition problem for any k ≥ 3, even under the assumption that the input graph is planar and bipartite (see Theorem 3.1 in [START_REF] Dyer | On the complexity of partitioning graphs into connected subgraphs[END_REF]). They further claimed that the problem remains NP-complete under the additional constraint that all vertices of the input graph have degree 2 or 3. Interestingly, if k = 3 and G is a bipartite cubic graph (i.e., each vertex has degree 3), then G can clearly be decomposed in polynomial time, using K 1,3 's only, by selecting either part of the bipartition and making each vertex in that set the center of a K 1, [START_REF] Brandstädt | Graph classes: a survey[END_REF] . This shows that focusing on the case k = 3 and on cubic graphs can lead to tractable results -as opposed to general graphs, for which when k = 3, and for any non-empty S ⊆ S, the S -decomposition problems all turn out to be NP-complete [START_REF] Dyer | On the complexity of partitioning graphs into connected subgraphs[END_REF][START_REF] Holyer | The NP-completeness of some edge-partition problems[END_REF].

In this paper, we study the S-decomposition problem on subcubic graphs in the case where S is the set of all connected graphs on three edges, i.e., S = {K 1,3 , K 3 , P 4 } (respectively known as claws, triangles and paths). For any non-empty S ⊆ S, we settle the computational complexity of the corresponding S -decomposition problem. More specifically, we give polynomial-time algorithms for:

• decomposing strictly subcubic graphs into claws, triangles, or both claws and triangles (Propositions 3.2, 3.3 and 3.6);

• decomposing cubic graphs using only claws (Proposition 4.3; triangles are trivially unusable on their own, and a polynomial-time approach to path decompositions was previously known) or both paths and triangles (Proposition 4.2);

and we show that all other decomposition problems on strictly subcubic graphs are NP-complete (Theorems 3.1 and 3.5 and Propositions 3.4 and 3.7), even if the input graph is planar and bipartite. Furthermore, we prove that deciding whether a cubic graph admits a decomposition into paths and claws (and possibly triangles) is an NP-complete problem (Theorem 5.6), even if the input graph is K 3 -free and planar. Table 1 summarises the state of knowledge regarding the complexity of decomposing subcubic and arbitrary graphs using connected subgraphs of size 3, and puts our results into perspective. Without loss of generality, the input graph is assumed to be connected; otherwise, separate results can be used on different components depending on whether they are strictly subcubic or cubic. Table 1: Known complexity results on decomposing graphs using subsets of {K 1,3 , K 3 , P 4 }.

A large portion of the results in this paper first appeared in a conference version [START_REF] Bulteau | Decomposing cubic graphs into connected subgraphs of size three[END_REF]. The main additions and differences are:

• all results on strictly subcubic graphs (Section 3);

• explicit algorithms (Algorithms 1 to 3) and complexity analyses for the polynomial time solvable cases (see Table 1);

• a sharper characterisation of hard instances for the problems of decomposing cubic graphs in the case where {K 1,3 , P 4 } ⊆ S : we now have a proof that those problems are hard on planar graphs, whereas the previous versions of those results only assumed K 3 -freeness (see Theorem 5.6);

• and some simplifications and generalisations of previous versions of our results.

Notation and definitions

We follow Brandstädt et al. [START_REF] Brandstädt | Graph classes: a survey[END_REF] for notation and terminology. All graphs we consider are simple and nontrivial (i.e. |V (G)| ≥ 2 and |E(G)| ≥ 1). A cubic graph contains only vertices of degree 3, while a strictly subcubic graph contains at least one vertex of degree strictly less than 3; a subcubic graph may be either cubic or strictly subcubic.

Definition 2.1. Given a set S of graphs, a graph G admits an S-decomposition, or is S-decomposable, if E(G) can be partitioned into subgraphs, each of which is isomorphic to a graph in S.

Throughout the paper, S denotes the set of connected graphs of size 3, i.e. S = {K 1,3 , K 3 , P 4 }. We study the following problem:

S -decomposition

Input:

a subcubic graph G = (V, E), a non-empty set S ⊆ S. Question: does G admit an S -decomposition?

During the process of building a decomposition D for a graph G, it will sometimes be convenient to distinguish between covered edges, i.e. edges that belong to some element of D, and uncovered edges, which do not belong to any element of D. Definition 2.2. Given a graph G = (V, E), removing a subgraph H = (W ⊆ V, F ⊆ E) of G consists in removing edges in F from G as well as the possibly resulting isolated vertices. We use the notation G \ H to denote the graph obtained from G by removing H. For a subset U ⊆ V , we use the lighter notation

G \ U instead of G \ (U, ∅). We let G[U ] denote the subgraph of G induced by U ⊆ V (G). Recall that a graph G is H-free if there is no subset U of V (G) such that G[U ] is isomorphic to a given graph H. If G is not H-free, we say that G contains (a copy of) H.
Definition 2.3. Let G and G be two graphs:

• subdividing an edge {u, v} ∈ E(G) consists in inserting a new vertex w into that edge, so that V (G) becomes V (G) ∪ {w} and E(G) is replaced with (E(G) \ {u, v}) ∪ {u, w} ∪ {w, v};

• attaching G to a vertex u ∈ V (G) means building a new graph H by identifying u and some vertex v ∈ V (G );

• attaching G to an edge e ∈ E(G) consists in subdividing e using a new vertex w, then attaching G to w.

Figure 1 illustrates the process of attaching an edge to an edge of the cube graph, which yields what we refer to as a buoy graph. We shall use N (v) to denote the open neighbourhood of a vertex v in a graph, i.e. the set that consists of all vertices adjacent to v, as opposed to its closed neighbourhood which we denote N [v] = N (v) ∪ {v}. We use E(v) to denote the set of all edges that are incident with vertex v.

u v u v

Decomposing strictly subcubic graphs

In this section, we assume that the graph G we seek to decompose is strictly subcubic. Our hardness results will follow the strategies presented by Dyer and Frieze [START_REF] Dyer | On the complexity of partitioning graphs into connected subgraphs[END_REF], who use the following well-known NP-complete problem [START_REF] Dyer | Planar 3DM is NP-complete[END_REF]: planar exact cover by 3-sets (planar x3c) Input:

a set W and a set of triplets T ⊆ W × W × W such that the bipartite graph G = (W ∪ T, E) is planar, where E = ∪ t=(r,b,y)∈T {{r, t}, {b, t}, {y, t}}. Question: is there a subset T ⊆ T which contains all elements of W exactly once? planar x3c remains NP-complete under the following restriction [START_REF] Dyer | Planar 3DM is NP-complete[END_REF], which we will assume holds for our reductions: each element of W appears in two or three elements of T . We will find it convenient in our reductions to view instances of planar x3c immediately as planar embeddings of the bipartite graph G as described in the problem definition.

Decompositions with only one type of graph

We start our study of S -decomposition on strictly subcubic graphs with only P 4 's at our disposal. We show that this first problem is NP-complete.

Theorem 3.1. The {P 4 }-decomposition problem is NP-complete for strictly subcubic planar bipartite graphs.

Proof. We transform a planar embedding of an instance G of planar x3c into a new graph G by replacing each vertex w in W with one of the two vertex gadgets described below, depending on its degree. Since we assume that w has degree either 2 or 3, we replace w with H 2 in the former case or with H 3 in the latter. The subgraph of G induced by N [t], for each triplet t in T , is mapped onto a triplet gadget H t attached to three gadgets denoted by H(z), where H(z) is either gadget H 2 or H 3 depending again on the degree of z in G. Vertices v 1 and v 2 in H 2 (and v 3 in the case of H 3 ) will be used for attaching each gadget to H t , so the notation v r (resp. v b and v y ) corresponds to one of the v i 's in H(r) (resp. H(b) and H(y)). Figure 2 illustrates the transformation The resulting graph G is clearly strictly subcubic. We now show that G admits an exact cover by 3-sets if and only if G admits a {P 4 }-decomposition. ⇒: we map every triplet t in an instance G of planar x3c onto three P 4 's in the decomposition D that we build for G , in a way that depends solely on whether or not t has been selected as part of a solution T to G. More specifically, as Figure 3 illustrates: To lighten the discussion, we will refer to a P 4 in D with only two edges in a vertex gadget as a partial P 4 . Note that since T is an exact cover by 3-sets, every vertex gadget contains exactly one partial P 4 , which must involve one of its vertices with label v 1 or v 2 (or v 3 for H 3 ).

v 1 v 2 e 1 e 2 v 1 v 2 v 3 1 2 e 1 e 2 e 3 e 4 t r b y t v r v b v y x 1 x 2 x 3 x 4 x 5 x 6 H(r) H(b) H(y) gadget H 2 gadget H 3 gadget H t for triplets
We now show that the choices we make for each gadget H t completely determine the rest of D, by examining their impact on the decomposition of the attached gadgets. We distinguish between the following cases, illustrated in Figure 4: that contains e 3 and ends with v 2 . In that case, v 3 is left uncovered, and covering it with a P 4 will require the use of its other incident edge in the triplet gadget to which H 3 is attached. (end of Claim 2)

(a) (H 2 ): if v 1 is
v 1 v 2 v 3 1
We can now show how to transform any {P 4 }-decomposition D for G into an exact cover by 3-sets for G: every vertex gadget contains exactly one partial P 4 (Claim 1) which is completed using an edge of the triplet gadget to which it is attached in order to obtain a P 4 , say P , of D. In other words, P "points" to the triplet that must be selected to solve the original instance G of planar x3c. Claim 2 guarantees that either all elements of a triplet or none of them will be selected, and Claim 1 ensures that no element can be covered by two different triplets. Therefore, the solution we deduce from D is indeed an exact cover by 3-sets.

We only have two properties left to prove:

1. G is bipartite: since the gadgets we introduced are trees, they cannot create any new cycle in G , but they will lengthen cycles that were already present in G in two ways.

(a) Since vertices in W are replaced by a copy of H 2 or H 3 , a P 3 with edges {t a , w} and {w, t b } in a cycle of G will now enter gadget H(w) through some v i and exit it through some v j = v i . Depending on the degree of w and the specific entry and exit points in H(w), this adds either 6 or 8 edges to the cycle.

(b) Since vertices in T are replaced by a copy of H t , a P 3 with edges {w c , t} and {t, w d } in a cycle of G will now enter gadget H t through some v i and exit it through some v j = v i . Depending on the specific entry and exit points in H t , this adds either 4 or 8 edges to the cycle.

In all cases, all cycles in G are even to start with, and become longer but remain even in G . Therefore, G is also bipartite.

2. G is planar: let us identify G with any of its planar embeddings. Again, since each gadget is a tree, each gadget itself admits a planar embedding; and since no two edges connecting two different elements of W to either the same triplet or different triplets in G cross, the replacement of these elements with our gadgets will not create any crossing in G either.

We now move on to the case of {K 1,3 }-decompositions, which Algorithm 1 solves in polynomial time. We prove its correctness below. Proposition 3.2. The {K 1,3 }-decomposition problem for strictly subcubic connected graphs is in P.

Proof. Since the input graph G is strictly subcubic, it contains a vertex v of degree 1 or 2 whose neighbour(s) must be the center of a K 1,3 if a {K 1,3 }-decomposition exists for G. Since G is connected, the graph G obtained from G by removing that K 1,3 is also strictly subcubic, and therefore G admits a {K 1,3 }-decomposition if and only if G does. The decomposition, if it exists, can be found by repeating this claw-removal strategy until either all edges have been removed, in which case we have found a {K 1,3 }-decomposition, or no new claw center can be found, in which case no {K 1,3 }-decomposition exists.

Algorithm 1 implements the strategy described in the proof of Proposition 3.2 in an iterative way. It starts by pushing all vertices of degree strictly less than 3 onto a stack S, then keeps popping vertices and pushing neighbours of the newly created claws in the decomposition, which takes O(1) time. Its time complexity is

O(|V | + |E|) = O(|V |), since G is strictly subcubic.

Algorithm 1: StrictlySubcubicClawDecomposition(G)

Input: A graph G whose connected components are all strictly subcubic. Connectedness plays a minor role in our algorithms, since the decomposition problems we study can be solved independently on each connected component. However, we will need to use Algorithm 1 when we decompose cubic graphs, and we will not be able to guarantee that the input to Algorithm 1 will be connected. This can only be an issue for cubic components, since we have not yet explained how to decompose them, which is why we require that all connected components in the input to Algorithm 1 be strictly subcubic. We conclude this section with the easiest case: decomposing strictly subcubic graphs using only K 3 's.

Output: A K 1,3 -decomposition of G if one exists, ∅ otherwise. 1 D ← ∅; 2 S ←
Proposition 3.3. The {K 3 }-decomposition problem for strictly subcubic graphs is in P.

Proof. Straightforward: a strictly subcubic graph admits a {K 3 }-decomposition if and only if all its connected components are K 3 's.

Decompositions with two types of graphs

We now examine decomposition problems on strictly subcubic graphs using two types of graphs, starting with the following hardness result. Proposition 3.4. The {K 3 , P 4 }-decomposition problem is NP-complete for strictly subcubic planar bipartite graphs.

Proof. Follows directly from the proof of Theorem 3.1, since our reduction produces a bipartite graph which is therefore K 3 -free so only P 4 's can be used in a decomposition.

The second hardness result of this subsection requires a more involved proof but which is similar in spirit to that of Theorem 3.1.

Theorem 3.5. The {K 1,3 , P 4 }-decomposition problem is NP-complete for strictly subcubic planar bipartite graphs.

Proof. We transform a planar embedding of an instance G of planar x3c by replacing G[N [w]] for each w in W with either of the gadgets shown in Figure 6, depending on its degree. Since we assume that the degree of w is either 2 or 3, we replace it with H 2 in the former case or with H 3 in the latter.

The resulting graph G is clearly strictly subcubic. We now show that G admits an exact cover by 3-sets if and only G admits a {K 1,3 , P 4 }-decomposition. ⇒: every triplet in a solution T to the instance G of planar x3c naturally induces a K 1,3 which will be part of the {K 1,3 , P 4 }-decomposition D of G . Since every element w of W is covered exactly once by T , exactly one edge incident to w in G is part of a K 1,3 and therefore exactly one edge incident to either t i or t j (or

w t i t j t i t j w t i t j t k t i t j t k f i f k e i e j e k gadget H 2 gadget H 3
t k if w has degree 3) in the corresponding gadget in G is part of a K 1,3 in D.
Therefore, we only need to show that the remaining edges of each gadget admit a {K 1,3 , P 4 }-decomposition. If w has degree 2, then that decomposition consists of a single P 4 . For the case where w has degree 3, we have two cases to distinguish: either e i is unavailable (the case e k is symmetric), or e j is; in both cases, the rest of the gadget admits a {P 4 }-decomposition, as shown below. Figure 7 illustrates both cases, with arrows indicating implications, i.e. the fact that selecting a certain P 4 forces us to select another P 4 . ⇐: to prove that a {K 1,3 , P 4 }-decomposition for G yields an exact cover by 3-sets for G, we first observe that each gadget's structure limits our choices for a valid {K 1,3 , P 4 }-decomposition.

t i t j t k f i f k e i e j e k t i t j t k f i f k e i e j e k e i belongs to a K 1,3 in D centered in t i e j belongs to a K 1,3 in D centered in t j
Claim 3. If G admits a {K 1,3 , P 4 }-decomposition D, then no K 1,3 in D is a subgraph of a gadget.
Proof. A K 1,3 appearing as a subgraph of either gadget must use a vertex of degree 3 of that gadget as its center. This clearly cannot happen for gadget H 2 , or for the vertices adjacent to t i and t k in gadget H 3 , since in all these cases allowing those vertices to be the center of a K 1,3 in D would leave a pendant edge uncovered. The remaining case to handle is that of the vertex incident to t j in gadget H 3 , where such a choice would force the partial decomposition of the gadget shown in Figure 8: whichever choice we make for building the remaining P 4 's in the decomposition necessarily leaves four edges of the gadget uncovered. Proof. The claim trivially holds for gadget H 2 , so we now turn to gadget H 3 . For this case analysis, let f i (resp. f k ) denote the edge incident to e i (resp. e k ) on the unique path in the gadget between t i and t k . The P 4 's in D that are incident to the leaves of H 3 will have to use either e i or f i , on one hand, and either e k or f k , on the other hand. This leads us to the following four cases, illustrated in Figure 9, with arrows indicating implications, i.e. the fact that selecting a certain P 4 forces us to select another P 4 .

t i t j t k f i f k e i e j e k
(a) Selecting e i and e k leads to building a P 4 -decomposition which is the only possible choice and leaves only e j uncovered. (b) Selecting f i and f k leads to building a partial P 4 -decomposition which cannot be completed: the only way to cover the uncovered edges of the gadget is to use a P 4 that starts at the endpoint of either black P 4 , but that P 4 will leave at least one edge of the gadget uncovered, regardless of whether it ends with e j . (c) Selecting e i and f k leads to building a P 4 -decomposition which is the only possible choice and leaves only e k uncovered. (d) Selecting f i and e k leads to building a P 4 -decomposition which is the only possible choice and leaves only e i uncovered.

(end of Claim 4)

We can now show how to transform any {K 1,3 , P 4 }-decomposition D for G into an exact cover by 3-sets for G: every gadget has exactly one uncovered edge (Claim 4), and that edge is incident to the triplet t that will be part of the exact cover by 3-sets. Since D is a {K 1,3 , P 4 }-decomposition, the other two edges incident to t are also uncovered in their respective gadgets; therefore, the triplets that belong to the exact cover by 3-sets are exactly those triplets whose closed neighbourhood induces a K 1,3 that belongs to D, and Claim 3 guarantees that only they can correspond to a K 1,3 in D. By Claim 4, the original vertex w in W is covered by exactly one triplet, so the resulting solution is indeed an exact cover by 3-sets.

t i t j t k f i f k e i e j e k t i t j t k f i f k e i e j e k (a) (b) t i t j t k f i f k e i e j e k t i t j t k f i f k e i e j e k (c) (d)
Figure 9: The four cases in the proof of Claim 4 (reverse direction of Theorem 3.5).

We only have two properties left to prove:

1. G is bipartite: since the gadgets we introduced are trees, they cannot create any new cycle in G , but they may lengthen cycles that were already present in G. The parts of cycles in G that go through a vertex of degree 2 in W are not affected by the replacement with gadget H 2 ; those that go through a vertex of degree 3 will necessarily contain two edges from {{t i , w}, {t j , w}, {t k , w}}, and depending on the case, gadget H 3 will add either 6 or 12 edges to that cycle. Therefore, since all cycles in G are even, their (possibly lengthened) analogues in G are also even, so G is indeed bipartite.

2. G is planar: let us identify G with any of its planar embeddings. Again, since each gadget is a tree, each gadget itself admits a planar embedding; and since no two edges connecting two different elements of W to either the same triplet or different triplets in G cross, the replacement of these elements with our gadgets will not create any crossing in G either.

The only remaining case when two subgraphs are allowed is the case of {K 1,3 , K 3 }-decompositions. Algorithm 2 finds a {K 1,3 , K 3 }-decomposition for a strictly subcubic graph G in time O(|V |) if one exists. We prove its correctness below.

Proposition 3.6. The {K 1,3 , K 3 }-decomposition problem for strictly subcubic graphs is in P.

Proof. Since G is strictly subcubic, it contains a vertex v of degree 1 or 2. We have three cases to consider for G to admit a {K 1,3 , K 3 }-decomposition D:

1. if v is a leaf, then it must be adjacent to a vertex of degree 3 which will be the center of a K 1,3 in D; Either one of the above three cases occur and we can produce a graph G on which to recurse by removing a K 1,3 or a K 3 from G according to the above rules, or no decomposition for G exists. The graph G , if non-empty, resulting from this removal is necessarily strictly subcubic: at least one of the vertices concerned by the removal ensures the connectedness of G, thus it has at least one and at most two incident edges in G . We conclude that G admits a {K 1,3 , K 3 }-decomposition if and only if G does.

The approach implemented in Algorithm 2 uses a stack in the same way as Algorithm 1, and runs in O(|V |) time. The caveats regarding disconnected graphs that we expressed in the case of Algorithm 1 apply to Algorithm 2 as well, but can be resolved in exactly the same way.

Decompositions with three types of graphs

We conclude our analysis of S -decomposition on strictly subcubic graphs with the case where all connected subgraphs on three edges are allowed. The hardness of this variant is a direct consequence of our previous results.

Proposition 3.7. The {K 1,3 , K 3 , P 4 }-decomposition problem is NP-complete for strictly subcubic planar bipartite graphs.

Proof. Follows directly from the proof of Theorem 3.5, since our reduction produces a K 3 -free graph and therefore only P 4 's and K 1,3 's can be used to decompose G.

Decomposing cubic graphs

From this section on, we study our decomposition problems on cubic graphs. We give polynomial-time algorithms for all subproblems tackled in this section; the next section will be devoted to proving the hardness of decomposing planar K 3 -free cubic graphs using only K 1,3 's and P 4 's.

Decompositions without a K 1,3

In this section, we study decompositions of cubic graphs that use only P 4 's or K 3 's. Note that no cubic graph is {K 3 }-decomposable, since all its vertices have odd degree. According to Bouchet and Fouquet [START_REF] Bouchet | Trois types de décompositions d'un graphe en chaînes[END_REF], Kotzig [START_REF] Kotzig | Z teorie konečných pravidelných grafov tretieho a štvrtého stupňa[END_REF] proved that a cubic graph admits a {P 4 }-decomposition iff it has a perfect matching. However, the proof of the forward direction as presented in [START_REF] Bouchet | Trois types de décompositions d'un graphe en chaînes[END_REF] is incomplete, as it requires the use of Proposition 4.1(b) below, which is missing from their paper. Therefore, we provide the following proposition for completeness, together with another result which will also be useful for the case where S = {K 3 , P 4 }. Proposition 4.1. Let G be a cubic graph that admits a {K 3 , P 4 }-decomposition D. Then, in D, (a) no K 3 is used, and (b) no three P 4 's are incident to the same vertex.

Proof. Partition V (G) into three sets V 1 , V 2 and V 3 , where V 1 (resp. V 2 , V 3
) is the set of vertices that are incident to exactly one P 4 (resp. two, three

P 4 's) in D. Note that V 1 is exactly the set of vertices involved in K 3 's in D. Let n i = |V i |, 1 ≤ i ≤ 3. Our goal is to show that n 1 = n 3 = 0, i.e. V 1 = V 3 = ∅.
For this, note that (1) each vertex in V 3 is the extremity of three different P 4 's, (2) each vertex in V 2 is simultaneously the extremity of one P 4 and an inner vertex of another P 4 , while (3) each vertex in V 1 is the extremity of one P 4 . Since each P 4 has two extremities and two inner vertices, if p is the number of P 4 's in D, we have:

• p = 3n3+n2+n1 2
(by (1), ( 2) and (3) above, counting extremities);

• p = n2
2 (by (2) above, counting inner vertices). Putting together the above two equalities yields n 1 = n 3 = 0, which completes the proof.

The following result immediately follows from the work of Kotzig [START_REF] Kotzig | Z teorie konečných pravidelných grafov tretieho a štvrtého stupňa[END_REF] and Proposition 4.1 above, since K 3 's are not allowed in {K 3 , P 4 }-decompositions. As a result, {K 3 , P 4 }-decomposition for cubic graphs is in P. Proposition 4.2. A cubic graph admits a {K 3 , P 4 }-decomposition iff it has a perfect matching. [START_REF] Micali | algorithm for finding maximum matching in general graphs[END_REF] gave a O( |V ||E|) algorithm for finding a maximum cardinality matching in a graph; therefore, we can find a {K 3 , P 4 }-decomposition for a cubic graph in time O(|V | 3/2 ) by computing a perfect matching and then -if one exists -converting it into a {P 4 }-decomposition as described by Kotzig [START_REF] Kotzig | Z teorie konečných pravidelných grafov tretieho a štvrtého stupňa[END_REF].

Micali and Vazirani

Decompositions without a P 4

In this section, we study decompositions of cubic graphs that use only K 1,3 's or K 3 's. Proof. For the reverse direction, select either set of the bipartition, and make each vertex in that set the center of a K 1,3 . For the forward direction, let D be a {K 1,3 }-decomposition of G, and let C and L be the sets of vertices containing, respectively, all the centers and all the leaves of K 1,3 's in D. We show that this is a bipartition of V (G). First, C ∪ L = V since D covers all edges and therefore all vertices. Second, C ∩ L = ∅ since a vertex in C ∩ L would have degree at least 4. Finally, each edge in D connects the center of a K 1,3 and a leaf of another K 1,3 in D, which belong respectively to C and L. Therefore, G is bipartite.

As a result, {K 1,3 }-decompositions for cubic graphs are computable in O(|V |) time. We now prove that {K 1,3 , K 3 }-decompositions can be computed in polynomial time. Since bipartite graphs admit a {K 1,3 }decomposition (by Proposition 4.3), we can restrict our attention to non-bipartite graphs that contain K 3 's (indeed, if they were K 3 -free, then only K 1,3 's would be allowed and Proposition 4.3 would imply that they admit no decomposition). Our strategy consists in iteratively removing subgraphs from G and adding them to an initially empty {K 1,3 , K 3 }-decomposition until G is empty, in which case we have an actual decomposition, or no further removal operations are possible, in which case no decomposition exists. Our analysis relies on the following notion: a K 3 induced by vertices {u, v, w} in a graph G is isolated if V (G) contains no vertex x such that {u, v, x}, {u, x, w} or {x, v, w} induces a K 3 . Proof (contradiction). If an isolated K 3 were not part of the decomposition, then exactly one vertex of that K 3 would be the center of a K 1,3 , leaving the remaining edge uncovered and uncoverable.

C 6 is a minimal example of a cubic non-bipartite graph with K 3 's that admits no {K 1,3 , K 3 }-decomposition: both K 3 's in that graph must belong to the decomposition (by Lemma 4.1), but their removal yields a perfect matching. The following simple observation will allow us to rely on the algorithms we developed in Section 3.

Observation 4.1. Let G be a connected cubic graph. Then no sequence of at least one edge or vertex removal from G yields a cubic graph. Proof (contradiction). If after applying at least one removal operation on G we obtain a cubic graph G , then the graph that precedes G in this removal sequence must have had a vertex of degree at least 4, since G is connected. Proposition 4.4. For any connected non-bipartite cubic graph G whose K 3 's are all isolated, one can decide in polynomial time whether G is {K 1,3 , K 3 }-decomposable.

Proof. As seen in Lemma 4.1, all isolated K 3 's must belong to a {K 1,3 , K 3 }-decomposition if one exists, so we can remove them all from G and add them to an initially empty set D; therefore, G admits a {K 1,3 , K 3 }-decomposition iff the resulting graph G admits a {K 1,3 }-decomposition. Observation 4.1 implies that all connected components of G are strictly subcubic, and Proposition 3.2 then allows us to compute a decomposition for G if one exists, using Algorithm 2.

We conclude with the case where the graph may contain non-isolated K 3 's. They will necessarily belong to a diamond, i.e. a graph isomorphic to a K 4 from which an edge has been removed. Proposition 4.5. If a cubic graph G contains a diamond, then one can decide in polynomial time whether G is {K 1,3 , K 3 }-decomposable.

Proof. The only cubic graph on 4 vertices is K 4 , which is diamond-free and {K 1,3 , K 3 }-decomposable, so we assume |V (G)| ≥ 6 below. Let H = G[{u, v, w, x}] be a diamond, with {u, x} ∈ E(G), as Figure 10(a) shows. H is connected to two other vertices u and x of G, which are respectively adjacent to u and x, and there are only two ways to use the edges of H in a {K 1,3 , K 3 }-decomposition D, as shown in Figure 10(b) and(c). If u = x (as shown in Figure 10(d)), let y be the neighbour of x which is neither u nor x. If the decomposition we choose for H is the one depicted in Figure 10(b), then edges (x , u) and (x , y) are uncovered, while (x , x) is covered. In that case, no {K 1,3 , K 3 }-decomposition can exist. If the decomposition we choose for H is the one depicted in Figure 10(c), a similar argument applies and leads us to conclude that no {K 1,3 , K 3 }-decomposition can exist either. Altogether, this show that no {K 1,3 , K 3 }-decomposition exists for G in case (d), and therefore, we assume from now on that u = x .

As Figure 10(b) and (c) show, either {u, v, w} or {v, w, x} must form a K 3 in D, thereby forcing either {v, w, x, x } or {u , u, v, w} to form a K 1,3 in D. In both cases, removing the K 3 and the K 1,3 yields a strictly subcubic graph, so we can apply the results obtained in Proposition 3.6 as follows: we apply the decomposition in Figure 10 Without loss of generality, we require that the input to Algorithm 3 be connected. This is because Algorithm 3 uses Algorithms 1 and 2: they both require that all connected components of their inputs be strictly subcubic, and we can only guarantee this if the input to Algorithm 3 is connected (see Observation 4.1). Of course, if the input to Algorithm 3 is not connected, we can simply run it on each connected component of the input.

Algorithm 3: CubicClawTriangleDecomposition(G)

Input: A connected cubic graph G.

Output: A {K 1,3 , K 3 }-decomposition of G if one exists, ∅ otherwise. 5 Decomposing cubic graphs using both K 1,3 's and P 4 's

1 if V (G) admits a bipartition V 1 ∪ V 2 then // see Proposition 4.3 2 return {G[N [v]] | v ∈ V 1 }; 3 if G is K 3 -free then // see Proposition 4.3 4 return ∅; 5 if G K 4 then 6 return {G[{u, v, w}], G \ G[{u, v, w}]}; 7 if G contains a diamond
In this section, we show that problems {K 1,3 , P 4 }-decomposition and {K 1,3 , K 3 , P 4 }-decomposition are NP-complete, even on planar graphs. Our first hardness proof relies on intermediate problems that we define below and is structured as follows: cubic planar monotone 1-in-3 satisfiability ≤ P even-faced edge selection (Lemma 5.4)

≡ {K 1,3 , P 4 }-decomposition of marked graphs (Lemma 5.3)

≤ P {K 1,3 , P 4 }-decomposition in K 3 -free planar graphs (Lemma 5.2) G G G G (a) (b)
Figure 12: Adapting a {K 1,3 , P 4 }-decomposition when attaching a buoy to a marked edge of a graph G.

(a) if {u, w} belongs to a K 1,3 in D , that K 1,3 can be mapped onto a K

Equivalence with even-faced edge selection

Recall that a planar embedding of a planar graph partitions R 2 into connected components which are referred to as the faces of the embedding. Inner faces are bounded by edges and vertices of the graph, while the unbounded face is called the outer face. We represent a face using the set of vertices on its border. A face is said to be incident with an edge e if it contains at least one of its endpoints.

Definition 5.1. A selection in a marked graph (G, M ) with G = (V, E) is a subset E * ⊆ E \ M such that
no two edges are adjacent. The weight of a face is the number of vertices of degree 3 it contains. A selection E * is even-faced if every inner face of (V, E \ E * ) has an even weight.

Note that equivalently, E * is even-faced iff all cycles of (V, E \ E * ) have an even number of vertices of degree 3. We define the following problem, which will prove helpful in the sequel.

even-faced edge selection

Input: a cubic marked graph (G, M ). Question: does G admit an even-faced selection? Figure 14 illustrates this problem and its connection to {K 1,3 , P 4 }-decomposition.

Lemma 5.3. The problems even-faced edge selection and {K 1,3 , P 4 }-decomposition of marked graphs are equivalent. Proof. It suffices to show that a cubic marked graph (G, M ) has an even-faced selection if, and only if, G admits a {K 1,3 , P 4 }-decomposition such that no edge in M is the middle edge of a P 4 . We prove each direction separately.

⇐: assume first that G admits a {K 1,3 , P 4 }-decomposition D. Let E * be the set of middle edges of all P 4 's in D. E * is clearly a subset of E \ M , and no two edges may be incident (such a configuration would require a vertex of degree 4), therefore it is a selection of (G, M ). To show that this selection is also even-faced, we orient every edge e of E \ E * according to D:

• if e belongs to a K 1,3 , orient it from the center to the leaf of the K 1,3 ;

• if e belongs to a P 4 , then it must be one of the extreme edges of this path since it cannot be its middle edge: orient it towards the extremity of the P 4 .

Note that with this construction, for any node v and any incident edge e, where e belongs to some subgraph X in D (where X may be a P 4 or a K 1,3 ), the degree of v is 1 in X if and only if e is going towards v.

We now show that there are three types of vertices in G[E \ E * ]:

(a) vertices with 3 outgoing edges, (b) vertices with 3 incoming edges, and (c) vertices with 1 incoming and 1 outgoing edges.

If a vertex is shared between 3 distinct parts of D, it may only have degree 1 in each, therefore it belongs to class (b). If it is shared by 2 distinct parts of D, then it has degree 1 in either one and degree 2 in the other, therefore it belongs to class (c). Finally, if a vertex is used by a single part of D, it has degree 3 in that part, and therefore belongs to class (a).

Consider now any cycle

C of G[E \ E * ].
Summing over all vertices of C, the total number of outgoing edges in C must equal the total number of incoming edges. Vertices of type (a) contribute 2 to the first sum, vertices of type (b) contribute 2 to the second sum, and vertices of type (c) contribute one to each sum. So every cycle contains as many vertices of type (a) as vertices of type (b). Since types (a) and (b) together represent all vertices of degree 3, every cycle, and in particular every face, contains an even number of vertices of degree 3.

⇒: Let E * be an even-faced selection. Build the (multi-)graph G using G[E \ E * ] by contracting vertices of degree 2 (so that induced paths are replaced with single edges). Then all remaining vertices have degree 3, and by the even faced property, all faces have an even degree. Therefore, G is bipartite: partition its vertices into two independent sets A and B, and orient its edges from A to B. Now, orient all edges of every induced path of G[E \ E * ] according to the orientation of the corresponding edge of G . As in the first part of the proof, there are 3 types of vertices in G[E \ E * ]:

(a) vertices with 3 outgoing edges (which belong to A), (b) vertices with 3 incoming edges (which belong to B), and (c) vertices with 1 incoming and 1 outgoing edges (which do not appear in G since they are contracted).

Build a {K 1,3 , P 4 }-decomposition as follows: for every vertex v of type (a), add a K 1,3 centered in v.

For every edge e = (u, v) ∈ E * , u and v have type (c), so they both are the starting point of outgoing arcs e u , e v respectively: {e u , e, e v } therefore forms a P 4 , and we add it to the decomposition. For every vertex of type (a), (b) or (c), every outgoing edge in E \ E * belongs to a single part added to the decomposition, as well as every every edge in E * . Therefore, this decomposition partitions E.

The interface of a gadget g, denoted by I(g), is the set of its interface edges.

Definition 5.3. A subset B ⊆ I(g) is a border for g if there exists an even-faced selection E * for g such that B = E * ∩ I(g).

Definition 5.4. An outer path of g for E * is a path in the outer face of gadget g, after removing edges from E * , starting and ending with interface edges. It is the whole outer face if there is no remaining interface edge in g after removing E * . Its weight is the number of vertices of degree 3 it contains.

Definition 5.5. A border is even if B = E * ∩ I(g) for some E * such that all outer paths for E * have an even weight.

Intuitively, we build an instance as an assembly of gadgets, where adjacent gadgets share interface edges: vertices of degree 1 are removed in the process, the graph remains planar (since interface edges are on the outer faces of the gadgets), and it is K 3 -free. An even-faced selection for the whole graph can be seen as a collection of even-faced selections, one for each gadget. Conversely, a collection of even-faced selections for all gadgets yields an even-faced selection for the whole graph, when the borders of adjacent gadgets are consistent on shared edges and each border is even (this is a sufficient condition ensuring that all faces shared between several gadgets have an even weight).

Sections 5.3.1 to 5.3.5 are devoted to the introduction of our gadgets and the identification of their borders, which are all even (as will be proved in Propositions 5.1 to 5.5). We then combine them in Section 5.3.6 to obtain the hardness proof outlined above.

The OR gadget

The top of Figure 15 shows the OR gadget, which is our basic building block and has interface {α, β, γ, δ}. It combines two purposes: it serves as a crossing gadget (opposite interface edges are either both selected or both unselected), and as a logical OR (at least one pair among {α, γ} and {β, δ} is selected). Proof. The illustrations in Figure 15(a)-(d) each show an even-faced selection for the OR gadget that corresponds to each of the given sets, so they are indeed borders. Moreover, all outer paths for these selections have even weight, so these three borders are even.

We now prove that any even-faced selection E * has one of the above three borders. Let C be the cycle of length 4 induced by {α , β , γ , δ } in the OR gadget. Since no two edges of E * may be incident, we have |E * ∩ C| ≤ 2, so we have three cases to check:

1. if |E * ∩ C| = 0, then consider the four weight-5 inner faces of the gadget. Each of them has a single incident unmarked edge excluding C, hence this edge must be selected (otherwise the faces would still have an odd weight in (V, E \ E * )). This leads to E * = {α, β, γ, δ} (as in Figure 15(a)).

if |E

* ∩ C| = 1, assume first that E * ∩ C = {α }.
The graph (V, E \ {α }) has four inner faces: two with weight 4, incident to β and δ respectively (so β, δ / ∈ E * ), and two with weight 5, incident to α and γ. Therefore, we must have α, γ ∈ E * to reach weight 4 as in Figure 15(b). The same argument shows that the border must also be {α,

γ} if E * ∩ C = {γ }, or {β, δ} if E * ∩ C = {β } or E * ∩ C = {δ }. 3. if |E * ∩ C| = 2, then E * ∩ C may be either {α , γ } or {β , δ }. Assume first that E * ∩ C = {α , γ }.
The graph (V, E \ {α , γ }) has three inner faces: two with weight 3, incident to β and δ respectively (so β, δ ∈ E * in order to reach weight 2), and one with weight 6 incident to both α and γ. So either α, γ ∈ E * , and this face gets weight 4 (see Figure 15(c)), or α, γ / ∈ E * (see Figure 15(d)). With the same argument, the border is either {α, β, γ, δ} or {α, γ} if E * ∩ C = {β , δ }.

The NAND gadget

The top of Figure 16 shows the NAND gadget, which has interface {α, β, γ, δ}. Similarly to the OR gadget, it combines two purposes: it serves as a crossing gadget (opposite interface edges are either both selected or both unselected), and as a logical NAND (at most one pair among {α, γ} and {β, δ} is selected). Proof. The illustrations in Figure 16(a)-(c) each show an even-faced selection for the NAND gadget that corresponds to each of the given sets, so they are indeed borders. Any of these selections can be verified to be even-faced using the fact that all outer paths of the OR gadget have an even weight.

We now prove that any even-faced selection E * for the NAND gadget has one of the above three borders. Consider first the weight-5 face incident to α and α . To reach an even weight, we have |E * ∩ {α, α }| = 1, i.e. α ∈ E * ⇔ α / ∈ E * . The same property applies to β, γ, δ. Consider now the OR gadget included as a subgraph, with interface {α , β , γ , δ }. Selection E * for the whole NAND gadget yields an even-faced selection for the OR gadget, so its intersection with the interface is a border of the OR gadget. Proposition 5.1 then implies that E * ∩ {α , β , γ , δ } is one of {α , γ }, {β , δ } and {α , β , γ , δ }, and therefore the border is one of {α, γ}, {β, δ}, and ∅.

The ANY gadget

The top of Figure 17 shows the ANY gadget, which has interface {α 1 , α 2 , α 3 }. Its purpose is to force the selection of a single interface edge α i among all three, which corresponds to the "1-in-3" constraint of the satisfiability variant we will reduce from. Proof. Each {α i } is indeed an even border, as can be seen with the even-faced selections depicted in Figure 17(a)-(c).

We now prove that the only choices for an even-faced selection E * for the ANY gadget must be exactly one of the {α i }. Consider first the weight-4 face incident to edges α i and β i for any i ∈ {1, 2, 3}. For this face to maintain an even weight, we have α i ∈ E * ⇔ β i ∈ E * . Consider now the weight-5 faces incident to all three edges β i . Since they have an odd weight, E * ∩ {β 1 , β 2 , β 3 } = ∅. Furthermore, since those three edges are pairwise incident, |E * ∩ {β 1 , β 2 , β 3 }| ≤ 1. Therefore, E * contains exactly one edge among {β 1 , β 2 , β 3 }, and thus exactly one edge among {α 1 , α 2 , α 3 }.

1 β 1 α 2 β 2 α 3 β 3 ANY α 1 β 1 α 2 β 2 α 3 β 3 2 4 4 6 4 (a) α 1 β 1 α 2 β 2 α 3 β 3 4 2 4 4 6 (b) α 1 β 1 α 2 β 2 α 3 β 3

The VAR gadget

The top of Figure 18 shows the VAR gadget, which has interface {α i | 1 ≤ i ≤ 6}. Its purpose is to simulate a boolean variable where either all interface edges are selected, or none at all (as will be seen later on, a literal in a satisfiability instance will be represented as a pair of edges shared between gadgets, hence a variable with three occurrences needs an interface of size 6). Proof. Figure 18(a) and (b) show two selections creating the mentioned borders. They are indeed even-faced since for each OR and NAND gadget, they form an even border of these faces (therefore they can be extended as an even-faced selection of these gadgets, and the weight of any face not entirely included in a smaller gadget is the sum of the weights of outer paths for these gadgets, so it is even as well). Similarly, the weight of any outer path is the sum of the weights of outer paths for several gadgets, so it is also even.

We now show that any even-faced selection E * for the VAR gadget must be either of the mentioned borders. Propositions 5.1 and 5.2 imply that β i ∈ E * ⇔ β j ∈ E * for every 1 ≤ i, j ≤ 6. With the same properties, α 1 ∈ E * ⇔ α 1 ∈ E * ⇔ α 2 ∈ E * (and similarly for {α 3 , α 3 , α 4 } and {α 4 , α 4 , α 5 }). Furthermore, Proposition 5.1 implies that at least one of α 1 and β 1 must be in E * , and Proposition 5.2 implies that at most one of them is in

α 1 β 1 α 2 β 2 α 3 β 3 γ 2 γ 3 ANY ANY Nand CLAUSE α 1 β 1 α 2 β 2 α 3 β 3 γ 2 γ 3 ANY ANY Nand (a) α 1 β 1 α 2 β 2 α 3 β 3 γ 2 γ 3 ANY ANY Nand (b) α 1 β 1 α 2 β 2 α 3 β 3 γ 2 γ 3 ANY ANY Nand (c)
E * . Overall, α 1 ∈ E * ⇔ β 1 / ∈ E * .
The same applies for (α 3 , β 3 ) and (α 5 , β 5 ), and since all β i 's are equivalent, either α i ∈ E * for all 1 ≤ i ≤ 6, or α i / ∈ E * for all 1 ≤ i ≤ 6.

The CLAUSE gadget

The top of Figure 19 shows the CLAUSE gadget, which has interface {α i , β i | 1 ≤ i ≤ 3}. Its purpose is to simulate the behaviour of a "1-in-3" clause, where exactly one pair (α i , β i ) of its interface may be selected (it can be seen as an extension of the ANY interval, where two edges are used for each literal). However, it does not ensure that the pairs (α i , β i ) are selected together (for instance, {α 1 , β 3 } is an even-faced border of this gadget): this constraint will be enforced from outside, by VAR gadgets. This motivates the following definition: a border B for the CLAUSE gadget is paired if, for each

1 ≤ i ≤ 3, α i ∈ B ⇔ β i ∈ B.
Proposition 5.5. The paired borders for a CLAUSE gadget are {α 1 , β 1 }, {α 2 , β 2 } and {α 3 , β 3 }. They are all even.

Proof. These sets are indeed even and constitute paired borders for the CLAUSE gadget, since they can be obtained from the even-faced selections depicted in Figure 19(a)-(c) (just like for the VAR gadget, these selections are even-faced because they yield even borders of the ANY and NAND subgraphs). Let E * be any even-faced selection of the CLAUSE gadget with a paired border. Proposition 5.3 implies that E * contains exactly one edge among α 1 , γ 2 , β 3 . Proposition 5.2 implies that γ 2 ∈ E * ⇔ β 2 ∈ E * , so E * contains exactly one edge among α 1 , β 2 , β 3 . Since the border of E * is paired, it contains exactly one pair among {α 1 , β 1 }, {α 2 , β 2 }, {α 3 , β 3 }.

Assembling gadgets

We now combine our gadgets to show that even-faced edge selection is NP-complete. Lemma 5.4. even-faced edge selection is NP-complete.

Proof (reduction from cubic planar monotone 1-in-3 satisfiability). We first show how to transform an instance φ = C 1 ∧ C 2 ∧ • • • ∧ C n of cubic planar monotone 1-in-3 satisfiability into an instance (G, M ) of even-faced edge selection. The transformation proceeds by: 1. mapping each clause C j = {x j,1 , x j,2 , x j,3 } onto a CLAUSE gadget denoted by CLAUSE(C j ), with interface {α j,1 , β j,1 , α j,2 , β j,2 , α j,3 , β j,3 };

2. mapping each variable x i onto a VAR gadget denoted by VAR(x i ), whose interface edges coincide with the three pairs of edges {α j,h , β j,h } such that x i is the h-th literal of clause j.

Note that G = (V, E) is a cubic planar graph. It is also K 3 -free; indeed, the gadgets are K 3 -free by definition because they are marked graphs. So if a triangle exists it must contain at least two interface edges from some gadget: this is not possible either as those edges may not be incident according to Definition 5.2.

We now show that φ is satisfiable iff (G, M ) admits an even-faced selection.

⇒: We apply the following rules for transforming a satisfying assignment for φ into a selection E * for (G, M ):

• if variable x i is set to true, then select the edges of VAR(x i ) such that all interface edges are selected in the border, as in Figure 18(a).

• otherwise, select the edges of VAR(x i ) creating an empty border, as in Figure 18(b).

By this construction, for each clause gadget CLAUSE(C j ), exactly two edges {α j,h , β j,h } are selected in the interface. This pair corresponds to a border for this gadget, and we select the corresponding edges within the gadget.

It can be seen that this selection is even-faced. In (V, E \ E * ), every face within a VAR or CLAUSE gadget has an even weight since the selection corresponds to an even-faced selection for each one, and every face containing vertices from different gadgets can be seen as a concatenation of outer paths of even weights (since all borders are even), so all faces have an even weight.

⇐: Consider now a selection E * for (G, M ). For each variable x i , we set x i to true if the border of VAR(x i ) is the whole interface, and x i to false otherwise (i.e. if the border is empty, by Proposition 5.4). For each clause C j , 1 ≤ j ≤ n, if a literal x j,h is set to true, then α j h , β j,h ∈ E * , and α j h , β j,h / ∈ E * otherwise. Thus the border of every clause gadget is paired, and by Proposition 5.5, exactly one literal among x j,1 , x j,2 , x j,3 is set to true. Consequently, clause C j is satisfied and, overall, the formula is satisfied by this assignment.

Theorem 5.6. The {K 1,3 , P 4 }-decomposition and {K 1,3 , K 3 , P 4 }-decomposition problems are NPcomplete for planar cubic graphs.

Proof. Lemma 5.4 implies that even-faced edge selection is NP-complete. By Lemma 5.3, this problem is equivalent to {K 1,3 , P 4 }-decomposition of marked graphs. Since this problem reduces to {K 1,3 , P 4 }decomposition restricted to K 3 -free planar cubic graphs (Lemma 5.2), both {K 1,3 , P 4 }-decomposition and {K 1,3 , K 3 , P 4 }-decomposition are NP-complete, even when restricted to planar cubic graphs.

Conclusions and future work

In this paper, we provided a complete computational complexity landscape of the S-decomposition problem, where the input graph G is subcubic and S is the set of connected graphs of size 3. We identified all NP-complete subproblems in that setting and provided linear time algorithms for the problems that are solvable in polynomial time. All hard subproblems are NP-complete even if the input graph is both bipartite and planar, with the exception of decompositions of cubic graphs with a set S ⊇ {K 1,3 , P 4 } where only planarity is guaranteed (Theorem 5.6).

The only remaining nontrivial connected graph of size at most 3 that could have been used is P 3 . Lonc and Pszczoła [START_REF] Lonc | Edge decompositions into two kinds of graphs[END_REF] proved that {P 3 ∪ H}-decomposition is in P, where H is a connected graph of odd size. A closer examination of their results (namely, the comments made in [16, page 6373] right after their Theorem 3.6) allows us to conclude that {P 3 ∪ S }-decomposition for subcubic graphs is in P for any S ⊆ {K 1,3 , K 3 , P 4 }, because the problem then reduces to finding a subgraph H in G isomorphic to an element of S and such that G \ H contains only components of even size. Therefore, all S-decomposition problems on subcubic graphs involving connected graphs of size at most 3 are solved, complementing the cases involving disconnected graphs of size at most 3 covered by Theorem 1.2.

A natural generalisation would be to study decompositions of k-regular graphs into connected components of size k for k > 3. Some partial results exist, which do not use all connected graphs of size k; for instance, {P 4 }-decomposition is known to be in P for 4-regular graphs, but is NP-complete for regular graphs of odd degree ≥ 5 [START_REF] Diwan | The complexity of P 4 -decomposition of regular graphs and multigraphs[END_REF]. On the other hand, {P 5 }-decomposition is known to be in P for K 3 -free 5-regular graphs [START_REF] Botler | Decompositions of triangle-free 5-regular graphs into paths of length five[END_REF], which is obtained by proving a special case of a conjecture stating that if a (2k + 1)-regular graph admits a perfect matching, then it admits a {P k }-decomposition [START_REF] Favaron | Regular path decompositions of odd regular graphs[END_REF]. We would like to determine whether our positive results generalise in any way in that setting. It would also be interesting to identify tractable classes of graphs in the cases where those decomposition problems are hard, and to refine our characterisation of hard instances, as well as to obtain elegant graph-theoretical characterisations of easy instances.

[ 8 ,

 8 Theorem 3.5] in P (Proposition 3.3) O(1) (impossible) NP-complete [12] NP-complete (Theorem 3.1) in P [14] NP-complete [8, Theorem 3.4] in P (Proposition 3.6) in P (Proposition 4.6) NP-complete [8, Theorem 3.5] NP-complete (Theorem 3.5) NP-complete (Theorem 5.6) NP-complete [8, Theorem 3.1] NP-complete (Proposition 3.4) in P (Proposition 4.2) NP-complete [8, Theorem 3.4] NP-complete (Proposition 3.7) NP-complete (Theorem 5.6) NP-complete [8, Theorem 3.1]

Figure 1 :

 1 Figure 1: Attaching a new edge to {u, v}.

Figure 2 :

 2 Figure 2: The gadgets used in the proof of Theorem 3.1.

6 v 7 if no such v exists then 8 return ∅; 9 D 10 S 11 G

 67891011 stack with all vertices of degree < 3 in G;3 while S = ∅ do 4 x ← S.pop(); 5 if deg(x) = 0 then ← arbitrary neighbour of x with degree 3; ← D ∪ E(v);// v must be the center of a K 1,3 , which we add to D .push(vertices in N (v)); // push vertices whose degree will decrease ← G \ {v}; // remove recorded K 1,3 12 return D;

Figure 6 :

 6 Figure 6: The gadgets used in the proof of Theorem 3.5.

Figure 7 :

 7 Figure 7: Propagating triplet selection using P 4 's in gadgets H 2 and H 3 in the proof of the forward direction of Theorem 3.5.

Figure 8 :

 8 Figure 8: The impossibility of finding a {K 1,3 , P 4 }-decomposition for a gadget when using K 1,3 's (Claim 3, reverse direction of Theorem 3.5).(end of Claim 3)

2. if v has degree 2 ,

 2 let e 1 = {u 1 , v} and e 2 = {u 2 , v}:(a) if {u 1 , u 2 } ∈ E(G),the K 3 induced by {u 1 , u 2 , v} must belong to D, since any other choice will leave either e 1 or e 2 uncovered and uncoverable; (b) if {u 1 , u 2 } ∈ E(G), then v must be the intersection of two K 1,3 's in D, otherwise no {K 1,3 , K 3 }-decomposition exists.

Proposition 4 . 3 .

 43 A cubic graph G admits a {K 1,3 }-decomposition iff it is bipartite.

Lemma 4 . 1 .

 41 If a cubic graph G admits a {K 1,3 , K 3 }-decomposition D, then every isolated K 3 in G belongs to D.

Figure 10 :Proposition 4 . 6 .

 1046 Figure 10: (a) A diamond in a cubic graph, and (b), (c) the only two ways to decompose it in a {K 1,3 , K 3 }-decomposition. (d) The case where u = x . All the arguments developed in this section lead to the following result.Proposition 4.6. The {K 1,3 , K 3 }-decomposition problem for a cubic graph G can be solved in time O(|V (G)|). Proof. Algorithm 3 implements the approach proposed in this section, and its correctness follows from proofs of Propositions 4.3 to 4.5. We now examine its time complexity: lines 1-4 run in O(|V (G)|) time. A diamond in a cubic graph can be found by naively searching for a claw {u, v, w, x} with center u and then checking whether G[{v, w, x}] P 3 , which takes O(|V (G)|) time as well. Lines 8-17 either involve operations running in O(1) or O(|V (G)|) time, or calls to Algorithm 2 which, as seen in Section 3, runs in O(|V (G)|) time. Finally, line 18 involves listing all isolated triangles in a cubic graph, which can be done naively by checking the intersection of N (u) and N (v) for each edge {u, v}. This approach takes O(|E(G)|) = O(|V (G)|) time since G is cubic.

9 A 10 D 13 B 14 D 15 if D = ∅ then 16 return

 91013141516 then // see Proposition 4.5 8 u, v, w, x ← vertices as in Figure 10; /* try the decomposition in Figure 10(b) as starting point */ ← {G[{u, v, w}]}; ← StrictlySubcubicClawTriangleDecomposition(G \ A); 11 if D = ∅ then 12 return D ∪ A; /* try the decomposition in Figure 10(c) as starting point */ ← {G[{v, x, w}]}; ← StrictlySubcubicClawTriangleDecomposition(G \ B); D ∪ B; 17 return ∅; /* last case: G is diamond-free (see Proposition 4.4) */ 18 T ← all (necessarily isolated) triangles in G; 19 D ← StrictlySubcubicClawDecomposition(G \ T ); 20 if D = ∅ then 21 return D ∪ T ; 22 return ∅;

Figure 13 :

 13 Figure 13: Obtaining a {K 1,3 , P 4 }-decomposition for a marked graph G from a {K 1,3 , P 4 }-decomposition for its transformed counterpart G .

Figure 15 :

 15 Figure 15: Top: Definition of the OR gadget. Bottom: All possible selections (up to symmetry) for this gadget. Circled numbers indicate the weights of the inner faces.

Proposition 5 . 2 .

 52 The possible borders for a NAND gadget are {α, γ}, {β, δ}, and ∅. They are all even.

Proposition 5 . 3 .

 53 The possible borders for an ANY gadget are {α 1 }, {α 2 }, {α 3 }. They are all even.

Figure 16 :

 16 Figure 16: Top: Definition of the NAND gadget. Bottom: All possible selections for this gadget. Circled numbers indicate the weights of some inner faces.

  α

Figure 17 :

 17 Figure 17: Top: Definition of the ANY gadget. Bottom: All possible selections for this gadget. Circled numbers indicate the weights of the inner faces.

Figure 18 :Proposition 5 . 4 .

 1854 Figure 18: Top: Definition of the VAR gadget. Bottom: All possible selections for this gadget.

Figure 19 :

 19 Figure 19: Top: Definition of the CLAUSE gadget. Bottom: All selections yielding a paired border (α 1 with β 1 , α 2 with β 2 , α 3 with β 3 ).

  1. if t belongs to the solution T , then the P 4 's G [{v r , x 1 , x 2 , x 3 }] and G [{v b , x 4 , x 5 , x 6 }] are added to D, as well as the P 4 's that have two edges in their attached gadget and exactly one edge inG [{t, v r , x 1 , x 2 , x 3 , v b , x 4 , x 5 , x 6 , v y }]; 2. if t does not belong to the solution T , then G [{t, v r , x 1 , x 2 , x 3 , v b , x 4 , x 5 , x 6 , v y }] decomposes into three P 4 's G [{t, v r , x 1 , x 2 }], G [{x 2 , x 3 , v b , x4}] and G [{x 4 , x 5 , x 6 , v y }], which are added as such to D.

	v r		v b		v y	v r	v b	v y
	t	x 1 x 2 x 3	x 4 x 5 x 6	t	x 1 x 2 x 3	x 4 x 5 x 6
	H(r)	H(b)	H(y)	H(r)	H(b)	H(y)
			selected triplet			unselected triplet
	Figure 3: Expressing triplet selection using P 4 's in gadget H t in the proof of the forward direction of
	Theorem 3.1.

  the vertex that belongs to the partial P 4 in H 2 (case v 2 is symmetric), then v 2 must be the starting point of a P 4 which contains edge e 2 , which in turn forces us to select the P 4 that starts with and contains e 1 .(b) (H 3 ): if v 1 is the vertex that belongs to the partial P 4 in H 3 (case v 3 is symmetric), then the P 4 that starts with 1 must end with e 1 . This in turn forces the P 4 that starts with v 2 to end with e 2 , which then forces the P 4 that starts with 2 to end with e 3 ; and finally, this last choice forces the selection of the P 4 that starts with v 3 and ends with e 4 .(c) (H 3 ): finally, if v 2 is the vertex that belongs to the partial P 4 in H 3 , then this forces the selection of both the P 4 from v 1 that ends with e 1 and the P 4 from v 3 that ends with e 4 . These two choices then force us to select e 2 (resp. e 4 ) as the final edge of the P 4 that starts with 1 (resp. 2 ). If G admits a {P 4 }-decomposition D, then D contains exactly one partial P 4 for each gadget H 2 and H 3 which must cover either v 1 or v 2 (or v 3 for H 3 ).Proof. Every {P 4 }-decomposition of H 2 must contain a P 4 that starts with its only leaf and contains either e 1 or e 2 . Choosing either edge for that P 4 forces us to build another P 4 that will contain the other edge and end with either v 2 or v 1 ; the uncovered vertex can then be covered by a partial P 4 using an additional edge from the triplet gadget to which H 2 is attached. The case analysis is similar in the case of H 3 : every {P 4 }-decomposition must contain two P 4 's that start with 1 and 2 , respectively, and two edges out of {e 1 , e 2 , e 3 , e 4 } will then be selected to end Selecting e 1 and e 3 forces us to build a P 4 that contains e 2 and ends with v 2 and another P 4 that contains e 4 and ends with v 3 . In that case, v 1 is left uncovered, and covering it with a P 4 will require the use of its other incident edge which does not belong to H 3 . (b) Selecting e 1 and e 4 leads to a partial decomposition which cannot be completed: any P 4 that ends with v 2 will leave out either e 2 or e 3 , which therefore cannot be part of a P 4 . (c) Selecting e 2 and e 3 forces us to build a P 4 that contains e 1 and ends with v 1 and another P 4that contains e 4 and ends with v 3 . In that case, v 2 is left uncovered, and covering it with a P 4 will require the use of its other incident edge in the triplet gadget to which H 3 is attached. (d) Selecting e 2 and e 4 forces us to build a P 4 that contains e 1 and ends with v 1 and another P 4

	Figure 4 illustrates the above three cases. Arrows indicate implications, i.e. the fact that selecting a certain P 4 forces us to select another P 4 . As a result, a {P 4 }-decomposition for G can straightforwardly be derived from any exact cover by 3-sets for G. ⇐: to prove that a {P 4 }-decomposition for G yields an exact cover by 3-sets for G, we first observe that each gadget's structure limits our choices for a valid {P 4 }-decomposition. The following claims characterise how our gadgets might be decomposed. v 2 e 1 e 2 v 1 v 2 v 3 1 2 e 1 e 2 e 3 e 4 v 1 v 2 v 3 1 2 e 1 e 2 e 3 e 4 (a) (b) (c) Figure 4: Expressing triplet selection using P 4 's in gadgets H 2 and H 3 in the proof of the forward direction of Theorem 3.1. these two P 4 's. Figure 5 illustrates the following four cases, with arrows indicating implications, i.e. the fact that selecting a certain P 4 forces us to select another P 4 . Claim 1. v 1 (a)

2 e 1 e 2 e 3 e 4

  Claim 2. If G admits a {P 4 }-decomposition D, then for every gadget H t in G :1. either G [{t, v r , x 1 , x 2 , x 3 , v b , x 4 , x 5 , x 6 , v y }] decomposes into three P 4 's that belong to D, or 2. edges {t, v r }, {x 3 , v b } and {x 6 , v y } are the terminal edges of partial P 4 's in D that respectively start in H(r), H(b), and H(y). Proof. Claim 1 implies that H(r), H(b) and H(y) each contain exactly one partial P 4 ; if a partial P 4 is incident with H t , then it must be completed using an edge of G [{t, v r , x 1 , x 2 , x 3 , v b , x 4 , x 5 , x 6 , v y }]. We show that all three vertex gadgets attached to H t must be in the same state, i.e. either v r , v b and v y all belong to partial P 4 's in H(r), H(b) and H(y), or none of them do: * if v r belongs to a partial P 4 in D, then its last edge must be {t, v r }, which forces the selection in D of the P 4 induced by {v r , x 1 , x 2 , x 3 }. The P 4 in H(b) that contains v b must be partial, otherwise the number of remaining edges to cover in H t is not a multiple of 3 and they can therefore not be covered regardless of the state of H(y). That partial P 4 must contain {x 3 , v b }, which in turn forces the selection in D of the P 4 induced by {v b , x 4 , x 5 , x 6 } and thereby also the selection of a partial P 4 in H(y) containing {x 6 , v y }. * if v r does not belong to a partial P 4 in D, then D must contain the P 4 induced by {t, v r , x 1 , x 2 }. The P 4 in D that contains x 2 , x 3 and v b cannot end with an edge in H(b), so its last edge is {v b , x 4 } and H(b) contains no partial P 4 involving v b . This in turn forces the P 4 induced by {x 4 , x 5 , x 6 , v

	v 1	v 2	v 3	v 1	v 2	v 3	v 1	v 2	v 3
	e 1 e 2 e 3 e 4	e 1 e 2 e 3 e 4	e 1 e 2 e 3 e 4
	1	2		1	2		1	2
	(a)	(b)			(c)			(d)
	Figure 5: The four cases in the proof of Claim 1 (reverse direction of Theorem 3.1).
			(end of Claim 1)

y } to belong to D, and therefore H(y) has no partial P 4 involving v y .

  1,3 in D by replacing {u, w} with {v, w}; (b) otherwise, {u, w} is an extremal edge of a P 4 in D , and that P 4 can be mapped onto a P 4 in D by replacing {u, w} with {v, w}. Note that the resulting subgraph may only be a P 4 , and not a K 3 , since G is K 3 -free; moreover, only the extremal edge of a P 4 may be marked in (G, M ) by definition.

Algorithm 2: StrictlySubcubicClawTriangleDecomposition(G)

Input: A graph G whose connected components are all strictly subcubic. Output: A {K 1,3 , K 3 }-decomposition of G if one exists, ∅ otherwise.

Marking edges

We first define a marked graph as a pair (G, M ) where G = (V, E) is a planar, embedded, triangle-free graph and M ⊆ E is a subset of marked edges. The drawings that illustrate our proofs in this section show marked edges as thick and solid (i.e.

), and unmarked edges as thin and dashed (i.e.

). We define the following intermediate decomposition problem on marked graphs: {K 1,3 , P 4 }-decomposition of marked graphs Input: a cubic marked graph (G, M ). Question: does G admit a {K 1,3 , P 4 }-decomposition D in which no edge in M is the middle edge of a P 4 ?

The proof of Lemma 5.2, which shows how the above problem relates to {K 1,3 , P 4 }-decomposition, uses the following result.

Lemma 5.1. Let e be a bridge in a cubic graph G which admits a {K 1,3 , K 3 , P 4 }-decomposition. Then e must be the middle edge of a P 4 in D.

Proof (contradiction). First note that e = {u, v} cannot belong to a K 3 in D. Now suppose e is part of a K 1,3 in D. Without loss of generality, the situation is as shown in Figure 11 (G u If we remove from G the K 1,3 in D that contains e, then summing the terms of the degree sequence of

) and therefore G v admits no decomposition into components of size 3. The very same argument shows that if e belongs to a P 4 in D, then it must be its middle edge, which completes the proof. Lemma 5.2. Let (G, M ) be an instance of {K 1,3 , P 4 }-decomposition of marked graphs, where G is K 3 -free and planar, and G be the graph obtained by attaching a buoy to every edge in M . Then (G, M ) is a yes-instance iff G admits a {K 1,3 , P 4 }-decomposition.

Proof. First, note that the transformation from G to G , described in the statement of the lemma, preserves cubicity, K 3 -freeness, and planarity. Now, we prove each direction separately.

⇒: we show how to transform a decomposition D of (G, M ) into a decomposition D of G . The subgraphs in D that have no edge in M are not modified. For the other subgraphs, a subgraph containing an edge of M is either (a) a K 1,3 or (b) a P 4 whose middle edge is not in M . Figure 12 shows how to adapt the decompositions in both cases.

⇐: we now show how to transform any {K 1,3 , P 4 }-decomposition D of G into a decomposition of (G, M ). Again, the only parts of D that will need adapting are those connected to the buoys that we attached to each marked edge when transforming G into G . Since the leaf u of the buoy we attached has a neighbour x such that {u, x} is a bridge in G , {u, x} is the middle edge of a P 4 in D (Lemma 5.1) and we may therefore assume without loss of generality that our starting point in G is as shown in Figure 13, where {v, w} ∈ E(G ) since G is simple; we have two cases to consider: (b) A {K 1,3 , P 4 }-decomposition of this graph, where K 1,3 's are represented by thin blue edges with a white center, and P 4 's by thick red edges. In particular, the middle edge of a P 4 (dark bold) is never marked. (c) An even-faced selection for this graph, where selected edges of E * are indicated as dashed bold lines, and vertices of degree 3 in (V, E \ E * ) are black. Circled numbers correspond to the weights of inner faces of (V, E \ E * ). As described in Lemma 5.3, this selection corresponds to the {K 1,3 , P 4 }-decomposition: selected edges are middle edges of P 4 's, and, among the remaining vertices, vertices that are at the center of a K 1,3 alternate with other vertices, which corresponds to the parity condition.

The hardness of even-faced edge selection

We prove that even-faced edge selection is NP-complete through an assembly of gadgets. We give a few formal definitions below to help understand how gadgets interact, after a short outline of the hardness proof to motivate their introduction. The reduction relies on the cubic planar monotone 1-in-3 satisfiability problem, which is known to be NP-complete [START_REF] Moore | Hard tiling problems with simple tiles[END_REF]:

negations over a set Σ = {x 1 , x 2 , . . . , x m }, with exactly three distinct variables per clause and where each literal appears in exactly three clauses; moreover, the graph with clauses and variables as vertices, and edges joining clauses and the variables they contain, is planar. Question: does there exist an assignment of truth values f : Σ → {true, false} such that exactly one literal is true in every clause of φ?

Since we intend to prove the hardness of even-faced edge selection using a reduction from a variant of the satisfiability problem, we will need a number of gadgets to encode boolean formulas in a graphtheoretic language. Those gadgets come in the form of marked graphs whose type will depend on their function in the reduction: three of them (OR, NAND and ANY) simulate boolean operations, and the remaining two (VAR and CLAUSE) allow us to encode variables and clauses, while preserving the particular additional constraints of cubic planar monotone 1-in-3 satisfiability. All these gadgets will need to be connected in a specific way, which will be achieved using each gadget's interface edges. Definition 5.2. A gadget g is a marked graph (G, M ) with the following properties:

• all vertices have degree 1 or 3; edges incident with vertices of degree 1 are called interface edges;

• all interface edges are unmarked (i.e. in E(G) \ M );

• all interface edges are on the outer face;

• no two interface edges are incident.