Bi Li

Fatima Zahra Moataz

Nicolas Nisse

Karol Suchan

Size-Constrained Tree Decompositions ⋆

Tree-Decompositions are the corner-stone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms based on tree-decompositions is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this report, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. More precisely, we focus on the following problem: given a fixed k ≥ 1, what is the complexity of computing a tree-decomposition of width at most k with minimum size in the class of graphs with treewidth at most k? We prove that the problem is NP-complete for any fixed k ≥ 4 and polynomial for k ≤ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.

Introduction

A tree-decomposition of a graph [START_REF] Robertson | Graph minors. II. algorithmic aspects of tree-width[END_REF] is a way to represent G by a family of subsets of its vertex-set organized in a tree-like manner and satisfying some connectivity property. The treewidth of G measures the proximity of G to a tree. More formally, a tree decomposition of G = (V, E) is a pair (T, X ) where X = {X t |t ∈ V (T )} is a family of subsets, called bags, of V , and T is a tree, such that:

-t∈V (T ) X t = V ; for any edge uv ∈ E, there is a bag X t (for some node t ∈ V (T )) containing both u and v; for any vertex v ∈ V , the set {t ∈ V (T )|v ∈ X t } induces a subtree of T .

The width of a tree-decomposition (T, X ) is max t∈V (T ) |X t | -1 and its size is order |V (T )| of T . The treewidth of G, denoted by tw(G), is the minimum width over all possible tree-decompositions of G.

If T is constrained to be a path, (T, X ) is called a path-decomposition of G. The pathwidth of G, denoted by pw(G), is the minimum width over all possible path-decompositions of G.

Tree-Decompositions are the corner-stone of many dynamic programming algorithms for solving graph problems. As an example, the famous Courcelle's Theorem states that any problem expressible in MSOL can be solved in linear-time in the class of bounded treewidth graphs [START_REF] Courcelle | The monadic second-order logic of graphs. i. recognizable sets of finite graphs[END_REF]. Another framework based on graph decompositions is the bi-dimensionality theory that allowed the design of sub-exponential-time algorithms for many problems in the class of graphs excluding some fixed graph as a minor (e.g., [START_REF] Demaine | The bidimensionality theory and its algorithmic applications[END_REF]). Given a tree-decomposition with width w and size n, the time-complexity of most of such dynamic programming algorithms can be expressed as O(2 w n) (or O(2 w log w n) in the case of global problems). Therefore, the problem of computing tree-decompositions with small width has drawn much attention in the last decades. It has been extensively studied and investigated from different angles: parametrized complexity, exact or approximation algorithms.

The above mentioned algorithms have mainly a theoretical interest because, on the one hand, their time-complexity exponential depends on the treewidth of graphs and, on the other hand, as far as we know, no practical algorithm exists that computes a "good" tree-decomposition for graphs with treewidth at least 5. However, in case of small (≤ 4) treewidth graphs, efficient (i.e., practical) algorithms exist to compute tree-decompositions with optimal width. Moreover, in such case, the time-complexity of above-mentioned dynamic programming algorithms becomes dominated by the size of the tree-decompositions and, therefore, it becomes interesting to minimize it.

In report, we study the problem of computing tree-decompositions with minimum size. Obviously, if the width is not constrained, then the problem is trivial since there always exists a tree-decomposition of a graph with one bag (the full vertex-set). Hence, given a graph G and an integer k ≥ tw(G), we consider the problem of minimizing the size of a tree-decomposition of G with width at most k. Related Work. The problem of computing "good" tree-decompositions has been extensively studied. Computing optimal tree-decomposition -i.e., with width tw(G) -is NP-complete in the class of general graphs G [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF]. For any fixed k ≥ 1, Bodlaender designed an algorithm that computes, in time O(k k 3 n), a tree-decomposition of width k of any n-node graph with treewidth at most k [3]. Very recently, a single-exponential (in k) algorithm has been proposed that computes a tree-decomposition with width at most 5k in the class of graphs with treewidth at most k [4]. As far as we know, the only practical algorithms for computing optimal tree-decompositions hold for graphs with treewidth at most 1 (trivial since tw(G) = 1 if and only if G is a tree), 2 (graphs excluding K 4 as a minor) [START_REF] Wald | Steiner trees, partial 2-trees, and minimum ifi networks[END_REF], 3 [2,[START_REF] Kajitani | Characterization of partial 3-trees in terms of three structures[END_REF][START_REF] Matousek | Algorithms finding tree-decompositions of graphs[END_REF] and 4 [START_REF] Sanders | On linear recognition of tree-width at most four[END_REF].

We are not aware of any work dealing with the computation of tree-decompositions with minimum size. In [START_REF] Dereniowski | Minimum length path decompositions[END_REF], Dereniowski et al. consider the problem of size-constrained path-decompositions. Given any positive integer k and any graph G with pathwidth at most k. Let l k (G) denote the smallest size (length) of a path-decomposition of G with width at most k. For any fixed k ≥ 4, computing l k is NP-complete in the class of general graphs and it is NP-complete, for any fixed k ≥ 5, in the class of connected graphs [START_REF] Dereniowski | Minimum length path decompositions[END_REF]. Moreover, computing l k can be solved in polynomial-time in the class of graphs with pathwidth at most k for any k ≤ 3. Finally, the "dual" problem is also hard: for any fixed s ≥ 2, it is NP-complete in general graphs to compute the minimum width of a tree-decomposition with size s [8] 6 . Our results. Let k be any positive integer and G be any graph. If tw(G) > k, let us set s k (G) = ∞. Otherwise, let s k (G) denote the minimum size of a tree-decomposition of G with width at most k. See a simple example in Fig. 1. We first prove in Section 2 that, for any (fixed) k ≥ 4, the problem of computing s k is NP-hard in the class of graphs with treewidth at most k. Moreover, the computation of s k for k ≥ 5 is NP-hard in the class of connected graphs with treewidth at most k. Furthermore, the computation of s 4 is NP-complete in the class of planar graphs with treewidth 3. In Section 3, we present a general approach for computing s k for any k ≥ 1. In the rest of the report, we prove that computing s 2 can be solved in polynomial-time. Finally, we prove that s 3 can be computed in polynomial time in the class of trees and 2-connected outerplanar graphs.

(G) = 4, s2(G) = s3(G) = 2, s k>3 (G) = 1.

NP-hardness in the class of bounded treewidth graphs

In this section, we prove that: Theorem 1. For any fixed integer k ≥ 4 (resp., k ≥ 5), the problem of computing s k is NP-complete in the class of graphs (resp., of connected graphs) with treewidth at most k.

Note that the corresponding decision problem is clearly in NP. Hence, we only need to prove it is NP-hard. Our proof mainly follows the one of [START_REF] Dereniowski | Minimum length path decompositions[END_REF] for size-constrained path-decompositions. Hence, we recall here the two steps of the proof in [START_REF] Dereniowski | Minimum length path decompositions[END_REF]. First, it is proved that, if computing l k is NP-hard for any k ≥ 1 in general graphs, then the computation of l k+1 is NP-hard in the class of connected graphs. Second, it is shown that computing l 4 is NP-hard in general graphs with pathwidth 4. In particular, this implies that computing l 5 is NP-hard in the class of connected graphs with pathwidth 5. The second step consists of a reduction from the 3-PARTITION problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] to the one of computing l 4 . Precisely, for any instance I of 3-PARTITION, a graph G I is built such that I is a YES instance if and only if l 4 (G I ) equals a defined value ℓ I .

Our contribution consists first in showing that the first step of [START_REF] Dereniowski | Minimum length path decompositions[END_REF] directly extends to the case of tree-decompositions. That is, it directly implies that, if computing s k is NP-hard for some k ≥ 4 in general graphs, then so is the computation of s k+1 in the class of connected graphs. Our main contribution of this section is to show that, for the graphs G I built in the reduction proposed in [START_REF] Dereniowski | Minimum length path decompositions[END_REF], any tree-decomposition of G I with width at most 4 and minimum size is a path decomposition. Hence, in this class of graphs, l 4 = s 4 and, for any instance I of 3-PARTITION, I is a YES instance if and only if s 4 (G I ) equals a defined value ℓ I . We describe the details in what follows.

Lemma 1. If the problem of computing s k for an integer k ≥ 1 is NP-complete in general graphs, then the computation of s k+1 is NP-complete in the class of connected graphs.

Proof. Let G be any graph. We construct an auxiliary connected graph G ′ from G by adding a vertex a adjacent to all vertices in V (G). Given two integers k, s ≥ 1, in the following, we prove that there is a tree decomposition of G with width at most k and size at most s if and only if there is a tree decomposition of G ′ with width at most k + 1 and size at most s.

First, assume that (T, X ) is a tree decomposition of G with width at most k and size at most s. Add a in each bag of X . Then we obtain a tree decomposition of G ′ with width at most k + 1 and size at most s.

Now let (T ′ , X ′ ) be a tree decomposition of G ′ with width at most k + 1 and size at most s. We are going to find a tree decomposition of G with width at most k and size at most s. Let X a be the set of all bags in X ′ containing a. Let T a be the subtree of T ′ induced by the bags in X a . Every vertex v ∈ V (G) is contained in a bag in X a because va ∈ E(G ′ ). For any edge uv ∈ E(G), there is a bag X ⊇ {a, u, v} in X ′ since {a, u, v} induces a clique in G ′ . So X ∈ X a . Delete a in each bag of X a and denote by X -the obtained set of bags. So (T a , X -) is a tree decomposition of G with width at most k and size at most s.

Before doing the reduction from the 3-PARTITION problem to the problem of computing s 4 , let us first recall its definition.

Definition 1. [3-PARTITION]

Instance: A multiset S of 3m positive integers S = (w 1 , . . . , w 3m ) and an integer b. Question: Is there a partition of the set {1, . . . , 3m} into m sets S 1 , . . . , S m such that i∈Sj w i = b for each j = 1, . . . , m?

This problem is NP-complete even if |S j | = 3 for all j = 1, . . . , m [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Given an instance of 3-PARTITION, in the following, we construct a disconnected graph G(S, b) as in [START_REF] Dereniowski | Minimum length path decompositions[END_REF]. First, for each i ∈ {1, . . . , 3m}, we construct a connected graph H i as follows. Take w i copies of K 3 , denoted by K i,q 3 , q = 1, . . . , w i , and w i -1 copies of K 4 , denoted by K i,q 4 , q = 1, . . . , w i -1 (the copies are mutually disjoint). Then for each q = 1, . . . , w i -1, we identify two different vertices of K i,q 4 with a vertex of K i,q 3 and with a vertex of K i,q+1

3

, respectively. This is done in such a way that each vertex of each K i,q 3 is identified with at most one vertex from other cliques. Informally the cliques form a 'chain' in which the cliques of size 3 and 4 alternate. See Figure 2(a) for an example of H i where w i = 3.

Second, we construct a graph H m,b as follows. Take m + 1 copies of K 5 , denoted by K 1 5 , . . . , K m+1

5

, and m copies of the path graph P b of length b (P b has b edges and b + 1 vertices), denoted by P 1 b , . . . , P m b . (Again, the copies are taken to be mutually disjoint.) Now, for each j = 1, . . . , m, identify one of the endpoints of P j b with a vertex of

3 i,1 K 3 i,2 K 3 i,3 K 4 i,1 K 4 i,2 K (a)
Hi, where wi = 3. K j 5 , and identify the other endpoint with a vertex of K j+1

5

. Moreover, do this in a way that ensures that, for each j, no vertex of K j 5 is identified with the endpoints of two different paths. See Figure 2(b) for an example of H 2,4 . Let G(S, b) be the graph obtained by taking the disjoint union of the graphs H 1 , . . . , H 3m and the graph H m,b . In the following, we prove that there is a tree decomposition of G(S, b) of width 4 and size at most s = 1 -2m + 2 3m i=1 w i if and only if there is a partition of the set {1, . . . , 3m} into m sets S 1 , . . . , S m such that i∈Sj w i = b for each j = 1, . . . , m in the instance of 3-PARTITION.

In Lemma 2.2 of [START_REF] Dereniowski | Minimum length path decompositions[END_REF], a path decomposition of G(S, b) of width 4 and length 1 -2m + 2 3m i=1 w i is constructed if there is a partition of the set {1, . . . , 3m} into m sets S 1 , . . . , S m such that i∈Sj w i = b for each j = 1, . . . , m in the instance of 3-PARTITION. Obviously, this path decomposition is also a tree decomposition of G(S, b) of width 4 and size s. So we have the following lemma. Proof. Lemma 2.6 in [START_REF] Dereniowski | Minimum length path decompositions[END_REF] proved that if G(S, b) has a path decomposition (T, X ) of width at most 4 and length at most 1 -2m + 2 3m i=1 w i , then there is a partition of the set {1, . . . , 3m} into m sets S 1 , . . . , S m such that i∈Sj w i = b for each j = 1, . . . , m. So it is enough to prove that any tree decomposition (T, X) of G(S, b) of width at most 4 and size at most s = 1 -2m + 2 3m i=1 w i is a path decomposition of G(S, b). As proved in Lemma 2.3 of [START_REF] Dereniowski | Minimum length path decompositions[END_REF], each bag in (T, X) contains exactly one of the cliques K i,q 3 , K i,q 4 , K j 5 . Indeed, each of these cliques has size at least 3. Moreover, any two of them share at most one vertex, and no two cliques of size 3 (K i,q

3 ) share a vertex. So each bag of (T, X ) contains at most one of the cliques K i,q 3 , K i,q 4 , K j 5 . However, for any clique, there is a bag in (T, X ) containing its vertices. Since s equals the number of the cliques K i,q 3 , K i,q 4 , K j 5 , each bag of (T, X ) contains exactly one of them.

Moreover let us prove that any edge in K i,q 4 , K j 5 , P j b (i.e. both the two endpoints of the edge) is contained in exactly one bag. Since each bag in (T, X) contains exactly one of the cliques K i,q 3 , K i,q 4 , K j 5 , the two endpoints of any edge in the paths P 1 b , . . . , P m b are contained in a bag containing some K i,q 3 . (The bags containing a K i,q 4 (resp., K j 5 ) cannot add another two vertices (resp., one vertex) since (T, X ) is a tree decomposition of width at most 4.) Every bag containing some K i,q

3 contains at most one edge in the paths P 1 b , . . . , P m b , because the bag can add at most another two vertices and any K i,q 3 and P j b are disjoint. There are mb edges in the paths P 1 b , . . . , P m b and there are mb bags containing some K i,q 3 , so every bag containing a K i,q 3 contains exactly one edge in the paths P 1 b , . . . , P m b . So any edge in the paths P 1 b , . . . , P m b is contained in exactly one bag. Also each bag containing some K i,q 3 contains 5 vertices, so it does not contains any edge (i.e. both its two endpoints) in K i,q 4 or K j 5 . Therefore, any edge on K i,q 4 , K j 5 is contained in exactly one bag. Now we prove that there are only two leaves in T and so T is a path. If a bag containing some K i,q 3 and an edge uv on some path P j b is a leaf bag in T , then its neighbor bag also contains u, v because both u and v are incident to other edges in G(S, b). This is a contradiction with any edge (its two endpoints) on P j b are contained only in one bag. So any bag containing some K i,q 3 is not a leaf bag in T . Similarly, we can prove that any bag containing any K i,q 4 or K j 5 for 1 < j < m + 1 is not a leaf bag in T . Thus there are only two bags containing K 1 5 and K m+1 5 are leaves in T .

Then we get the following corollary.

Corollary 1. It is NP-complete to compute s 4 in the class of graphs of treewidth at most 4.

Theorem 1 follows from Lemma 1 and Corollary 1.

We furthermore modify the reduction to prove theorem 2.

Theorem 2. It is NP-complete to compute s 4 in the class of planar graphs of treewidth at most 3.

Proof. As in the previous reduction, we build a graph G(S, b) for an instance of 3-PARTITION; we keep the subgraphs H i as they are and modify the graph H m,b as follows. We replace the m+1 copies of K 5 by m+1 copies of the graph F that consists of a K 4 and a K 3 sharing an edge as depicted in Figure 3(a). We denote the copies by F 1 , F 2 , . . . , F m+1 . The new graph G(S, b) we obtain is planar and has treewidth 3. Lemma 2 is still true and for 3 to be correct we need to prove that if G(S, b) has a tree decomposition (T, X ) of width at most 4 and size at most s = 1 -2m + 2 3m i=1 w i , then there is a bag of (T, X ) containing F i , for each F i , i ∈ 1, . . . , m + 1. Let us denote by K i 3 and K i 4 the two cliques sharing exactly one edge that form F i . Each of these cliques, should appear in one bag. Note that among all the cliques of G(S, b), the only cliques that can coexist in a bag are of the form K i 3 and K i 4 since the sum of the number of vertices of any other two cliques is more than 5. Let us suppose that there exists j ∈ 1, . . . , m + 1 such that no bag of (T, X ) contains F j , i.e. K j 3 and K j 4 are not in the same bag. In this case the number of bags of (T, X ) is at least the number of the cliques K i,q 3 , K i,q 4 , K i ′ 4 (i ′ = j), plus the two bags containing K j 3 and K j 4 . This gives a size of at least 2 -2m + 2 3m i=1 w i wich is not possible.

Notations and preliminaries

In this section, we present the definitions and notations used throughout the report and some well-known facts about tree-decompositions.

Notations

Given a graph G = (V, E), for any S ⊆ V , For an integer c ≥ 0, a graph G = (V, E) is c-connected if |V | > c and no subset V ′ ⊆ V with |V ′ | < c is a separator in G. A 2-connected component of G is a maximal 2-connected subgraph.
Let (T, X ) be any tree-decomposition of G. Abusing the notations, we will identify a node t ∈ V (T ) and its corresponding bag X t ∈ X . This means that, e.g., instead of saying

t ∈ V (T ) is adjacent to t ′ ∈ V (T ) in T , we can also say that X t ∈ X is adjacent to X t ′ ∈ X in T . A bag B ∈ X is called a leaf-bag if B has degree one in T . Let k ≥ 1 and G be a graph with tw(G) ≤ k. A subset B ⊆ V (G) is a k-potential-leaf if there is a tree-decomposition (T, X ) with width at most k and size s k (G) such that B is a leaf bag of (T, X ). A subgraph H ⊆ V is a k-potential- leaf of G if V (H) is a k-potential-leaf of G.
Note that a k-potential-leaf has size at most k + 1. Given a class of graphs C and integer k ∈ N * , a set of graphs P is called a complete set of k-potential-leaves of C, if for any graph G ∈ C, there exists a graph

H ∈ P such that H is a k-potential-leaf of G.
A tree-decomposition is reduced if no bag is contained in another one. It is straightforward that, in any leaf-bag B of reduced tree-decomposition, there is v ∈ V such that v appears only in B and so N [v] ⊆ B. Note that it implies that any reduced tree-decomposition has at most n -1 bags.

In the following we define two transformation rules, that take a tree-decomposition (T, X ) of a graph G, and computes another one without increasing the width nor the size.

Leaf. Let X ∈ X and N T (X) = {X 1 , • • • , X d }. Assume that, for any 1 < i ≤ d, X i ∩ X ⊆ X 1 . Let (T * , X * ) =
Leaf (X, X 1 , (T, X )) denote the tree-decomposition of G obtained by replacing each edge X i X ∈ E(T ) by an edge X i X 1 for any 1 < i ≤ d. Note that X becomes a leaf-bag after the operation. See in Fig. 4.

Reduce. Let XX ′ ∈ E(T ) with X ⊆ X ′ . Let (T * , X * ) = Reduce(X, X ′ , (T, X )) denote the tree-decomposition
of G obtained by deleting the bag X from the tree-decomposition Leaf (X, X ′ , (T, X )). Note that the size of the tree decomposition is decreased by one after the operation.

From any tree-decomposition of G with width k and size s, it is easy to obtain a reduced tree-decomposition of G with width at most k and size at most s -1 by applying the Reduce operation while it is possible (i.e., while a bag is contained in another one). In particular, any minimum size tree decomposition is reduced.

1 X 2 X d X X 1 T 2 T d T 1 X 2 X d X X 1 T 2 T d T ➡ ( T, X ) ( T*, X*) Fig. 4. In a tree decomposition (T, X ), NT (X) = {X1, • • • , X d } and for any 1 < i ≤ d, Xi ∩ X ⊆ X1. For 1 ≤ i ≤ d, Ti ∪ Xi induces the subtree containing Xi in T \ {XXi}.
Replace each edge XiX ∈ E(T ) by an edge XiX1 for any 1 < i ≤ d. This gives a tree decomposition (T * , X * ) = Leaf (X, X1, (T, X )). X is a leaf-bag in (T * , X * ).

We conclude this section by a general lemma on tree-decompositions. This lemma is known as folklore, we recall it for completness. Lemma 4. Let (T, X ) be a tree decomposition of a graph G. Let X ∈ X and v, w ∈ X. If there exists a connected component in G \ X containing a neighbor of v and a neighbor of w, then there is a neighbor bag of X in (T, X ) containing v and w.

Proof. First, let us note that, for any connected subgraph H of G, the set of bags of T that contain a vertex of H induces a subtree of T (the proof is easy by induction on |V (H)|).

Let C be a connected component in G \ X containing a neighbor of v and a neighbor of w. By above remark, let T ′ C be the subtree of T induced by the bags that contain some vertex of C. Moreover, because no vertices of C are contained in the bag X, then

T ′ C is a subtree of T \ X. Let T C be the connected component of T \ X that contains T ′ C . Let Y ∈ V (T C ) be the bag of T C which is a neighbor of X in T . Let x ∈ N (v) ∩ C be a neighbor of v in C.
Then there exists a bag Z ∈ X in T C containing both x and v. So both X and Z contain vertex v. Then the bag Y , which is on the path between X and Z in T , also contains v. Similarly, we can prove that w ∈ Y .

Corollary 2. Let (T, X ) be a tree decomposition of a 2-connected graph G. Let X ∈ X and |X| ≤ 2. Then there is a neighbor bag Y of X in (T, X ) such that X ⊆ Y . Proof. Since G is 2-connected, |V (G)| ≥ 3. So there exist at least another bag except X in X . If |X| = 1, let X = {v}. Then there is a neighbor bag Y of X containing v, since G is 2-connected and v is adjacent to some vertices in G. So X ⊆ Y .
Otherwise X = 2 and let X = {v, w}. Let G 1 be any connected component in G \ X. If v is not adjacent to any vertex in G 1 , then {w} separates V (G 1 ) from {v}. It contradicts with the assumption that G is 2-connected. So any connected component in G \ X containing a neighbor of v and a neighbor of w. From Lemma 4, there is a neighbor bag Y of X containing v, w, i.e. X ⊆ Y .

General approach

In what follows, we propose polynomial-time algorithms to compute minimum-size tree-decompositions of graphs with small treewidth. Our algorithms mainly use the notion of potential-leaf.

Let k ≥ 1 and G = (V, E) be a graph with tw(G) ≤ k. The key idea of our algorithms is to identify a finite complete set of potential-leaves. Then, our algorithms are recursive: given a graph G and a k-potential-leaf H from the complete set, we compute a minimum-size tree-decomposition of G by adding H to a minimum-size treedecomposition of a smaller graph.

The next lemmas formalize the above paragraph.

Lemma 5. Let k ≥ 1 and G = (V, E) be a graph with tw(G) ≤ k. Let B ⊆ V be a k-potential-leaf of G. Let S ⊂ B be the set of vertices of B that have a neighbor in V \ B. Then s k (G) = s k (G S \ (B \ S)) + 1. Proof. Let us first prove s k (G) ≤ s k (G S \ (B \ S)) + 1.
Suppose that (T S , X S ) is a minimum size tree decomposition of width at most k of the graph G S \ (B \ S). Then there exists a bag X ∈ X S containing S because S induces a clique in the graph G S \ (B \ S). So add the bag B and make it adjacent to X in the tree decomposition (T S , X S ).

Then we obtain a tree decomposition of width at most k for graph

G of size s k (G S \ (B \ S)) + 1. Now we prove that s k (G) ≥ s k (G S \ (B \ S)) + 1. Let (T, X ) be a minimum size tree decomposition of G of width at most k such that B is a leaf bag in it. Note that, if B = V then G S \ (B \ S)
is the empty graph. Let us assume that B ⊂ V . Then (T, X ) is also a tree decomposition of G S . Let B be adjacent to the bag Y in (T, X ). Then S ⊂ Y since each vertex in S is contained in another bag in (T, X ). Let (T ′ , X ′ ) be the tree decomposition obtained by deleting the vertices in B \ S in all the bags of (T, X ). Then B is changed to B ′ = S ∈ X ′ and let Y be changed to

Y ′ ∈ X ′ . So B ′ ⊆ Y ′ . Then the tree decomposition Reduce(B ′ , Y ′ , (T ′ , X ′ )) is a tree decomposition of G S \ (B \ S) of size s k (G) -1. So s k (G) -1 ≥ s k (G S \ (B \ S)).
This lemma implies the following corollary: Corollary 3. Let k ∈ N * and C be the class of graphs with treewidth at most k. If there is a g(n)-time algorithm A k that, for any n-vertex-graph G ∈ C, computes a k-potential-leaf of G. Then s k can be computed in O(g(n) • n) time in the class of n-vertex graphs in C. Moreover, a minimum size tree decomposition of width at most k can be constructed in the same time.

Proof. Let G ∈ C be a n-vertex-graph. Let us apply Algorithm A k to find a subgraph H of G in g(n) time, which is a k-potential-leaf of G. Let S ⊂ V (H) be the set of vertices having a neighbor in G \ H and G ′ = G S \ (V (H) \ S). Then, by Lemma 5, s k (G) = s k (G ′ ) + 1. Finally, |V (G ′ )| ≤ n -1 and G ′ has treewidth at most k. We then proceed recursively. So the total time complexity is O(g(n) • n). Moreover, for any minimum size (s k (G ′ )) tree decomposition (T ′ , X ′ ) of G ′ of width k, there is a bag X containing S since S induces a clique in G ′ . Add a new bag N = V (H) adjacent to X in (T ′ , X ′ ). The obtained tree decomposition is a minimum size (s k (G) = s k (G ′ ) + 1) tree decomposition of G of width at most k.

Graphs with treewidth at most 2

In this section, we describe algorithm A 2 computes a 2-potential-leaf of a given graph. In particular, all graphs considered in this section have treewidth at most 2, i.e. partial 2-trees. Please see a complete set of 2-potential-leaf of graphs of treewidth at most 2 in Fig. 5. We are going to prove that any of the subgraphs in Fig. 5 is a potential-leaf and then that each non-empty graph of treewidth at most 2 contains one of them as a 2-potential-leaf. Proof. Let (T, X ) be any tree-decomposition of G with width at most 2 and size at most s ≥ 1. We show how to modify it to obtain a tree-decomposition with width at most 2 and size at most s and in which {f, p, q} is a leaf bag. Since f p ∈ E(G), there is a bag B in (T, X ) containing both f and p. We may assume that B is the single bag containing f (otherwise, delete f from any other bag). Similarly, since pq ∈ E(G), let X be a bag in (T, X ) containing both p and q.

First, let us assume that X = B = {f, p, q}. In that case, we may assume that X is the single bag containing p (otherwise, delete p from any other bag). If X is a leaf bag, then the lemma is proved. Otherwise, let X 1 , • • • , X d be the neighbors of X in T . Since f and p appear only in X, then X ∩ X i ⊆ {q} for any 1 ≤ i ≤ d. If there is 1 ≤ i ≤ d such that q ∈ X i , let us assume w.l.o.g., that q ∈ X 1 . By definition of the operation Leaf , the tree-decomposition Leaf (X, X 1 , (T, X )) has width at most 2, same size as (T, X ), and X is a leaf.

Second, consider the case when X = B. There are two cases to be considered. Either B = {f, p} or B = {f, p, x} with x = q. In the latter case, note that there is another bag B ′ , neighbor of B, that contains x unless x is an isolated vertex of G. In the former case or if x appears only in B (in which case, x is an isolated vertex), let B ′ be any neighbor of B. Let (T ′ , X ′ ) be obtained by deleting f, p in all bags of (T, X ). Then, contract the edge BB ′ in T ′ , i.e., remove B and make any neighbor of B adjacent to B ′ . Note that, in the resulting tree-decomposition of G \ {f, p}, there is a bag X ′ containing q and with |X ′ | ≤ 2 (the bag that results from X). Finally, add a bag {f, p, q} adjacent to X ′ and, if node x was only in B, then add x to X ′ . The result is the desired tree-decomposition. Lemma 7. Let G be a graph with treewidth at most 2 and q ∈ V (G) such that q has at least two one-degree neighbors f and p (see in Fig. 5(b)). Then {f, p, q} is a 2-potential-leaf of G.

Proof. Let (T, X ) be any tree-decomposition of G with width at most 2 and size at most s ≥ 1. We show how to modify it to obtain a tree-decomposition with width at most 2 and size at most s and in which {f, p, q} is a leaf bag.

Since f q ∈ E(G), there is a bag B in (T, X ) containing both f and q. We may assume that B is the single bag containing f (otherwise, delete f from any other bag). Similarly, since pq ∈ E(G), let X be a bag in (T, X ) containing both p and q. Again, we may assume that X is the single bag containing p (otherwise, delete p from any other bag).

First, let us assume that X = B = {f, p, q}. If X is a leaf bag, then the lemma is proved. Otherwise, let X 1 , • • • , X d be the neighbors of X in T . Since f and p appear only in X, then X ∩ X i ⊆ {q} for any 1 ≤ i ≤ d. If there is 1 ≤ i ≤ d such that q ∈ X i , let us assume w.l.o.g., that q ∈ X 1 . By definition of the operation Leaf , the tree-decomposition Leaf (X, X 1 , (T, X )) has width at most 2, same size as (T, X ), and X is a leaf.

Second, let us assume that X = {f, q} or B = {p, q}. In the former case, remove p from any bag and add p to X. In the latter case, remove f from any bag and add f to B. In both cases, we get a bag {f, p, q} as in the first case.

Otherwise, let B = {f, q, x}, x = p, and X = {p, q, y}, y = f .

-If B and X are adjacent in T , then add a new bag N = {q, x, y}; remove B and X and make each of their neighbors adjacent to the new bag N and, finally, add a leaf-bag {f, p, q} adjacent to N . See in Fig. 6(a). The obtained tree-decomposition has the desired properties.

-Otherwise, if there is a neighbor B ′ of B with q, x ∈ B ′ , then remove B, make all neighbors of B adjacent to B ′ and finally add a leaf-bag {f, p, q} adjacent to X. The obtained tree-decomposition has the desired properties. -Otherwise, let B ′ be the neighbor of B on the path between B and X. In this case, q ∈ B ′ and x / ∈ B ′ . Moreover, q does not belong to any neighbor of B that contains x and the other way around: x does not belong to any neighbor of B that contains q. For any neighbor Y of B with q ∈ Y (and hence x / ∈ Y ), replace the edge Y B ∈ E(T ) with the edge Y B ′ . Finally, replace the edge BB ′ ∈ E(T ) by the edge BX. See in Fig. 6(b). In the resulting tree-decomposition of G, B and X are adjacent and we are back to the first item.

B X 1 T 2 T ➡ q,p,y f,q,x f,p,q N 1 T 2 T q,x,y
(a) In the tree decomposition (T, X ), let T1 ∪ B (resp. T1 ∪ B) induce the subtree containing B (resp. X) in T \{BX}. Delete B and X and make each of their neighbors adjacent to the new bag N = {q, x, y}; and add a leaf-bag {f, p, q} adjacent to N .

B X ➡ q,p,y f,q,x Y q,... q,... B' B X
q,p,y f,q,x Y q,... q,...

B'

x,... Lemma 8. Let G be a graph with treewidth at most 2 and q ∈ V (G) such that q has one neighbor f with degree 1 and for any vertex w ∈ N (q) \ {f }, {w, q} belongs to a 2-connected component of G.

If G has an isolated vertex α, then {q, f, α} is a 2-potential-leaf; otherwise {q, f } is a 2-potential-leaf (see in Fig. 5(c)).

Proof. Let (T, X ) be any tree-decomposition of G with width at most 2 and size at most s ≥ 1. We show how to modify it to obtain a tree-decomposition with width at most 2 and size at most s and in which {f, q, α} is a leaf bag if G has an isolated vertex α; and otherwise {f, q} is a leaf bag.

Since f q ∈ E(G), there is a bag B in (T, X ) containing both f and q. We may assume that B is the single bag containing f (otherwise, delete f from any other bag).

1. If B = {f, q}, then the intersection of B and any of its neighbor in T is empty or {q}. If there is a neighbor of B containing q, then let X be such a neighbor; otherwise let X be any neighbor of B. By definition of the operation Leaf , the tree-decomposition Leaf (B, X, (T, X )) has width at most 2, same size as (T, X ), and B is a leaf. If there are no isolated vertices, we are done. Otherwise, if there is an isolated vertex α in G, then delete α in all bags of the tree-decomposition Leaf (B, X, (T, X )) and add α to bag B, i.e. make B = {f, p, α}. The result is the desired tree decomposition. 2. Otherwise let B = {f, q, x}.

(a) If x is a neighbor of q, then x and q are in a 2-connected component of G. So there exists a connected component in G \ B containing a vertex adjacent to x and a vertex adjacent to q. From Lemma 4, there is a neighbor X of B in (T, X ) containing both x and q. Then by definition of the operation Leaf , the treedecomposition Leaf (B, X, (T, X )) has width at most 2, same size as (T, X ), and B is a leaf. Then delete x in B, i.e. B = {f, q}. Finally, if α is an isolated vertex of G, remove it to any other bag and add it to B. The result is the desired tree decomposition. (b) Otherwise x is not adjacent to q. If there is a neighbor X of B in (T, X ) containing both x and q, then (T, X ) is modified as in case 2a. Otherwise, any neighbor of B in (T, X ) contains at most one of q and x.

If there is a neighbor of B in T containing q, then let Y be such a neighbor of B; otherwise let Y be any neighbor of B. Delete the edges between B and all its neighbors not containing x except Y in (T, X ) and make them adjacent to Y . If there is no neighbor of B containing x, then x is an isolated vertex and we get a tree decomposition of the same size and width as (T, X ), in which there is a leaf bag B = {f, q, x}. It is a required tree decomposition.

Otherwise let Z be a neighbor of B in (T, X ) containing x, then delete the edges between B and all its neighbors containing x except Z in (T, X ) and make them adjacent to Z. Proof. Let G = (V, E) be a graph of treewidth at most 2. Let b ∈ V with exactly 2 neighbors a, c ∈ V satisfy the hypotheses of the lemma. If V = {a, b, c}, the result holds trivially, so let us assume that |V | ≥ 4. Let (T, X ) be a reduced tree decomposition of width at most 2 of G. From (T, X ), we will compute a tree decomposition (T * , X * ) of G without increasing the width or the size and such that {a, b, c} is a leaf-bag of (T * , X * ).

Let X be any bag of (T, X ) containing {a, b} and Y be any bag containing {b, c}. The bags X, Y exist because ab, bc ∈ E. If X = {a, b}, then there exists a connected component in G\X containing a neighbor of a and a neighbor of b. By Lemma 4, there is a neighbor of X in (T, X ) that contains both a and b, contradicting the fact that (T, X ) is reduced. So |X| = 3 and, similarly, |Y | = 3.

-Let us first assume that X = Y = {a, b, c}. In particular, it is the case when N (a) = {b, c} since {a, b, c} induces a clique. We may assume that b only belongs to bag X (otherwise, remove b from any other bag).

If N (a) = {b, c}, then we can also assume that a only belongs to X. Let Z be any neighbor of B containing c if exists; otherwise let Z be any neighbor of B (Z exists since |V | ≥ 4). Otherwise, there exists a path P between a and c in G \ {b} with at least one internal vertex. In this latter case, there exists a connected component in G \ X containing a neighbor of a and a neighbor of c. So by Lemma 4, there is a neighbor bag Z of X in (T, X ) containing both a and c. In both cases, Leaf (X, Z, (T, X )) is the desired tree-decomposition.

-Otherwise, X = {a, b, x} and Y = {b, c, y} with x = c and y = a; and there exists a path P between a and c in G \ {b} with at least one internal vertex. Let Q be the path between X and Y in (T, X ). We may assume that b only belongs to the bags in Q, because otherwise b can be removed from any other bag.

• If X is adjacent to Y , then by properties of tree-decomposition, X ∩ Y separates a and c. Since {b} does not separate a and c, X ∩ Y = {b, x}, i.e. x = y. In this case, (T * , X * ) is obtained by making X = {a, c, x} and removing Y from (T, X ), then making all neighbors of Y adjacent to X and finally, adding a bag {a, b, c} adjacent to X. • Otherwise, let X ′ be the bag in the path Q containing a, which is closest to Y . Similarly, let Y ′ be the bag in the path Q containing c, which is closest to X. Finally, let Q ′ be the path from X ′ to Y ′ in T and note that b belongs to each bag in Q ′ and a and c do not belong to any internal bag in Q ′ . Then we may assume that b only belongs to the bags in Q ′ , because otherwise b can be removed from any other bag.

If X ′ and Y ′ are adjacent in T , the proof is similar to the one in previous item. Otherwise, let Z be the neighbor of X ′ in Q ′ . By properties of tree-decompositions, X ′ ∩ Z separates a and c. Since {b} does not separate a and c, let

X ′ ∩ Z = {b, x ′ }. Since Z = {b, x ′ } because (T, X ) is reduced, then Z = {b, x ′ , z}
for some z ∈ V . Replace b with a in all the bags. By doing this (T, X ) is changed to a tree decomposition (T c , X c ) of the graph G/ab obtained by contracting the edge ab in G. In (T c , X c ), the bag X ′ has become X c = {a, x ′ } and Z is changed to be Z c = {a, x ′ , z}. So X c can be reduced in (T c , X c ). Moreover Y is changed to Y c = {a, c, y}. To conclude, let us add the bag {a, b, c} adjacent to Y c in the tree decomposition Reduce(X c , Z c , (T c , X c )). See in Fig. 8. The result is the desired tree-decomposition (T * , X * ) of G. Before going further, let us introduce some notations. A bridge in a graph G = (V, E) is any subgraph induced by two adjacent vertices u and v of G (i.e., uv ∈ E) such that the number of connected components strictly increases when deleting the edge uv, but not the two vertices u, v in G, i.e., G ′ = (V, E \ {uv}) has strictly more connected components than G. A vertex v ∈ V is a cut vertex if {v} is a separator in G. A maximal connected subgraph without a cut vertex is called a block. Thus, every block of a graph G = (V, E) is either a 2-connected component of G or a bridge or an isolated vertex. Conversely, every such subgraph is a block. Different blocks of G intersect in at most one vertex, which is a cut vertex of G. Hence, every edge of G lies in a unique block, and G is the union of its blocks.

X' Y' ➡ b,c,y' a,b,x' b,x',z Z Replace b with a in all bags Y b,c,y X a,b,x X' Y' a,c,y' a,x' a,x',z Z Y a,c
Let G = (V, E) be a connected graph and let r ∈ V . A spanning tree T of G is a BFS-tree of G if for any v ∈ V (G), the distance from r to v in G is the same as the one in T . Let B = {C : C is a block of G}. The block graph of G is the graph B(G) whose vertices are the blocks of G and two block-vertices of B(G) are adjacent if the corresponding blocks intersect, that is,

B(G) = (B, {C 1 C 2 : C 1 , C 2 ∈ B and C 1 ∩ C 2 = ∅}). Note that B(G) is connected.
Finally, a block-tree of G is any BFS-tree F (with any arbitrary root) of B(G). See an example in Fig. 9.

There is a linear (in the number of edges) algorithm for computing all blocks in a given graph [START_REF] Hopcroft | Algorithm 447: efficient algorithms for graph manipulation[END_REF]. Also a BFS-tree can be found in linear (in the number of vertices plus the number of edges) time. So given a graph G = (V, E), we can compute a block tree

F of G in O(|V | + |E|) time.
Now we are ready to prove next theorem by using the Lemmas 6-9. . This graph G is an induced subgraph of the graph in Fig. 9. Its block tree F , with root C1, has two blocks less than the one in Fig. 9 (the blocks C6 and C10). All leaf blocks, C7, C8, C9, C11, in F contains two vertices of G.

let us first assume that C is a bridge in G, i.e. C consists of one edge f p ∈ E(G) and p is a cut vertex. Then f has degree one in G because C is a leaf block in F . Let P be the parent block of C in F . Then any child block A of P in F consists of one edge because C has the maximum number of vertices among all the children of P ; and A is a leaf block in F because C is a furthest leaf from the root block R. Proof. Let G be any graph. It can be checked in polynomial-time whether tw(G) ≤ 2 (e.g. see [START_REF] Wald | Steiner trees, partial 2-trees, and minimum ifi networks[END_REF]). If tw(G) > 2, then s 2 = ∞. Otherwise tw(G) ≤ 2, then the result follows from Theorem 3 and Corollary 3.

5 Minimum-size tree-decompositions of width at most 3

In this section, we study the computation of s 3 in the class of trees and 2-connected outerplanar graphs.

computation of s 3 in trees

In this subsection, given a tree G, we show how to find a 3-potential-leaf in G. We characterize a complete set of 3-potential-leaves of trees in Fig. 11. We first prove that each of the subgraphs in Fig. 11 is a 3-potential-leaf and then that any tree with at least four vertices contains one of them. Lemma 12 in Lemma 13 in Lemma 14 in Lemma 15 in Lemma 16 Proof. Let (T, X ) be any reduced tree decomposition of width at most 3 and size at most s ≥ 1 of G. We show how to modify it to obtain a tree-decomposition with width at most 3 and size at most s and in which {f, p, g, f ′ } is a leaf bag.

g g h G p (a) p f g f p G G G (b) (c) (d) (e) ' f g f p G ' f p f f ' f '' f see in
From Lemma 11, we can assume that there is a bag B in (T, X ) containing all f, p, g. We may assume that B is the single bag containing f, p (otherwise, delete f, p from any other bag). Since gf ′ ∈ E(G), let Y be a bag in (T, X ) containing both f and g. We may assume that Y is the single bag containing f ′ (otherwise, delete f ′ from any other bag).

- Proof. Let (T, X ) be any reduced tree decomposition of width at most 3 and size at most s ≥ 1 of G. We show how to modify it to obtain a tree-decomposition with width at most 3 and size at most s and in which {f, p, g, f ′ } is a leaf bag.

If B = Y = {f, p, g, f ′ },
From Lemma 11, we can assume that there is a bag B in (T, X ) containing all f, p, g. We may assume that B is the single bag containing f, p (otherwise, delete f, p from any other bag).

1. If B = {f, p, g}, then the intersection of B and any of its neighbor in T is contained in {g}. A desired tree decomposition can be obtained from Lemma 10. 2. Otherwise, B = {f, p, g, x}. Then the intersection of B and any of its neighbor in T is contained in {g, x}.

(a) If there is a neighbor B ′ of B such that B ∩ B ′ = {g, x}, then by definition of the operation Leaf , the tree-decomposition Leaf (B, B ′ , (T, X )) has width at most 3, same size as (T, X ), and B = {f, p, g, x} is a leaf. Then delete x in B in the tree-decomposition Leaf (B, B ′ , (T, X )) since {g, x} ⊆ B ′ . The obtained tree decomposition has the desired properties. (b) Otherwise any neighbor of B contains at most one of g and x. If x is not adjacent to g, then there is a connected component in G \ B containing a neighbor of g and a neighbor of x. From Lemma 4, there exists a neighbor bag of B in (T, X ) containing g and x. It is a contradiction. So we have x is adjacent to g in this case. i. x is a child of g. Then x has exactly one child y, which is a leaf in G since f is one of the furthest leaves from r. Since yx ∈ E(G), there is a bag Y in (T, X ) containing both y and x. We may assume that Y is the single bag containing y (otherwise, delete y from any other bag). Since {g, x} ⊂ B and any neighbor of B contains at most one of g and x, any bag except B contains at most one of g and x. Then g / ∈ Y because x ∈ Y . So y, x, g are not contained in one bag. From Lemma 11, we can modify (T, X ) to obtain a tree-decomposition (T ′ , X ′ ) of width at most 3 and size at most s having a leaf bag X = {y, x, g}. Note that x (resp. y) plays the same role as p (resp. f ) in G, i.e., g, p, f and g, x, y are symmetric in G. Hence, the result is a desired tree decomposition. ii. x is the parent of g. Let p ′ be another child of g and let f ′ be the child of p ′ , which is a leaf in G. Let B ′ be the bag in (T, X ) containing both f ′ and p ′ . We may assume that B ′ is the single bag containing f ′ (otherwise, delete f ′ from any other bag). Let X ′ be a bag containing both p ′ and g. Then we have

X ′ = B (because p ′ / ∈ B).
Since g ∈ X ′ any bag except B contains at most one of g and x, we have x / ∈ X ′ . In the following, we modify (T, X ) to obtain a tree-decomposition (T ′ , X ′ ) with width at most 3 and size at most s having a bag {f ′ , p ′ , g}. Then we are in case 1, since g, p, f and g, p ′ , f ′ are symmetric in G. If B ′ = X ′ = {f ′ , p ′ , g} then, we are done. If B ′ = X ′ = {f ′ , p ′ , g, x ′ }. Then x ′ is not x, which is the parent of g, since x / ∈ X ′ . So we can do as in case 2a or case 2(b)i. Otherwise, B ′ = X ′ . From Lemma 11, we can modify (T, X ) to obtain a tree-decomposition with width at most 3 and size at most s having a leaf bag {f ′ , p ′ , g}.

Lemma 15. Let G be a tree rooted at r ∈ V (G) and |V (G)| ≥ 4. Let f a leaf in G. Let p be the parent of f . If p has exactly two children f, f ′ in G and let g be the parent of p in G (see in Fig. 11(d

)), then H = G[{f, f ′ , p, g}] is a 3-potential-leaf of G.
Proof. Let (T, X ) be any reduced tree decomposition of width at most 3 and size at most s ≥ 1 of G. We show how to modify it to obtain a tree-decomposition with width at most 3 and size at most s and in which {f, f ′ , p, g} is a leaf bag.

Since f p ∈ E(G), there is a bag B in (T, X ) containing both f and p. We may assume that B is the single bag containing f (otherwise, delete f from any other bag). Similarly, let B ′ be the single bag in (T, X ) containing both f ′ and p. Let X be a bag containing both p and g.

= G[{p, f, f ′ , f ′′ }] is a 3-potential-leaf of G.
Proof. Let (T, X ) be any reduced tree decomposition of width at most 3 and size at most s ≥ 1 of G. We show how to modify it to obtain a tree-decomposition with width at most 3 and size at most s and in which {p, f, f ′ , f ′′ } is a leaf bag. Since f p ∈ E(G), there is a bag B in (T, X ) containing both f and p. We may assume that B is the single bag containing f (otherwise, delete f from any other bag). Similarly, let B ′ (resp. B ′′ ) be the single bag in (T, X ) containing both f ′ (resp. f ′ ) and p.

1. If B = B ′ = B ′′ = {f, f ′ , f ′′ ,
p}, then the intersection of B and any of its neighbor in T is contained in {p}. A desired tree decomposition can be obtained from Lemma 10.

Let G be any tree. If |V (G)| ≤ 4, then V (G) is a 3-potential-leaf. Let us assume that |V (G)| ≥ 5. Root G at any vertex r. Let f be one of the furthest leaves from r in G. Let p, g, h be the first three vertices on the path from f to r in G (if exist), i.e. p is f 's parent; g is p's parent; and h is g's parent in G.

-If g, p both have only one child in G, then {f, p, g, h} is a 3-potential-leaf of G from Lemma 12; -If p has only one child and g has a child f ′ , which is a leaf in G, then {f, p, g, f ′ } is a 3-potential-leaf of G from Lemma 13; -If p has only one child and any child of g has exactly one child, then {f, p, g} is a 3-potential-leaf of G from Lemma 14; -If p has only one child and there exist a child p ′ of g, which has exactly two children f 1 , f 2 , then {f 1 , f 2 , p ′ , g} is a 3-potential-leaf of G from Lemma 15; -If p has only one child and there exist a child p ′ of g, which has at least three children

f 1 , f 2 , f 3 , then {f 1 , f 2 , f 3 , p ′ }
is a 3-potential-leaf of G from Lemma 16; -If p has exactly two children f, f ′ , then {f, f ′ , p, g} is a 3-potential-leaf of G from Lemma 15; -Otherwise p has at least three children f, f ′ , f ′′ , then {f, f ′ , f ′′ , p} is a 3-potential-leaf of G from Lemma 16.

In fact, the algorithm for trees can be extended to forests by consider their connected component, i.e., trees. The only difference is in Lemma 14 the 3-potential-leaf becomes {f, p, g, α} if there is an isolated vertex α in the given forest.

Computation of s 3 in 2-connected outerplanar graphs

In this subsection, given a 2-connected outerplanar graph G, we show how to find a 3-potential-leaf in G. See a complete set of 3-potential-leaves of 2-connected outerplanar graphs in Fig. 12. We first prove that each subgraph in the Fig. 12 is a 3-potential-leaf and then we show that any 2-connected outerplanar graphs contains one of them. The following fact is well known for 2-connected outerplanar graphs.

Lemma 17. [15] A 2-connected outerplanar graph has the unique Hamilton cycle.

In the rest of this subsection, let G be a 2-connected outerplanar graph and C be the Hamilton cycle in G.

Definition 2. Any edge in E(G) \ E(C) is called a chord in G. The vertices v 1 , . . . , v j ∈ V (G), for 2 ≤ j ≤ |V (G)|, are consecutive in C ( we also say that they are consecutive in G) if v i v i+1 ∈ E(C) for 1 ≤ i ≤ j -1; and v 1 , . . . , v j ∈ V (G)
= G[{a, b, c, d}] is a 3-potential-leaf of G. respectively in C 1 ; moreover, {a 1 a 2 , a 2 a 3 } ∩ {b 1 b 2 , b 2 b 3 } = ∅. So we have either v i v j / ∈ {a 1 a 2 , a 2 a 3 } or v i v j / ∈ {b 1 b 2 , b 2 b 3 }.
In both cases (|V (C 1 )| = 3 and |V (C 1 )| ≥ 4), there is at least one bag X in (T 1 , X 1 ) containing three consecutive vertices in C 1 , denoted as x 1 , x 2 , x 3 , such that v i v j / ∈ {x 1 x 2 , x 2 x 3 }. So x 1 , x 2 , x 3 are also consecutive in C. Similarly, there is at least one bag Y in (T 2 , X 2 ) containing three consecutive vertices in C 2 , denoted as y 1 , y 2 , y 3 , such that v i v j / ∈ {y 1 y 2 , y 2 y 3 }. So y 1 , y 2 , y 3 are also consecutive in C. Finally, we have {x Proof. Let (T, X ) be any tree decomposition of width at most 3 and size at most s ≥ 1 of G. We show how to modify (T, X ) to obtain a tree-decomposition of G, which has width at most 3, size at most s and a leaf bag {a, b, c, d}.

1 x 2 , x 2 x 3 } ∩ {y 1 y 2 , y 2 y 3 } = ∅ because E(C 1 ) ∩ E(C 2 ) = {v i v j } and v i v j / ∈ {x 1 x 2 , x 2 x 3 }.
Note that the vertices of C ′ induce a cycle in G. Without confusion, we denote this cycle C ′ . Let (T ′ , X ′ ) be the tree decomposition of C ′ obtained by deleting all vertices not in C ′ in the bags of (T, X). From Lemma 20, there is either a bag containing all vertices in C ′ (only if |C ′ | = 4); or two bags X, Y containing three consecutive vertices in C ′ respectively and the two corresponding edge sets do not intersect.

In the former case, V (C ′ ) = {a, b, c, d} and so (T, X ) is also a tree decomposition of G ∪ {ac}, from Lemma 18, {a, b, c, d} is a 3-potential-leaf of G.

In the latter case, let X ⊇ {u, v, w} and ∈ {x, y}.) (T, X ) is also a tree decomposition of G ∪ {uw}, which is still an outerplanar graph by assumptions. Note that w has degree 3 in the graph G ∪ {uw}. So from Lemma 18, we can modify (T, X ) to obtain a tree-decomposition (T ′ , X ′ ) of G ∪ {uw}, which has width at most 3, size at most s and a leaf bag L containing four consecutive vertices {u, v, w, z}. Note that (T ′ , X ′ ) is also a tree decomposition of G. So we get a tree decomposition where a leaf bag contains 4 consecutive vertices of C ′ . It remains to show how to modify it to obtain a tree decomposition with a leaf bag {a, b, c, d}.

Y ⊇ {u ′ , v ′ , w ′ }, where u, v, w (resp. u ′ , v ′ , w ′ ) are consecutive in C ′ . Since {uv, vw} ∩ {u ′ v ′ , v ′ w ′ } = ∅,
Let B be the neighbor of L in T . Then u, z ∈ B since each of u, z is adjacent to some vertices in G \ L. We can assume that L is the single bag containing v, w in (T ′ , X ′ ), because otherwise we can delete them in any other bags. Thus, deleting the bag L in (T ′ , X ′ ), we get a tree decomposition (T 1 , X 1 ) of the graph G 1 , which is the graph obtained by deleting v, w and adding an edge uz in G. So (T 1 , X 1 ) has width at most 3 and size at most s-1. Note that the graph G 1 is isomorphic to the graph G 2 ≡ G∪{ad}\{b, c} since z ∈ C ′ . So from the tree decomposition (T 1 , X 1 ) of G 1 we can obtain a tree decomposition (T 2 , X 2 ) of G 2 with the same width and size. Note that since ad ∈ E(G 2 ), there is a bag Y containing both a and d. Finally, add a new bag N = {a, b, c, d} adjacent to Y in (T 2 , X 2 ). The result is a desired tree decomposition.

Lemma 22. There is an algorithm that, for any 2-connected outerplanar graph G, computes a 3-potential-leaf of G in polynomial time. In the following, let f 0 , f 1 , f 2 be the faces as in Claim 5.2. If ae ∈ E(G), then from Lemma 19, {a, b, c} is a 3-potential-leaf of G.

Otherwise, we can prove that any tree decomposition of G of width at most 3 can be modified to a tree decomposition of G ∪ {ae} with the same width and size in the following. So {a, b, c} is a 3-potential-leaf of G. Let (T, X ) be a tree decomposition of width at most 3 and size at most s ≥ 1 of G. Let (T 0 , X 0 ) be the tree decomposition obtained by deleting all vertices not in f 0 . Then (T 0 , X 0 ) is a tree decomposition of f 0 (without confusion f 0 is used to denote the face and the cycle induced by vertices in f 0 as well). From Lemma 20, there is a bag containing three consecutive vertices u, v, w in f 0 and uv, vw are edges of some faces in F. (Note that u, v, w are not consecutive in C.) So (T, X ) is also a tree decomposition of G ∪ uw. The graph G ∪ uw and the graph G ∪ ae are isomorphic. So from (T, X ) we can obtain a tree decomposition (T ′ , X ′ ) of G ∪ ae with the same width and size. Then (T ′ , X ′ ) is the desired tree decomposition.

From Lemmas 22 and Corollary 3, we obtain the following result. Corollary 6. s 3 can be computed and a minimum size tree decomposition of width at most 3 can be constructed in polynomial-time in the class of 2-connected outerplanar graphs.

Conclusion

In this report, we gave preliminary results on the complexity of minimizing the size of tree-decompositions with given width. Table 1 summarizes our results as well as the remaining open questions. We currently investigate the case of s 3 in the class of connected graphs with treewidth 2 or 3 and we conjecture it is polynomially solvable. But it is more tricky than computing s 3 in trees and 2-connected outerplanar graphs. It seems that a global view of the graph needs to be considered to decide wether a subgraph is a 3-potential-leaf of the graph. 1. Summary of the complexity results.

See an example in Fig. 14(a). In this example, G is a connected outerplanar graph. {r, a, b, c} is not a 3-potential-leaf of G, but it is a 3-potential-leaf of G \ {yw}. Let G ′ ≡ G \ {a, b, c}. Then G ′ is 2-connected outerplanar. From the algorithm of computing s 3 in 2-connected outerplanar graphs in subsection 5.2, we can compute that s 3 (G ′ ) = 5. So if {r, a, b, c} is a potential-leaf of G, then s 3 (G) = 6. But there exists a tree decomposition of G of width 3 and size 5, where the bags are {a, r, z, y}, {r, y, x, w}, {b, r, w, v}, {r, v, u, e}, {c, r, d, e}. So {r, a, b, c} is not a 3-potential-leaf of G. However, in the graph G ′′ ≡ G \ {yw}, we can prove that s 3 (G ′′ ) = 5 and there is a minimum size tree decomposition containing {r, a, b, c} as a leaf bag, i.e. {r, a, b, c} is 3-potential-leaf of G ′′ . So the existence of the edge yw, not incident to any vertex in {r, a, b, c}, changes the behavior of {r, a, b, c}. In any minimum size tree decomposition of width 5 (and size 2) of this tree, there exists a bag inducing a forest, not a subtree. For example, in a tree decomposition of width 5 and size 2, one bag is {r, a1, a2, a3, b1, b2} and the other one is {r, b2, b3, c1, c2, c3}. The problem of computing s k , for k ≥ 4, seems more intricate already in the case of trees. Indeed, our polynomialtime algorithms to compute s k , k ≤ 3, in trees mainly rely on the fact that, for any tree T , there exists a minimum-size tree-decomposition of T with width at most 3, where each bag induces a connected subtree. This is unfortunately not true anymore in the case of tree-decomposition with width 5. As an example, consider the tree G (with 10 nodes) obtained from a star with three 3 leaves by subdividing twice each edge. See in Fig. 14(b). s 5 (G) = 2 and any minimum size tree decomposition has a bag X such that G[X] is disconnected.

Fig. 1 .

 1 Fig. 1. Given a tree G with five vertices, for any k ≥ 1, a minimum size tree decomposition of width at most k is shown. So we see that s1(G) = 4, s2(G) = s3(G) = 2, s k>3 (G) = 1.

4 Fig. 2 .

 42 Fig. 2. Examples of gadgets in graph G(S, b).

Lemma 2 .

 2 Given a multiset S of 3m positive integers S = (w 1 , . . . , w 3m ) and an integer b, if there is a partition of the set {1, . . . , 3m} into m sets S 1 , . . . , S m such that i∈Sj w i = b for each j = 1, . . . , m, then G(S, b) has a tree decomposition of width at most 4 and size at most s = 1 -2m + 2 3m i=1 w i . Now we prove the other direction. Lemma 3. If G(S, b) has a tree decomposition (T, X ) of width at most 4 and size at most s = 1 -2m + 2 3m i=1 w i , then there is a partition of the set {1, . . . , 3m} into m sets S 1 , . . . , S m such that i∈Sj w i = b for each j = 1, . . . , m.

(a) F 1 F 2 F 3 F 4 1 P 4 2 P(b) H2, 4 Fig. 3 .

 123414243 Fig. 3. Example of the new gadget in G(S, b).

Fig. 5 .

 5 Fig. 5. Complete set of 2-potential-leaves of graphs of treewidth at most 2.

Fig. 6 .

 6 Fig. 6. Explanation of proof of Lemma 7.

Fig. 7 .

 7 Fig. 7. To be simple and clear, we show only the subtree induced by B, Y and another three neighbors Z, W, U of B. Y contains q; Z, U both contain x and W does not contain x. First we make the bag not containing x, e.g. W adjacent to Y instead of B; and make the bag containing x except Z, e.g. U adjacent to Z instead of B. Second, make Z adjacent to Y instead of B and delete x in B. Then B = {f, q} is a leaf-bag.

Fig. 8 .

 8 Fig.8. To be simple and clear, we show only the path from X to Y . After the two transformations, {a, b, c} is a leaf-bag.

1 C 2 C 3 C 5 C 4 C 6 C 7 C 8 C 9 C 10 C 11 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 CFig. 9 .Theorem 3 .Fig. 10

 12354678910111234567899310 Fig. 9. Graph G is connected. For i = 1, . . . , 11, each Ci is a block of G. B(G) is the block graph of G. The BFS tree of B(G) with bold edges is a block tree of G with root C1.

Fig. 11 .

 11 Fig. 11. Complete set of 3-potential-leaves of trees.

  then the intersection of B and any of its neighbor in T is contained in {g}. A desired tree decomposition can be obtained from Lemma 10. -If B = {f, p, g}, then delete f ′ in Y and add f ′ in B, then we are in the previous case. -Otherwise, B = {f, p, g, x} where x = f ′ . Then the intersection of B and any of its neighbor in T is contained in {g, x}. Let P be the path in T from B to Y . Then g is contained in all bags on P . Let B ′ be the neighbor of B on P . If B ∩ B ′ = {g, x}, then by definition of the operation Leaf , the tree-decomposition Leaf (B, B ′ , (T, X )) has width at most 3, same size as (T, X ), and B = {f, p, g, x} is a leaf. Then in the tree-decomposition Leaf (B, B ′ , (T, X )), delete f ′ in Y and remove x from B and add f ′ to B, i.e. make B = {f, p, g, f ′ }. The obtained tree decomposition has the desired properties since {g, x} ⊆ B ′ . Otherwise B ∩ B ′ = {g}. Delete f ′ from the bag Y and add x in Y ; delete x from B and add f ′ in B, i.e., make B = {f, p, g, f ′ }; finally make all neighbors of B except B ′ adjacent to Y since now {g, x} ⊆ Y . The result is the desired tree decomposition. Lemma 14. Let G be a tree rooted at r ∈ V (G) and |V (G)| ≥ 3. Let f be one of the furthest leaves from r. Let p be the parent of f and let g be the parent of p in G. If g has degree at least 3 and any child of g has degree 2 in G (see in Fig. 11(c)), then H = G[{f, p, g}] is a 3-potential-leaf of G.

1 .

 1 If B = B ′ = X = {f, f ′ , p, g}, then we can assume that B is the single bag containing p (otherwise, delete p from any other bag). So the intersection of B and any of its neighbor in T is contained in {g}. Then a desired tree decomposition can be obtained from Lemma 10. 2. If B = B ′ = {f, f ′ , p}, then the intersection of B and any of its neighbor in T is contained in {p}. Let Y be a neighbor of B in T containing p. By definition of the operation Leaf , the tree-decomposition Leaf (B, Y, (T, X )) has width at most 3, same size as (T, X ), and B = {f, f ′ , p} is a leaf. Then delete B and add a new bag N = {f, f ′ , p, g} adjacent to X. The result is a desired tree decomposition. 3. If B = B ′ = {f, f ′ , p, x} and x = g, then the intersection of B and any of its neighbor in T is contained in {p, x}. Since x / ∈ {f, f ′ , g}, p is not adjacent to x. There is a connected component in G \ B containing a neighbor of p and a neighbor of x. From Lemma 4, there exists a neighbor bag of B in (T, X ) containing p and x. Let Y be such a neighbor of B in T . By definition of the operation Leaf , the tree-decomposition Leaf (B, Y, (T, X )) has width at most 3, same size as (T, X ), and B = {f, f ′ , p, x} is a leaf. Then delete x from B and we get a tree decomposition having a bag {f, f ′ , p}. So we are in case 2. 4. If B = B ′ and |B| ≤ 3, then delete f ′ in B and add f ′ in B. Then we are in case 2 or 3. It is proved similarly if B = B ′ and |B ′ | ≤ 3. 5. Otherwise B = B ′ and |B| = |B ′ | = 4. Let B = {f, p, x, y} and B ′ = {f ′ , p, x ′ , y ′ }. Let P be the path in T from B to B ′ . Then p is contained in all bags on P . Let Y be the neighbor of B on P . If B∩Y = {p}, then {p} separates x from x ′ . But p is not a separator between any two vertices in V (G) \ {f, f ′ }. It is a contradiction. So w.l.o.g. we can assume that B ∩ Y ⊇ {p, x}. Deleting f, f ′ , p in all bags of (T, X ). Add a new bag Z = {x, y} ∪ Y \ {p, x} adjacent to all neighbors of the two bags B, Y and delete B and Y . Finally add another new bag N = {f, f ′ , p, g} adjacent to a bag containing g. The obtained tree decomposition has the desired properties. Lemma 16. Let G be a tree rooted at r ∈ V (G) and |V (G)| ≥ 4. Let all children of p be leaves in G and p have at least three children f, f ′ , f ′′ (see in Fig. 11(e)). Then H

Fig. 12 .

 12 Fig. 12. Complete set of 3-potential-leaves of 2-connected outerplanar graphs.

  are also called the consecutive vertices from v 1 to v j . Lemma 18. Let a, b, c, d ∈ V (G) be consecutive in C. If {a, b, c} induces a clique and c has degree 3 in G (see in Fig. 12(a)), then H

Lemma 21 .

 21 Let xy be a chord in G. Let C ′ be the set of all the consecutive vertices from x to y in C and |C ′ | ≥ 4. If each vertex in C ′ \ {x, y} has degree 2 in G, then for any consecutive vertices a, b, c, d ∈ C ′ (see in Fig. 12(c)), H = G[{a, b, c, d}] is a 3-potential-leaf of G.

Proof.

  Let G be a 2-connected outerplanar graph and C be the unique Hamilton cycle of G. If |V (G)| ≤ 4, then V (G) is a 3-potential-leaf of G. Otherwise, |V (G)| ≥ 5 and consider the outerplanar embedding of G. -If there exists an inner face f with at most one chord of G and f has at least four vertices, then from Lemma 21, the set of any four consecutive vertices in f , which are also consecutive in C, is a 3-potential-leaf in G. -If there is an inner face f = {a, b, c} with only one chord ac of G and c has degree 3, then let d be the other neighbor of c except b, a. From Lemma 18, the set of four consecutive vertices a, b, c, d, is a 3-potential-leaf in G. -Otherwise, let F be the set of all inner faces with only one chord of G. Then any face f ∈ F has three vertices and both the two endpoints of the chord in f have degree at least 4, i.e., they are incident to some other chords except this one. We can prove by induction on |V (G)| that: Claim. There exist two faces f 1 , f 2 ∈ F such that (1)f 1 = {a, b, c}; (2) f 2 = {c, d, e}; (3) a, b, c, d, e are consecutive in G; (4) there is a face f 0 containing both ac and ce and at most one chord, which is not in any face of F. See in Fig. 13. It is true when |V (G)| = 5. Assume that it is true for |V (G)| ≤ n -1. Now we prove it is true for |V (G)| = n.Note that F = ∅ if there is at least one chords in G, which is valid in this case. Let f ∈ F have three consecutive vertices x, y, z and let xz ∈ E(G) be the single chord in f . Then the graph G \ y is a 2-connected outerplanar graph with n -1 vertices. From the assumption, we have the desired facesf ′ 0 , f ′ 1 , f ′ 2 in G \ y. If xz is not an edge in any face of f ′ 1 , f ′ 2, then these faces are also the desired faces in G. Otherwise, let xz be an edge of f ′ 1 or f ′ 2 = {x, z, t}. Then z has degree 3 in G, i.e. it is not incident to any other chords except xz, since xt ∈ E(G). So we are in second case above, which contradicts with the assumption.

Fig. 13 .

 13 Fig.[START_REF] Robertson | Graph minors. II. algorithmic aspects of tree-width[END_REF]. F is the set of all inner faces with only one chord of G, such as f1, f2, f1, f2. The faces f0, f1, f2 satisfy the properties in Claim 5.2. But f0, f1, f2 does not satisfy the properties since f0 contains two edges ey, xy which are not in any face of F .

  k = max{tw + 1, 5}Graphs of treewidth at most tw = 1 P (trivial) P P ? ? Graphs of treewidth at most tw = 2 -

  {r, a, b, c} is not a 3-potential-leaf of G, but it is a 3-potential-leaf of G \ {yw}. The five bags {a, r, z, y}, {r, y, x, w}, {b, r, w, v}, {r, v, u, e}, {c, r, d, e} connecting as a path in this order forms a tree decomposition of G.

Fig. 14 .

 14 Fig. 14.

  If P has another child block except C in F containing the cut vertex p, then this child block also consists of one edge f ′ p ∈ E(G), where f ′ has degree one in G because this child is also a leaf block in F . (For example, in Fig.10, take C as C 8 , which intersects C 9 with a cut vertex.) From Lemma 7, {f, p, f ′ } is a 2-potential-leaf. Otherwise P has only one child block C in F containing the cut vertex p. Then any vertex in N G (p) \ {f } belongs to P . If P is also a bridge in G, i.e., P consists of one edge pq ∈ E(G), then p has degree 2 in G. (For example, in Fig.10, take C as C 11 , whose parent C 5 is also a bridge in G.) From Lemma 6, {f, p, q} is a 2-potential-leaf of G. Otherwise, P is a 2-connected component of G and p ∈ V (G) satisfies the hypothesis of Lemma 8. (For example, in Fig.10, take C as C 7 , whose parent C 4 is a 2-connected component of G.) Hence, either G has an isolated vertex α and {α, f, p} is a 2-potential-leaf or {f, p} is a 2-potential-leaf. -Finally, let us assume that C is a 2-connected component of G. It is known that any graph with at least two vertices of treewidth k contains at least two vertices of degrees at most k [5]. There is no degree one vertex in C because C is 2-connected. So there exists two vertices with degree 2 in C. Since C is a leaf in F , there is only one cut vertex of G in C. So there exists a vertex b in C which has degree two in G. If |V (C)| ≥ 4, then there exists a path between two neighbors a, c of b in G \ {b} containing at least one internal vertex. (For example, in Fig. 9, take C as C 10 .) From Lemma 9, {a, b, c} is a 2-potential-leaf. Otherwise C is a triangle {a, b, c} with at least two vertices with degree 2 in G. Again from Lemma 9, {a, b, c} is a 2-potential-leaf.

So the total time complexity is O(n + m). Corollary 4. s 2 can be computed in polynomial-time in general graphs. Moreover, a minimum size tree decomposition can be constructed in polynomial-time in the class of partial 2-trees.

  we have either xy / ∈ {uv, vw} or xy / ∈ {u ′ v ′ , v ′ w

′ }. W.l.o.g. assume that xy / ∈ {uv, vw}. Then u, v, w are also consecutive in C and at least one of u, w has degree 2 in G. W.l.o.g. suppose w has degree 2 in G, i.e.w / ∈ {x, y} (since x, y have degree at least 3 in G). Let z ∈ C ′ be the other neighbor (except v) of w in C ′ . (z exists because w /

This result was proved in[START_REF] Dereniowski | Minimum length path decompositions[END_REF] in terms of path-decomposition but it is straightforward to extend it to tree-decomposition.

⋆ This work has been partially supported by European Project FP7 EULER, ANR project Stint (ANR-13-BS02-0007), the associated Inria team AlDyNet, the project ECOS-Sud Chile and a grant from the "Conseil régional Provence Alpes-Côte d'Azur".

 Lemma 10. Let (T, X ) be a tree decomposition of a tree G. Let X ∈ X and N T (X) = {X 1 , . . . , X d } for d ≥ 1. Suppose that for any 1 ≤ i ≤ d, X i ∩ X ⊆ {x}. Then there is a tree decomposition (T ′ , X ′ ) of G of the same width and size as (T, X ) such that X is a leaf bag.

Proof. If there is a bag X i for 1 ≤ i ≤ d containing x, then let B be X i . Otherwise let B be any neighbor of X. By definition of the operation Leaf , the tree-decomposition Leaf (X, B, (T, X )) is a desired tree decomposition.

Lemma 11. Let G be a tree rooted at r ∈ V (G). Let f be a leaf in G. Let p be the parent of f and let g be the parent of p in G. Let p have degree 2 in G. Let (T, X ) be a tree decomposition of G of width at most 3 and size at most s ≥ 1.

If there is no bag in (T, X ) containing all of f, p, g, then there is a tree decomposition (T ′ , X ′ ) of G of width at most 3 and size at most s such that {f, p, g} ∈ X ′ is a leaf bag.

Proof. Since f p ∈ E(G), there is a bag B in (T, X ) containing both f and p. We may assume that B is the single bag containing f (otherwise, delete f from any other bag). Similarly, since pg ∈ E(G), let X be a bag in (T, X ) containing both p and g. Let P be the path in T from B to X. Then p is contained in all bags on P and we may assume that p is not contained in any other bags (otherwise, delete p from any other bag). Let B ′ be the neighbor of B on P . Then B ∩ B ′ ⊇ {p}. Note that it is possible that B ′ = X.

If B = {f, p}, then make all other neighbors of B adjacent to B ′ and delete B. Add a bag {f, p, g} adjacent to X. The result is a desired tree decomposition (T ′ , X ′ ).

Otherwise, B contains at least one vertex not in {f, p}. and all neighbors of B ′ ; and delete the two bags B and B ′ ; and delete f, p from all bags. Finally add another new bag N = {f, p, g} adjacent to some bag containing g. The obtained tree decomposition has width at most 3, same size as (T, X ), and a bag N = {f, p, g}.

Lemma 12. Let G be a tree rooted at r ∈ V (G) and |V (G)| ≥ 4. Let f be a leaf in G. Let p be the parent of f and let g be the parent of p in G. Suppose that both p and g have degree 2. Let h be the parent of g (see in Fig. 11(a)), then

Proof. Let (T, X ) be any reduced tree decomposition of width at most 3 and size at most s ≥ 1 of G. We show how to modify it to obtain a tree-decomposition with width at most 3 and size at most s and in which {f, p, g, h} is a leaf bag.

From Lemma 11, we can assume that there is a bag B in (T, X ) containing all f, p, g. We may assume that B is the single bag containing f, p (otherwise, delete f, p from any other bag). Since gh ∈ E(G), let Y be a bag in (T, X ) containing both h and g.

1.

If B = Y = {f, p, g, h}, then the intersection of B and any of its neighbor in T is contained in {h}. A desired tree decomposition can be obtained from Lemma 10. 2. If B = {f, p, g}, then the intersection of B and any of its neighbors in T is contained in {g}. From Lemma 10, there is a tree-decomposition (T ′ , X ′ )) of the same width and size as the ones of (T, X ) such that B = {f, p, g} is a leaf. Then delete B in the tree-decomposition Leaf (B, B ′ , (T, X )) and add a new bag N = {f, p, g, h} adjacent to Y . The obtained tree decomposition has the desired properties.

Proof. Let (T, X ) be any tree decomposition of width at most 3 and size at most s ≥ 1 of G. We show how to modify it to obtain a tree-decomposition with width at most 3 and size at most s and in which {a, b, c, d} is a leaf bag. Since {a, b, c} induces a clique in G, there is a bag B containing all a, b, c. Let X be a bag in (T, X ) containing both c and d (it exists since cd ∈ E(G)). Note that b is not incident to any chords, i.e. has degree 2. (Because if by ∈ E(G) is a chord in G, then deleting all chords except ac, by in G and contracting the edges in C except ab, bc we get a K 4 -minor in G. It is a contradiction with the fact that G is outerplanar.)

Replace b, c with a in all bags of (T, X ). Then (T, X ) becomes a tree decomposition (T ′ , X ′ ) of the graph G ′ obtained by contracting the edges ab and bc. The bag X becomes X ′ , which contains both a and d; and B becomes

From Corollary 2, in both case there exists a neighbor Y of B ′ such that B ′ ⊆ Y . So B ′ can be reduced in (T ′ , X ′ ). The tree decomposition Reduce(B ′ , Y, (T ′ , X ′ )) has one bag less than (T, X ). Finally, add a new bag N = {a, b, c, d} adjacent to X ′ , which contained both a and d, in the tree decomposition Reduce(B ′ , Y, (T ′ , X ′ )). The result is a desired tree decomposition, because b, c are not adjacent to any vertices in V (G) \ N . Proof. Let (T, X ) be any tree decomposition of width at most 3 and size at most s ≥ 1 of G. We show how to modify it to obtain a tree-decomposition with width at most 3 and size at most s and in which {a, b, c} is a leaf bag.

Since {a, b, c} (resp. {c, d, e}) induces a clique in G, there is a bag X (resp. Y ) containing all a, b, c (resp. c, d, e). Note that b, c, d are not adjacent to any vertices in V (G) \ {a, b, c, d, e}.

Delete b, c, d in all bags of (T, X ). Then (T, X ) becomes a tree decomposition (T ′ , X ′ ) of the graph

Similarly, the bag Y becomes Y ′ , which can also be reduced in (T ′ , X ′ ). After reducing the two bags X ′ , Y ′ in (T ′ , X ′ ), let the obtained tree decomposition be (T ′′ , X ′′ ). Finally, add two new bags N 1 = {a, b, c} and N 2 = {a, c, d, e}; make N 1 adjacent to N 2 and make N 2 adjacent to a bag Z containing both a and e in the tree decomposition (T ′′ , X ′′ ). (Z exists because ae ∈ E(G ′ ).) The result is a desired tree decomposition.

Lemma 20. Let C l be a cycle of l ≥ 4 vertices. Let (T, X ) be a tree decomposition of C l of width at most 3. Then there exist either a bag containing all vertices of V (C l ) (only if l = 4) or two bags X, Y ∈ X such that X (resp. Y ) contains at least three consecutive vertices x 1 , x 2 , x 3 (resp. y 1 , y 2 , y 3 ) and the two edge sets {x 1 x 2 , x 2 x 3 } ∩ {y 1 y 2 , y 2 y 3 } = ∅.

Proof. The treewidth of any cycle is bigger than 1, so there exists a bag in any tree decomposition of a cycle (with at least 4 vertices) containing two vertices not consecutive, equivalently they are not adjacent in the cycle. We prove the lemma by induction on l in the following.

First let us prove that it is true for l = 4. Let a, b, c, d be the four consecutive vertices in C 4 . Let (T, X ) be a tree decomposition of width at most 3. Then there exists a bag containing a, c or b, d. W.l.o.g assume a, c are contained in one bag. So (T, X ) is also a tree decomposition of H, obtained from C 4 by adding the edge ac. The set {a, b, c} induces a clique in H. So there is a bag X containing a, b, c. For the same reason, there is a bag Y containing c, d, a. If X = Y then there is a bag containing all a, b, c, d of V (C 4 ). Otherwise there are two bags X, Y such that X ⊇ {a, b, c} and Y ⊇ {c, d, a}. We see that {ab, bc} ∩ {cd, da} = ∅. So the lemma is true for l = 4. Now suppose it is true for l ≤ n -1 and we prove it for l = n ≥ 5. Note that since (T, X ) has width 3 and l ≥ 5, there is no bag containing all vertices of V (C l ). So in the following we prove that there always exist two bags X, Y with the desired properties. Let v 1 , . . . , v n be the n consecutive vertices in C n . Let (T, X) be a tree-decomposition of width at most 3 of C n . Then there exists a bag containing two non-adjacent vertices v i , v j for 1 ≤ i < j ≤ n. So (T, X ) is also a tree decomposition of the graph H, obtained from C n by adding the edge v i v j . The graph H is also the union of two subcycles C 1 induced by {v i , . . . , v j } and C 2 induced by {v j , . . . , v n , . . . , v i }. Then max{|C 1 |, |C 2 |} ≤ n-1. Let (T 1 , X 1 ) (resp. (T 2 , X 2 )) be the tree decomposition of C 1 (resp. C 2 ) obtained by deleting all vertices not in C 1 (resp. C 2 ) in the bags of (T, X).

If |V (C 1 )| = 3 then there is a bag in (T 1 , X 1 ) containing V (C 1 ) = {v i , v i+1 , v j = v i+2 }. So v i v j / ∈ {v i v i+1 , v i+1 v j }. If |V (C 1 )| ≥ 4 then, by induction, there exist either a bag in (T 1 , X 1 ) containing all vertices of V (C 1 ) = {v i , v i+1 , v i+2 , v j = v i+3 } or two bags A, B in (T 1 , X 1 ) containing three consecutive vertices a 1 , a 2 , a