Mathieu Chapelle
email: mathieu.chapelle@univ-orleans.fr

Frédéric Mazoit
email: frederic.mazoit@labri.fr

Ioan Todinca
email: ioan.todinca@univ-orleans.fr

Constructing brambles

Given an arbitrary graph G and a number k, it is well-known by a result of Seymour and Thomas [20] that G has treewidth strictly larger than k if and only if it has a bramble of order k + 2. Brambles are used in combinatorics as certificates proving that the treewidth of a graph is large. From an algorithmic point of view there are several algorithms computing tree-decompositions of G of width at most k, if such decompositions exist and the running time is polynomial for constant k. Nevertheless, when the treewidth of the input graph is larger than k, to our knowledge there is no algorithm constructing a bramble of order k + 2. We give here such an algorithm, running in O(n k+4 ) time. Moreover, for classes of graphs with polynomial number of minimal separators, we define a notion of compact brambles and show how to compute compact brambles of order k + 2 in polynomial time, not depending on k.

Introduction

Motivation. Treewidth is one of the most extensively studied graph parameters, mainly because many classical NP-hard optimisation problems become polynomial and even linear when restricted to graphs of bounded treewidth. In many applications of treewidth, one needs to compute a tree-decomposition of small width of the input graph. Although determining the treewidth of arbitrary graphs is NP-hard [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF], for small values of k one can decide quite efficiently if the treewidth of the input graph is at most k. The first result of this flavour is a rather natural and simple algorithm due to Arnborg, Corneil and Proskurowski [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF] working in O(n k+2 ) time (as usual n denotes the number of vertices of the input graph and m denotes the number of its edges). Using much more sophisticated techniques, Bodlaender [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF] solves the same problem by an algorithm running in O(f (k)n) time, where f is an exponential function.

The treewidth problem has been also studied for graph classes, and it was shown [START_REF] Bouchitté | Treewidth and minimum fill-in: grouping the minimal separators[END_REF][START_REF] Bouchitté | Listing all potential maximal cliques of a graph[END_REF] that for any class of graphs with polynomial number of minimal separators, the treewidth can be computed in polynomial time. In particular the problem is polynomial for several natural graph classes e.g. circle graphs, circular arc graphs or weakly chordal graphs. All cited algorithms are able to compute optimal tree-decompositions of the input graph.

In the last years, tree decompositions have been used for practicle applications which encouraged the developement of heuristic methods for tree-decompositions of small width [START_REF] Bachoore | New upper bound heuristics for treewidth[END_REF][START_REF] Clautiaux | New lower and upper bounds for graph treewidth[END_REF] and, in order to validate the quality of the decompositions, several authors also developed algorithms finding lower bounds for treewidth [START_REF] Bodlaender | Contraction and treewidth lower bounds[END_REF][START_REF] Bodlaender | On the maximum cardinality search lower bound for treewidth[END_REF][START_REF] Bodlaender | Treewidth lower bounds with brambles[END_REF][START_REF] Clautiaux | New lower and upper bounds for graph treewidth[END_REF].

Indeed, one of the main difficulties with treewidth is that we do not have simple certificates for large treewidth. We can easily argue that the treewidth of a graph G is at most k: it is sufficient to provide a tree-decomposition of width at most k, and one can check in linear time that the decomposition is correct. On the other hand, how to argue that the treewidth of G is (strictly) larger than k? For this purpose, Seymour and Thomas introduced the notion of brambles, defined below. The goal of this article is to give algorithms for computing brambles. Some definitions. A tree decomposition of a graph G = (V, E) is a tree T D such that each node of T D is a bag (vertex subset of G) and satisfies the following properties: [START_REF] Amini | Partition submodular functions[END_REF] each vertex of G appears in at least one bag, [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF] for each edge of G there is a bag containing both endpoints of the edge and (3) for any vertex x of G, the bags containing x form a connected subtree of T D. The width of the decomposition is the size of its largest bags, minus one. The treewidth of G is the minimum width over all tree decompositions of G.

Without loss of generality, we restrict to tree decompositions such that there is no bag contained into another. We say that a tree decomposition T D is finer than another tree decomposition T D ′ if each bag of T D is contained in some bag of T D ′ . Clearly, optimal tree decompositions are among minimal ones, with respect to the refining relation. A set of vertices of G is a potential maximal clique if it is the bag of some minimal tree decomposition. Potential maximal cliques of a graph are incomparable with respect to inclusion [START_REF] Bouchitté | Treewidth and minimum fill-in: grouping the minimal separators[END_REF]. More important, the number of potential maximal cliques is polynomially bounded in the number of minimal separators of the graph [START_REF] Bouchitté | Listing all potential maximal cliques of a graph[END_REF], which implies that for several graph classes (circle, circular arc, weakly chordal graphs...) the number of potential maximal cliques is polynomially bounded in the size of the graph.

A bramble of order k of G = (V, E) is a function β mapping each vertex subset X of size at most k -1 to a connected component β(X) of G -X. We require that, for any subsets X, Y of V of size at most k -1, the components β(X) and β(Y ) touch, i.e. they have a common vertex or an edge between the two. 3Theorem 1 (Treewidth-bramble duality, [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF]). A graph G is of treewidth strictly larger than k if and only if it has a bramble of order k + 2.

Very roughly, if a graph has treewidth larger than k, for each possible bag X of size at most k + 1 the bramble points toward a component of G -X which cannot be decomposed by a tree-decomposition of width at most k (restricted to X ∪ β(X)) using X as a bag. Treewidth can be also stated in terms of a cops-and-robber game, and tree decompositions of width k correspond to winning strategies for k + 1 cops, while brambles of order k + 2 correspond to escaping strategies for the robber, if the number of cops is at most k + 1 (see e.g. [START_REF] Bodlaender | A partial k-arboretum of graphs with bounded treewidth[END_REF]).

Since optimal tree decompositions can be obtained using only potential maximal cliques as bags, we introduce now compact brambles as follows. Instead of associating to any set X of size less than k a component β(X) of G -X, we only do this for the sets which are also potential maximal cliques. It is not hard to prove that, in Theorem 1, we can replace brambles by compact brambles. Indeed if the treewidth of G is larger than k then there is a bramble of order k + 2, which can be restricted to a compact bramble of the same order. Conversely, suppose that there exists a compact bramble of order k + 2 and a tree decomposition of width at most k. Consider a minimal, optimal tree decomposition of G. According to [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF], there is a bag X of this decomposition intersecting each set β(Y ) of the bramble. By our choice X is a potential maximal clique of size at most k + 1, thus X intersects β(X) -a contradiction.

Our results. After the seminal paper of Seymour and Thomas proving Theorem 1, there were several results, either with shorter and simpler proofs [START_REF] Bellenbaum | Two short proofs concerning tree-decompositions[END_REF] or for proving other duality theorems of similar flavour, concerning different types of tree-like decompositions, e. g. branchdecompositions, path-decompositions or rank-decompositions (see [START_REF] Amini | Partition submodular functions[END_REF] for a survey). Unified versions of these results have been given recently in [START_REF] Amini | Partition submodular functions[END_REF] and [START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF]. We point out that all these proofs are purely combinatorial: even for a small constant k, it is not clear at all how to use these proofs for constructing brambles on polynomial time (e.g. the proofs of [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF][START_REF] Bellenbaum | Two short proofs concerning tree-decompositions[END_REF] start by considering the set of all connected subgraphs of the input graph). Nevertheless the recent construction of [START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF] gives a simpler information on the structure of a bramble (see Theorem 4). Based on their framework which we extend, we build up the following algorithmic result: Theorem 2. There is an algorithm that, given a graph G and a number k, computes either a tree decomposition of G of width at most k, or a bramble of order k + 2, in O(n k+4 ) time.

There is an algorithm that, given a graph G, computes a tree-decomposition of width at most k or a compact bramble of order k + 2 in O(n 4 r 2 ) time, where r is the number of minimal separators of the graph.

These brambles can be used as certificates that allow to check, by a simple algorithm, that a graph has treewidth larger than k. The certificates are of polynomial size for fixed k, and the compact brambles are of polynomial size for graph classes with a polynomial number of minimal separators, like circle, circular-arc or weakly chordal graphs (even for large k). Also, in the area of graph searching (see [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF] for a survey), in which it is very common to give optimal strategies for the cops, our construction of brambles provides a simple escape strategy for the robber.

The paper is organized as follows. In Section 2 we introduce an extended version of the framework of [START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF] and their version of the duality theorem. In Section 3 we give the algorithm constructing the brambles. In the Conclusion we discuss extentions of these results and further research.

Treewidth, partitioning trees and the generalized duality theorem

For our purpose, it is more convenient to view tree decompositions as recursive decompositions of the edge set of the graph, thus we rather use the notion of partitioning trees. The notion is very similar to branch-decompositions [START_REF] Robertson | Graph minors X. Obstructions to tree decompositions[END_REF] except that in our case internal nodes have arbitrary degree; in branch-decompositions, internal nodes are of degree three.

Definition 1 (partitioning trees).

A partitioning tree of a graph G = (V, E) is a pair (T, τ ) where T is a tree and τ is a one-to-one mapping of the edges of G on the leaves of T .

Given an internal node i of T , let µ(i) be the partition of E where each part corresponds to the edges of G mapped on the leaves of a subtree of T obtained by removing node i.

We denote by δ(µ(i)) the border of the partition, i.e. the set of vertices of G appearing in at least two parts of µ(i); δ(µ(i)) is also called the bag associated to node i. Let width(T, τ ) be the max |δ(µ(i))| -1, over all internal nodes i of T . The treewidth of G is the minimum width over all partitioning trees of G.

One can easily transform a partitioning tree (T, τ ) into a tree decomposition such that the bags of the tree-decompositions are exactly the sets δ(µ(i)). Indeed consider the tree decomposition with the same tree, associate to each internal node i the bag δ(µ(i)) and to each leaf j the bag {x j , y j } where x j y j is the edge of G mapped on the leaf j. It is a matter of routine to check that this tree decomposition satisfies all conditions of tree decompositions.

Conversely, consider a tree decomposition T D of G, we describe a partitioning tree (T, τ ) obtained from T D without increasing the width. Initially T is a copy T D. For each edge e of G, add a new leaf mapped to this edge, and make it adjacent to one of the nodes of T such that the corresponding bag contains both endpoints of the edge. Eventually, we recursively remove the leaves of T which correspond to nodes of T D (thus there is no edge of G mapped on these leaves). In the end we obtain a partitioning tree of G, and again is not hard to check that (see e.g. [START_REF] Mazoit | Décompositions algorithmiques des graphes[END_REF]) for each internal node i of T , we have that δ(µ(i)) is contained in the bag X(i) corresponding to node i in T D.

Consequently, the treewidth of G is indeed the minimum width over all partitioning trees of G.

Given a graph which is not necessarily of treewidth at most k, we want to capture the "best decompositions" one can obtain with bags of size at most k. For this purpose we define partial partitioning trees. Roughly speaking, partial partitioning trees of width at most k correspond to tree decompositions such that all internal bags are of size at most k + 1 -the leaves are allowed to have arbitrary size.

Definition 2 (partial partitioning trees).

Given a graph G = (V, E), a partial partitioning tree is a couple (T, τ ), where T is a tree and τ is a one-to-one function from the set of leaves of T to the parts of some partition (E 1 , . . . , E p ) of E. The bags δ(µ(i)) of the internal vertices are like in the case of partitioning trees. The bag of the leaf labeled E i is the set of vertices incident to E i . The partition (E 1 , . . . , E p ) is called the displayed partition of (T, τ ).

The width of a partial partitioning tree is max |δ(µ(i))| over all internal nodes of T . 4Partitioning trees are exactly partial partitioning trees such that the corresponding displayed partition of the edge set is a partition into singletons. Given an arbitrary graph, our aim is to characterize displayed partitions corresponding to partial partitioning trees of width at most k. Actually we only consider connected partial partitioning trees, and also the more particular case when the labels of the internal nodes are potential maximal cliques, and we will see that this classes contain the optimal decompositions.

The connected partial partitioning trees (strongly related to a similar notion on tree decompositions) are defined as follows. Let X be a set of vertices of G. We say that the set of edges F is a flap for X if F is formed by a unique edge with both endpoints in X or if there is a connected component of G -X, induced by a vertex subset C of G, and F corresponds exactly to the set of edges of G incident to C (so the edges of F are either between vertices of C or between C and its neighborhood N G (C)). Given a partial partitioning tree (T, τ ) and an internal node r which will be considered as the root, let T (i) denote the subtree of T rooted in node i. We denote by E(i) the union of all edge subsets mapped on the leaves of T (i). We say that (T, τ ) is a connected partial partitioning tree if and only if, for each internal node j and any son i of j, the edge subset E(i) forms a flap for δ(µ(j)).

Due to space restrictions, all proofs of this section are given in Appendix A.

Lemma 1. Given an arbitrary partial partitioning tree (T, τ ) of G, there always exists a connected partial partitioning tree (T ′ , τ ′ ) such that each edge subset mapped on a leaf of T ′ is contained in an edge subset mapped on a leaf of T and each bag of (T ′ , τ ′ ) is contained in some bag of (T, τ ).

Let P be a set of partitions of E. We define a new, larger set of partitions P ↑ as follows. Initially, P ↑ = P. Then, for any partition µ = (E 1 , E 2 , . . . , E p ) ∈ P ↑ and any partition ν = (F 1 , F 2 , . . . , F q , F q+1 , . . . F r ) ∈ P such that F q+1 ∪ . . . ∪ F r = E 1 , we add to P ↑ the partition µ ⊕ ν = (E 2 , . . . , E p , F q+1 , . . . , F r ). The process is iterated until it converges. In terms of partial partitioning trees, each partition ν ∈ P is the displayed partition of a partial partitioning tree with a unique internal node. Initially elements of P ↑ correspond to these starlike partial partitioning trees. Then, given any partial partitioning tree T µ corresponding to an element µ = (E 1 , E 2 , . . . , E p ) ∈ P ↑ and a star-like partial partitioning tree T ν corresponding to an element ν = (F 1 , F 2 , . . . , F q , F q+1 , . . . F r ) ∈ P, if the leaf E 1 of the first tree is exactly F q+1 ∪ . . . ∪ F r , then we glue the two trees by identifying the leaf E 1 of T µ with the internal node of T ν and then removing the leaves F 1 , . . . , F q of T ν . Thus µ ⊕ ν is the displayed partition of the new tree. See Figure 1 for an example of this recursive gluing on partial partitioning trees. (A similar but simpler grammar is used in [START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF].)

The proof of the following statement is an easy consequence of the definitions:

Lemma 2.
Let T be a partial partitioning tree obtained by recursive gluing. The root of T corresponds to the internal node of the first star-like partial partitioning tree used in the recursive gluing. Let x be an internal node of T , and denote by µ x the partition of P corresponding to the star-like tree with internal node x -which might be different from the partition µ(x) introduced in Definition 1. Then for any son y of x, E(y) is a part of µ x . (Recall that E(y) denotes the union of parts of E mapped on leaves of the subtree T (y) of T rooted in y.) If x is the root, then the sets E(y) for all sons y of x are exactly the parts of µ x .

Conversely, let T be a (rooted) partial partitioning tree such that, for each internal node x there is a partition µ x ∈ P such that for any son y of x, E(y) is a part of µ x , and, moreover, if x is the root then its sons correspond exactly to the parts of µ x . Then T is obtained by gluing the partitions µ x , starting from the root and in a breadth-first search order.

Let P k-f lap be the set of partitions µ of E such that δ(µ) is of size at most k + 1 and the elements of µ are exactly the flaps of δ(µ). The set P k-pmc is the subset of P k-f lap such that for any µ ∈ P k-pmc , its border δ(µ) is a potential maximal clique. Thus the sets P ↑ k-f lap and P ↑ k-pmc correspond to partial partitioning trees of width at most k. By Lemma 2, for any graph G, P ↑ k-f lap is the set of displayed partitions of connected partial partitioning trees of width at most k. Moreover, P ↑ k-pmc is the set of displayed partitions of connected partitioning trees of width at most k and such that the bags of all internal vertices are potential maximal cliques. Consequently, we have:

Lemma 3. G is of treewidth at most k if and only if P ↑ k-f lap contains the partition into singletons, and if and only if P ↑

k-pmc contains the partition into singletons.

Clearly P k-f lap is of size O(n k+1
) and P k-pmc is of size at most the number of potential maximal cliques of the graph. Lemma 4. Given a set of partitions P and the corresponding set P ↑ , we say that P ↑ is orientable if, for any partition µ ∈ P ↑ and any part F of µ, there is a partition ν ∈ P ↑ finer than µ (i.e. each part of ν is contained in a part of µ) and a partial partitioning tree T ν displaying ν in which the leaf mapped on F is adjacent to the root.

The sets of partitions P ↑ k-f lap and P ↑ k-pmc are orientable. Following [START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF], we define P-brambles, associated to any set P of partitions of E. (a) A graph G = (V,E).

Definition 3 (bramble). Let P be an arbitrary set of partitions of E. A P-bramble is a set B of pairwise intersecting subsets of E, all of them of size at least 2, and such that for any partition

µ = (E 1 , . . . , E p ) ∈ P, there is a part E i ∈ B.
ω ψ ρ φ {1} {2,3,4} {5,6} {11} {8} {9} {7} σ {10} {12}
(b) A partial partitioning tree in P ↑ , with ψ as root. Here, the bag associated to node ψ (in the corresponding classical tree decomposition) would be {b, c, d}.

φ {7} {8} {9} {1 ,2,3,4,5, 6,10,11,12} ρ
(c) The corresponding partial partitioning trees in P. With this definition, one can see that a bramble of order k + 2 corresponds exactly to a P k-f lap -bramble, and a compact bramble of order k + 2 corresponds to a P k-pmc -bramble. We say that a set of partitions P ↑ is refining if for any partitions (A, A 2 , . . . , A p ) and (B, B 2 , . . . , B q ) in P ↑ , with A and B disjoints, there exists a partition (C 1 , . . . , C r ) in

P ↑ such that each part C i is contained in some A j , 2 ≤ j ≤ p, or in some B l , 2 ≤ l ≤ q.
In [START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF], the authors show that for the set P k defined by the partitions of E having borders of size at most k + 1 (without any other restriction), P ↑ k is refining. Using Lemma 1, we can easily deduce that P ↑ k-f lap is refining. On the other hand, much more efforts are required to prove that P ↑ k-pmc is also refining (see Appendix A).

Theorem 3. For any graph G, the sets of partitions P ↑ k-f lap and P ↑ k-pmc are refining.

The following result implies the "hard part" of Theorem 1. Indeed, by applying Theorem 4 to P ↑ k-f lap , we have that any graph of treewidth greater than k has a bramble of order k +2. For the sake of completion and for better understanding, we give the proof of [START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF] in Appendix A.

Theorem 4 ([16]

). Let P be a set of partitions of E and suppose that P is refining and does not contain the partition into singletons. Let B be a set of subsets of E such that:

1. Each element of B is of size at least 2 and it is a part of some µ ∈ P; 2. For each µ = (E 1 , . . . , E p ) ∈ P, there is some part E i ∈ B; 3. B is upper closed, i.e. for any F ∈ B, and any superset

F ′ with F ⊂ F ′ ⊆ E such that F ′
is the part of some µ ′ ∈ P, we also have F ′ ∈ B; 4. B is inclusion-minimal among all sets satisfying the above conditions.

Then B is a P-bramble.

The algorithm

Our goal is to apply Theorem 4 in order to obtain a P ↑ k-f lap -bramble and a P ↑ k-pmc -bramble. Note that the sets P k-f lap and P k-pmc are not refining, so we cannot use them directly.

We make an abuse of notation and say that a flap of P ↑ is a subset of E appearing as the part of some µ ∈ P ↑ . Consequently the flaps of P ↑ are exactly the flaps of P. Thus, once we have computed a P ↑ k-f lap -bramble (resp. a P ↑ k-pmc -bramble), by restricting it to P k-f lap (resp. P k-pmc ) we obtain a bramble (resp. a compact bramble) of order k + 2. The difficulty is that the complexity of our algorithm should be polynomial in the size of P k-f lap (resp. P k-pmc ), while the sets P ↑ k-f lap and P ↑ k-pmc may be of exponential size even for small k. We give now our main algorithmic result. It is stated in a general form, for an arbitrary set of partitions P such that P ↑ is refining and orientable.

Theorem 5 (main theorem). Let P be a set of partitions of E. Suppose that P ↑ is refining, orientable and does not contain the partition into singletons. Then there is an algorithm constructing a P ↑ -bramble (and in particular a P-bramble), whose running time is polynomial in the size of E and of P.

The following algorithm is a straightforward translation of Theorem 4 applied to P ↑ , so the output B f is indeed a P ↑ -bramble.

Bramble(P) begin

B ← the set of the flaps of P;

B f ← ∅; foreach F ∈ B of size one do Remove F from B; end foreach foreach F ∈ B taken in inclusion order do if there is a partition µ ∈ P ↑ such that F is the unique non-removed flap of the partition or ∃F ′ ∈ B f : F ′ ⊆ F then Add F to B f ; else Remove F from B; end if end foreach return B f ; end
Unfortunately the size of P ↑ may be exponential in the size of P and E, and hence the algorithm does not satisfy our complexity requirements because of the test "if there is a partition µ ∈ P ↑ such that F is the unique non-removed flap of the partition", which works on P ↑ . We would like it to work on P instead. Thus we replace this test by a marking process working on P instead of P ↑ but giving the same bramble (recall that the flaps of P ↑ are exactly the flaps of P). Let us introduce some definitions for the marking. A flap F is said to be removed if it has already been removed from the final P-bramble (instruction "Remove F from B ′′ ). Intuitively these removed flaps induce some forcing among other flaps: some of the flaps must be added to the final bramble, some others cannot be added to the final bramble. Thus whenever a flap is removed, we call the algorithm UpdateMarks. We use two types of markings on the flaps: forbidden and forced. We prove that a flap F will be marked as forced if and only if there is some partition µ ∈ P ↑ such that all flaps of µ, except F , are removed. Thus, in Algorithm Bramble, it suffices to test the mark of the flaps.

UpdateMarks begin

// marking forbidden flaps; while ∃ a flap F and a partition (F 1 , . . . , F p , F p+1 , . . . , F q ) ∈ P such that

( ∪ p i F i ) = F and ∀ i, 1 ≤ i ≤ p, F i is removed or F i is forbidden do Mark F as forbidden (if not already marked); end while // marking forced flaps; while ∃ (F, F 2 , . . . , F p ) ∈ P such that ∀ i, 2 ≤ i ≤ p : F i is removed or F i is forbidden do
Mark F as forced (if not already marked); end while end All throughout the algorithm we have the following invariants. Lemma 5. A flap F is marked as forbidden if and only if there exists a subtree T (x) of a partial partitioning tree T displaying some partition in P ↑ such that:

-Each flap mapped on a leaf of T (x) is removed; -The union of these flaps is exactly F .

Proof. Suppose first that such a tree exists. We show that the flap F corresponding to the edges mapped on the leaves of T (x) is marked as forbidden. Each internal node y of T (x) corresponds to a partition µ y of P. The edges E(y) of G mapped on the leaves of T (y) form a flap, by construction of T (see also Lemma 2). Consider these internal nodes of T (x), in a bottom up order, we prove by induction that all flaps of such type are marked as forbidden. By induction, when node y is considered, for each of its sons y 1 , . . . , y p , either the son is a leaf and hence the corresponding flap is removed, or E(y i ) has been previously marked as forbidden. Then Algorithm UpdateMarks forbids the flap E(y). Consequently, E(x) is marked as forbidden.

Conversely, let F be any flap marked as forbidden, we construct a partial partitioning tree T with a node x as required. We proceed by induction on the inclusion order over the forbidden flaps. When a flap F becomes forbidden, it is the union of some flaps F 1 , . . . , F p , each of them being forbidden or removed, and such that (F 1 , . . . , F p , F p+1 , . . . , F q ) is an element of P. By induction hypothesis, to each F i , i ≤ p, we can associate a tree T i (which is a subpart of a partial partitioning tree) such that the flaps mapped on the leaves of T i form a partition of F i and they are all removed. Notice that, if F i is a removed flap, then the tree T i is only a leaf. Consider now a tree T (x) formed by a root x, corresponding to the partition (F 1 , . . . , F p , F p+1 , . . . , F q ) ∈ P, and linked to the roots of T 1 , . . . , T p . Consider any partition (F, F ′ 1 , . . . , F ′ r ) ∈ P (such a partition exists, since F is a flap). Note that ∪ j F ′ j = ∪ i≥p+1 F i . The final tree T is obtained by choosing a root z, corresponding to (F, F ′ 1 , . . . , F ′ r ), to which root we glue the subtree T x by adding the edge xz, and for each flap F ′ j we add a leaf adjacent to the root z mapped on F ′ j . Thus the final tree T is a gluing between the tree rooted on x and the tree rooted on z. By construction, for each internal node y of this tree, the sets E(y ′ ) for the sons y ′ of y are parts of some partition µ y ∈ P. By Lemma 2, the tree T is a partial partitioning tree displaying an element of P ↑ . Clearly all leaves of T (x) are mapped on removed flaps.

⊓ ⊔ Lemma 6. A flap F is marked as forced if and only if there is a partition in P ↑ such that F is the only non-removed flap of the partition.

Proof. Let us show that F is the unique non-removed flap of some partition in P ↑ if and only if there is a partial partitioning tree T displaying a (possibly another) partition in P ↑ such that all leaves but F correspond to removed flaps and, moreover, the leaf mapped on F is adjacent to the root of T . Clearly if such a tree exists, the partition µ displayed by the partial partitioning tree has F as the unique non-removed flap. Suppose now that F is a unique non-removed flap of some partition µ ′ ∈ P ↑ . By the fact that P ↑ is orientable, there is a partial partitioning tree T displaying some partition µ, finer than µ ′ , and such that the leaf of T mapped on F is adjacent to the root of the tree. Thus every flap F i of µ other than F is contained in some flap F ′ j of µ ′ . Since flap F ′ j has been removed by algorithm Bramble, flap F i has also been removed (in a previous step, unless the trivial case F i = F ′ j ): indeed flap F i has been treated by the algorithm before F ′ j , and if F i is not removed it means that it has been added to the bramble B f , and hence the algorithm will not remove any superset of F icontradicting the fact that F ′ j is now removed. We conclude that all flaps of µ, except F , have been removed.

It remains to prove that a flap F is marked as forced if and only if there is a partial partitioning tree T displaying a partition in P ↑ , such that all leaves but F correspond to removed flaps and, moreover, the leaf mapped on F is adjacent to the root of T .

First, if such a tree exists, let z be its root. Then z corresponds to a partition (F, F 2 , . . . , F p ) in P, and each flap F i corresponds to a subtree T i of Tz. By Lemma 5, every flap F i , 2 ≤ i ≤ p, is removed or forbidden. Then Algorithm UpdateMarks marks the flap F as forced.

Conversely, suppose that Algorithm UpdateMarks marks the flap F as forced. Let (F, F 2 , . . . , F p ) be the partition in P which has triggered this mark, so all flaps F i are removed or forbidden. Thus to each such flap corresponds a subtree T i of some partial partitioning tree, such that the leaves of T i form a partition of F i and they are all removed flaps. The tree T , formed by a root x linked to the roots of each T i , plus a leaf (mapped on F ) adjacent to z satisfies our claim.

⊓ ⊔ Let us discuss now the time complexity of our algorithm. This complexity is the maximum between:

1. the overall complexity of the calls of UpdateMarks;

the complexity of the tests "∃F

′ ∈ B f : F ′ ⊆ F " of the Bramble algorithm.
Clearly both parts are polynomial in the total number of flaps, the number of elements of P and the size of the graph. The number of flaps is itself at most m|P|, since each partition has at most m parts. It is easy to see that the overall complexity is quadratic in the size of P, times a small polynomial in the size of the graph. This achieves the proof of Theorem 5.

Nevertheless let us go into a little more details, which will allow us to prove that, when we apply our algorithm to P k-f lap and P k-pmc , we obtain better complexity, as claimed in Theorem 2. In particular the running time will be linear in the size of P k-f lap (resp. P k-pmc ), times a small polynomial in n. The overall complexity of UpdateMarks is given by the complexity of updating the forbidden flaps. Let us say that a couple (F, µ), formed by a flap F and a partition µ ∈ P is a good couple if µ is of the form (F 1 , . . . , F p , F p+1 , . . . , F q ) with F = F 1 ∪ . . . ∪ F p . We use the following data structure. Each flap F i points towards each good couple (F i , µ i ). To each good couple (F i , µ i ) we associate the list of all flaps F ′ j which are parts of µ i and contained in F i , and we call it the list of good subflaps; this list is of size at most m. Whenever a flap F ′ j is triggered as forbidden or removed, it warns all good couples (F i , µ i ) to which it is associated (in the list of good subflaps). When, for a couple (F i , µ i ), all good subflaps of the associated list have become removed or forbidden, the flap F i is also marked as forbidden and the process continues. By Lemma 5 and by induction on the inclusion order of the flaps, the algorithm correctly marks the forbidden flaps as required. The complexity of the whole marking process of forbidden flaps is O(m • number of good couples). Thus the overall complexity of UpdateMarks is also O(m • number of good couples) plus the complexity of computing our data structure of good couples and good associated subflaps, which is also the number of good couples, multiplied by a small polynomial in the size of the graph. We discuss below this complexity for each particular case.

We also have to test, in Algorithm Bramble, whether a flap F contains some flap F ′ ∈ B f . For this purpose we construct a directed acyclic graph G f laps such that each node of this graph is a (non-trivial) flap of P and the transitive closure of the graph is the inclusion relation between flaps. Whenever a flap F ′ is put into B f , it marks all flaps F such that there exists a path from F ′ to F in G f laps as forced by inclusion. With standard techniques, this marking is linear in the size of G f laps , so it remains to ensure that the number of arcs of G f laps is moderate, which we also prove on each particular case (for further details, see Appendix B).

Theorem 5 has been stated in its most general form, and as we shall discuss in the conclusion it can be used for other parameters than treewidth. In the case of treewidth, algorithm Bramble and the UpdateMarks procedure can be further refined in order to obtain brambles and compact brambles of order k + 2, for graphs of treewidth larger than k. The running time will be, as announced in Theorem 2, O(n k+4 ) for brambles and O(n 4 r 2 ) for compact brambles, where r is the number of minimal separators of the input graph.

We point out that Algorithm UpdateMarks can be seen as a gereralization of the algorithms of [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF][START_REF] Bouchitté | Treewidth and minimum fill-in: grouping the minimal separators[END_REF][START_REF] Fomin | Exact algorithms for treewidth and minimum fill-in[END_REF]. Indeed the algorithm of Arnborg et al. [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF], deciding whether a graph has treewidth at most k in O(n k+2 ), behaves like when we call UpdateMarks on the set P k-f lap , only once, right after removing all trivial flaps (formed by a unique edge). Thus a graph is of treewidth at most k if and only if, after this run, the flap formed by the whole edge set (which is the unique flap of the trivial partition) is marked as forbidden. In a similar way, if we apply algorithm UpdateMarks on P k-pmc (to which we must add the trivial partition of E), it behaves like the algorithms of [START_REF] Bouchitté | Treewidth and minimum fill-in: grouping the minimal separators[END_REF][START_REF] Fomin | Exact algorithms for treewidth and minimum fill-in[END_REF]. Therefore it is not surprising that the data structures used in [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF][START_REF] Fomin | Exact algorithms for treewidth and minimum fill-in[END_REF] can also be used in our case in order to fasten the marking algorithm.

In both cases the key idea is that the number of good couples (or at least good couples that we really need to use) is moderate. The number of good couples is O(n k+3 ) for P ↑ k-f lap and O(n • number of potential maximal cliques) for P ↑ k-pmc . Moreover, the graph G f laps can be computed in O(n k+4 ) for P ↑ k-f lap , and in O(n 4 r 2 ) for P ↑ k-pmc . Due to space restrictions, the proofs are given in Appendix B.

Conclusion

We have presented in this article an algorithm computing brambles of large order for arbitrary graphs. The running time for the algorithm is O(n k+4 ) for computing a bramble of order k + 2, and of course we cannot expect drastic improvements since the size of the bramble itself is of order Ω(n k+1 ). There are other equivalent definitions for brambles. One of the most popular ones consists in defining a bramble of G as a set of pairwise touching connected sugraphs of G (we recall that two subgraphs touch if they share a vertex or if there is an edge between the two). The order of the bramble is the minimum size of a hitting set, i.e. of a vertex subset intersecting each of these connected subgraphs. It is clear that the two definitions are equivalent (see also [START_REF] Bodlaender | A partial k-arboretum of graphs with bounded treewidth[END_REF]). The latter definition allows, but only in some particular cases, to consider brambles of smaller size. For planar p × p grids, the "crosses" (a line plus column) form a bramble of order p; see also [START_REF] Bodlaender | Treewidth lower bounds with brambles[END_REF] for other constructions. Treewidth can be defined in terms of graph searching as a game between cops and a robber. As in many games, we can consider the graph of all possible configurations (here it has Θ(n k+2 ) vertices) and it is possible to compute [START_REF] Fomin | Nondeterministic graph searching: From pathwidth to treewidth[END_REF] which are winning configurations for the cops (treewidth at most k) and which are winning for the robber (treewidth larger than k). This can also be considered as a certificate for large treewidth, but clearly more complicated than brambles. Eventually, one can also argue that graphs of treewidth at most k can be characterized by f (k) obstructions for some function f -so the size does not depend on k. This is a consequence of the Robertson and Seymour's famous graph minor theorem, and also directly from the fact that the treewidth problem is fixed parameter tractable. Nevertheless, this function f (k) can be extremely huge. To our knowledge, the problem of defining good obstructions to tree decompositions -in the sense that these obstructions should be of moderate size and easy to manipulate -is largely open.

Another interesting question is whether our algorithm for computing brambles can be used for other tree-like decompositions. As we noted, other parameters (branchwidth, pathwidth, rankwidth...) fit into the framework of [START_REF] Amini | Partition submodular functions[END_REF][START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF] of partitioning trees and we can define P ↑ k-xxx-width -brambles in similar ways. The problem is that the size of "basic partitions" (the equivalent of our set P k-f lap ) may be exponential in n even for small k. Due to results of [START_REF] Mazoit | Décompositions algorithmiques des graphes[END_REF][START_REF] Mazoit | The branch-width of circular-arc graphs[END_REF], for branchwidth we can also restrict to connected decompositions and thus our algorithm can be used in this case with similar complexity as for treewidth.

sons as the number of flaps C l formed by the edge subset E(i) in T . The set δ T ′ (µ(j)) in T ′ is the same as the set δ T (µ(j)) in T . Indeed, the set of edges mapped on the leaves of linked subtrees T (i)(l) are flaps, so they are mutually disjoints, and hence no edge is added to δ T ′ (µ(j)). Moreover, for every flap C l , the set of edges shared with some other flaps in some E ′ (i) (other than E(i)) does not change. So the width of the partial partitioning tree (T ′ , τ ′ ) being constructed does not increase. By doing this for every internal node of T , we obtain a connected partial partitioning tree (T ′ , τ ′ ) such that each bag is contained in some bag of (T, τ ), and such that (T, τ ) and (T ′ , τ ′ ) have the same width.

⊓ ⊔

We point out that the connected partial partitioning trees are strongly related to connected tree decompositions: Definition 4. We say that a tree decomposition T D is connected if it can be rooted such that, for each node y other than the root, the set C(y) of vertices appearing in bags of the subtree T D(y), but not appearing in the bag X(x) of the father x of y, induces a connected subgraph in G.

Actually C(y) is one of the components of G -X(x). Any tree decomposition can be transformed into a connected one, such that the bags of the latter are contained in the bags of the first [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF]. Moreover the leaf bags of the connected tree decomposition are contained into leaf bags of the initial one. Some properties of potential maximal cliques. Tree decompositions of a graph G are often expressed in terms of triangulations. A graph H with the same vertex set as G is called a triangulation of G if the edge set of G is contained in the edge set of H and H is chordal (i.e. each cycle of length at least four of H has an edge between non-consecutive vertices). Every chordal graph has a tree decomposition such that the bags of the decomposition correspond to the maximal cliques of H. Conversely, consider a tree decomposition T D of G such that no bag is strictly contained into another. If we complete each bag into a clique (i.e. we add, in the graph G, all missing edges inside the bag), we obtain a triangulation H T D of G and the maximal cliques of H are exactly the bags of G. Therefore the treewidth of G can be defined as the minimum clique-size of H minus one, over all triangulations H of G. Clearly, we can restrict to minimal triangulations. A triangulation H of G is said to be minimal if no strict subgraph of H is a triangulation of G.

A set of vertices K of G is called a potential maximal clique [START_REF] Bouchitté | Treewidth and minimum fill-in: grouping the minimal separators[END_REF] if there is a minimal triangulation H of G such that K induces a maximal clique in H. In other terms, the potential maximal cliques correspond to the bags of minimal triangulations.

Let

G[K] denote the subgraph of G induced by K. Denote by C(K) = (C 1 , . . . , C p ) the connected components of G -K and let S i = N (C i ) be the neighborhood of C i in G.
The following statement is a simple characterization of potential maximal cliques.

Theorem 6 ([10]). Let K be a set of vertices of G. Then K is a potential maximal clique if and only if:

-For any

C i ∈ C(K), its neighborhood S i is strictly contained in K; -The graph G[K] {S 1 ,...,Sp} , obtained from G[K] by completing each S i into a clique, is a complete graph.
Potential maximal cliques are strongly related to minimal separators. A set of vetices S of G is a minimal separator if there are at least two distinct connected components C and D of G -S such that S = N (C) = N (D). Indeed, if K is a potential maximal clique, then the sets S i as above are exactly the minimal separators of G, contained in K [START_REF] Bouchitté | Treewidth and minimum fill-in: grouping the minimal separators[END_REF].

Moreover the number of potential maximal cliques of a graph is related to the number of minimal separators.

Theorem 7 ([11]

). Let G be a graph with n vertices, π be the number of potential maximal cliques of G and r be the number of its minimal separators. Then π ≤ nr 2 + nr + 1 and, moreover, all potential maximal cliques can be computed in O(n 4 r 2 ) time.

Several classes of graphs are known for having a "small" number of minimal separators and potential maximal cliques, in the sense that these quantities are polynomial in the size of the graph. For example, permutation graphs have O(n) minimal separators and potential maximal cliques, circular and circular-arc and weakly chordal graphs have O(n 2 ) minimal separators and O(n 3 ) potential maximal cliques -see [START_REF] Bouchitté | Treewidth and minimum fill-in: grouping the minimal separators[END_REF] for a survey.

We also know [START_REF] Fomin | Exact algorithms for treewidth and minimum fill-in[END_REF] that, given a graph, the treewidth can be computed in O(n 3 π) time, or in O(n 4 r 2 ) time.

Discussion on Lemma 4. To prove that P ↑ k-f lap is orientable, we use the same ideas as in the proof of Lemma 1. We want to prove that for any partition µ ∈ P ↑ k-f lap and any part F of µ, there is a partition ν ∈ P ↑ k-f lap finer than µ and a partial partitioning tree T ν displaying ν in which the leaf mapped on F is adjacent to the root.

Note that the partial partitioning tree of any partition in P ↑ k-f lap is connected, since every part of any partition in P k-f lap is a flap. Let T µ be a (connected) partial partitioning tree displaying µ ∈ P ↑ k-f lap . The construction in the proof of Lemma 1 can be done for any chosen initial root. Thus one can construct a (connected) partial partitioning tree T ν displaying a partition ν finer than µ, and such that the root of T ν is adjacent to the leaf mapped on F . Moreover the bags corresponding to internal nodes of T ν are exactly the bags corresponding to internal nodes of T µ , and hence the displayed partition ν of T ν is exactly the initial partition µ (in P ↑ k-f lap ). In particular this proves that P ↑ k-pmc is also orientable.

⊓ ⊔

Proof of Theorem 3. Let G = (V, E) be a graph. Let P k be the set of partitions of E having borders of size at most k + 1. By [START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF], P ↑ k is refining. P k-f lap is a subset of P k . Indeed, every partition in P k-f lap has borders of size at most k + 1, with the extra restriction that every part of the partition is a flap. Thus, by the construction of P ↑ sets, P ↑ k-f lap is a subset of P ↑ k . Let (A, A 1 , . . . , A p ) and (B, B 1 , . . . , B q ) be two partitions in P ↑ k-f lap , which are also in P ↑ k , such that A ∩ B = ∅. Let (T A , τ A ) and (T B , τ B ) be two partial partitioning trees, with displayed partitions (A, A 1 , . . . , A p ) and (B, B 1 , . . . , B q ) respectively. As P ↑ k is refining, there exists a partition (C 1 , . . . , C r ) ∈ P ↑ k finer than (A 1 , . . . , A p , B 1 , . . . , B q ). Consider a partial partitioning tree (T, τ ) with (C 1 , . . . , C r ) as its displayed partition. By Lemma 1, there exists a connected partial partitioning tree (T ′ , τ ′ ) such that each edge subset mapped on a leaf of T ′ is contained in an edge subset mapped on a leaf of T and each bag of (T ′ , τ ′ ) is contained in some bag of (T, τ ). The displayed partition of (T ′ , τ ′ ) is in P ↑ k-f lap , and hence P ↑ k-f lap contains a partition finer than (A 1 , . . . , A p , B 1 , . . . , B q ). Thus P ↑ k-f lap is refining. Unfortunately, for proving that P ↑ k-pmc is refining, we don't have the equivalent of Lemma 1 to simply deduce this from previous results. Indeed, there are small examples showing that in Lemma 1, we cannot add the extra condition that any internal bag of (T ′ , τ ′ ) is a potential maximal clique.

We sketch here the proof that P ↑ k-pmc is refining. Actually we describe with more details one of the techniques proving that P ↑ k-f lap is refining, then we adapt this proof to the case of potential maximal cliques.

Firstly, let us have a closer look at the relationship between a connected partial partitioning tree T µ displaying a partition µ ∈ P ↑ k-pmc and the associated tree decomposition. Consider this tree decomposition associated to T µ and remove trivial leaf bags (corresponding to a trivial leaf flap). The new tree decomposition T D µ has the following properties: [START_REF] Amini | Partition submodular functions[END_REF] all its internal bags are potential maximal cliques, and (2) for each leaf bag X, the intersection S between X and its neighbour X ′ is a minimal separator of G, and X \ X ′ is a connected component of G -X ′ such that S = N G (X \ X ′ ) (this can be easily deduced from Theorem 6). A tree-decomposition of graph G satisfying these two properties will be called internally-minimal. Conversely, by transforming an internally-minimal tree decomposition into a partial partitioning tree, we obtain a tree displaying an element of P ↑ k-pmc . Note that each leaf bag of the tree decomposition T D µ is either a potential maximal clique of size at most k + 1, or the set of vertices incident to a non-trivial flap of µ. Conversely, when we transform an internally-minimal tree decomposition T D into a partition µ ∈ P ↑ k-pmc , each not-trivial flap of µ corresponds to a leaf bag of the tree decomposition (the bag is formed by the vertices of G incident to the flap).

The following statement, which can be found by a little digging in the proofs of [START_REF] Bellenbaum | Two short proofs concerning tree-decompositions[END_REF], can be considered as the equivalent of Theorem 3 to tree decompositions. Theorem 8 (gluing theorem [START_REF] Bellenbaum | Two short proofs concerning tree-decompositions[END_REF]). Let T D 1 and T D 2 be two tree decompositions of G. Consider a leaf bag X of T D 1 and a leaf bag Y of T D 2 . Suppose that X and Y are noncrossing, in the sense that X (resp. Y ) intersects at most one component of G -Y (resp.

G -X).

Then there is a tree decomposition T D of G, whose decomposition tree is obtained from the union T D 1 and T D 2 by identifying the two leaves X and Y , and such that any bag Z of T D is at least as small as the corresponding bag of T D 1 or T D 2 .

Proof. Let S be a minimum-size X, Y -separator of G (i.e. ∀x ∈ X, ∀y ∈ Y , x and y are not connected in G -S). By Menger's theorem, there is a set P X (resp. P Y ) of disjoint paths of G, linking each vertex of S to some vertex of X (resp. of Y ). Let D X (resp. D Y ) be the union of connected components of G -S intersecting X (resp. Y ). First we construct a tree decomposition T D ′ 1 of G -D X , having the same tree as T D 1 , such that each bag of T D ′ 1 is smaller than the corresponding bag of T D 1 and such that the leaf whose bag is X in T D 1 has bag S in T D ′ 1 . Let X(i) be some bag of T D 1 , corresponding to some node i. In T D ′ 1 , the corresponding bag X ′ (i) is obtained from X(i) as follows. First we remove from X(i) all vertices of D X . Then for any vertex y ∈ D X ∩ X(i) such that y is on one of the paths of P X , we replace y by the endpoint of this path in S. It is easy to check that |X ′ (i)| ≤ |X(i)|, that bag X is replaced by S and one can check (see [START_REF] Bellenbaum | Two short proofs concerning tree-decompositions[END_REF] for details) that T D ′ 1 is a tree decomposition of G -D X . We point out that for each bag X(i), the vertices of X ′ (i) \ X(i) are exactly the vertices s of S such that X(i) separates s and X in the graph G.

The same operation is performed in order to transform T D 2 into a tree decomposition T D ′ 2 , where bag Y has been replaced by S. Eventually T D ′ 1 and T D ′ 2 are glued by identifying the two bags S.

⊓ ⊔

We now apply the gluing theorem to two internally-minimal tree decompositions T D 1 and T D 2 . The tree decomposition T D is not necessarily internally-minimal, but as we shall see it can be refined into an internally-minimal one. Our first remark is that the minimum-size X, Yseparator S of G (see the proof of Theorem 8 for the notations) is also a minimal separator. More precisely, D

X (resp. D Y ) is a connected component of G -S and N G (D X ) = N G (D Y ) = S.
Let i be a leaf of T D 1 (different from the leaf used for the gluing), we investigate the structure of the bag X T D (i) in the tree decomposition T D. Since T D 1 is internally-minimal, the bag X T D 1 (i) is the disjoint union of a minimal separator S(i) and a connected component

C(i) of G -S(i) such that S(i) = N G (C(i)).
Recall that, after gluing, the bag X T D (i) is obtained from the bag X T D 1 (i) by removing the vertices of X T D 1 (i) which are in D X and by adding the vertices of S such that X T D 1 (i) separates X from these vertices in graph G. Actually in this case there are no added vertices, so we also have that the leaf bags of T D are contained in the leaf bags of T D 1 and T D 2 (not only of smaller size). Let U (i) be the set of vertices of X T D (i) ∩ (S ∪ S(i)). These are the only vertices of X T D (i) which can have neighbors outside

X T D (i), in the graph G. Thus X T D (i) \ U (i) is a union of connected components D 1 (i), . . . , D p (i) of G -U (i). For any such component D j (i), its neighborhood W j (i) = N G (D j (i)
) is a minimal separator of G (see e.g. [START_REF] Bouchitté | Listing all potential maximal cliques of a graph[END_REF]). We transform the tree decomposition T D in a new one, by giving the bag U (i) to node i and adding, for each component D j (i), 1 ≤ j ≤ p, a new leaf i j with bag D j (i) ∪ W j (i). By doing this on all leaves i of the tree decomposition T D we obtain a new tree decomposition T D ′ , finer that T D, such that each leaf bag of T D ′ is contained in some leaf bag of T D. Moreover, T D ′ has well-formed leaves, in the following sense: each leaf bag of T D ′ is a union of a minimal separator W and a connected component D of G -W , such that N G (D) = W . We show how to transform such a tree decomposition into an internally-minimal one, by preserving the set of leaves. For each leaf bag D ∪ W we delete from G the set D and we complete the minimal separator W into a clique (the sets D are pairwise disjoint). Let G -be the graph obtained by these operations. Also note that T D ′ , minus its leaves of type D ∪ W , is a tree decomposition of G -. Take now a minimal triangulation of G -such that each bag of the corresponding tree decomposition T D -is contained in some internal bag of T D ′ . It is not hard to check, using Theorem 6, that each potential maximal clique of G -is also a potential maximal clique of G (see also [START_REF] Bouchitté | Treewidth and minimum fill-in: grouping the minimal separators[END_REF]). We construct an internally-minimal tree decomposition T D ′′ of G as follows. Fix a root of T D -and transform it into a connected tree decomposition. For any leaf bag D ∪ W of T D ′ , take the highest node of T D -which contains W ; such a node exists, since W induces a clique in G -. Add a leaf to this node, with bag D ∪ W . Consequently, T D ′′ is internally-minimal. The leaves of T D ′′ of type W ∪ D are contained in some leaf of T D ′ (and of T D); there might also be some other leaves, corresponding to nodes of T D -, in which case the corresponding bags are potential maximal cliques of G.

We are now ready to prove that P ↑ k-pmc is refining. Let µ 1 = (A, A 1 , . . . , A p ) and µ 2 = (B, B 1 , . . . , B q ) be two partitions in P ↑ k-pmc , with A ∩ B = ∅. Let T D 1 and T D 2 be two internally-minimal tree decompositions corresponding to partial partitionning trees of these partitions (after removing trivial bags, unless A and/or B are trivial, in which case we also keep leaf bags corresponding to these trivial flaps). We apply the gluing theorem on the bags corresponding to flaps A and B and, using the previous observations, we eventually obtain an internally-minimal tree decomposition T D. Each leaf bag of T D is either a potential maximal clique of size at most k + 1 of G, or it is of type W ∪ D and moreover the bag is included in a leaf bag of T D 1 or T D 2 . In the latter case, the flap F D formed by the edges By Lemma 7, in our algorithm UpdateMarks it is sufficient to consider good couples of type (E T ′ (y), µ T ′ (y)) as described in the lemma. Thus we restrict to good couples (F, µ) such that δ(µ) corresponds to δ(F, E \ F ) plus one vertex; moreover we may assume that flap F is non-trivial (not reduced to a single edge) since trivial flaps are removed at the initialization step. We claim that the number of such flaps is O(n k+3 ). The number of elements of P k-f lap is O(n k+1 ), since we only consider partitions µ = (F 1 , . . . , F p ) where |δ(µ)| ≤ k + 1 and each part is either an edge with boths ends in δ(µ), or it is formed by the set of edges of the input graph G, incident to a connected component of Gδ(µ). For any partition µ, the number of non-trivial flaps is at most n, thus the number of all useful flaps is m + O(n k+2 ). To each non-trivial flap F we associate at most n good couples of the form δ(F, E \ F ) plus one vertex, which achieves the proof on the number of good couples. For each good couple (F, µ) there are at most m good associated subflaps (flaps of µ, contained in F ). But here again we only need to memorize the non-trivial ones, which reduces the list to at most n elements. Altogether, the UpdateMarks algorithms works in O(n k+3 ) time, and computing the list of good flaps and the associated good (non-trivial) subflaps can be done in O(n k+4 ) time.

It remains to discuss how we test, in Algorithm Bramble, whether a flap F contains some flap F ′ ∈ B f . Recall that we want to construct a graph G f lap such that the vertex set of G f lap is the set of all flaps of P k-f lap and the arcs are such that the transitive closure of G f lap gives the inclusion order on the set of flaps. Again using the same ideas as [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF], we can show that for any two flaps F ′ ⊂ F , there is a flap F ′′ such that F ′ ⊆ F ′′ ⊂ F and, moreover, F is a flap associated to a partition µ, where δ(µ) is formed by δ(F, E \ F ) plus one vertex. Thus the arcs of the graph G f lap will only be put between flaps (F ′′ , F ) with this property. Again for a flap F we consider at most n partition µ, each of them giving at most n flaps F ′ , hence flap F has at most n 2 incoming arcs. The size of G f lap is O(n k+3 ) and the time complexity for computing this graph is O(n k+4 ). Altogether, computing a bramble of order k + 2 costs O(n k+4 ) time.

A very similar argument holds for potential maximal cliques. Recall that any partial partitioning tree of width at most k can be transformed into a connected partitioning tree of width at most k and such that, for each internal node, the border of the corresponding partition (i.e. the bag of the node) is a potential maximal clique. By [START_REF] Fomin | Exact algorithms for treewidth and minimum fill-in[END_REF], the number of good couples (F, µ) is at most nπ, where π is the number of potential maximal cliques of the input graph. By [START_REF] Bouchitté | Listing all potential maximal cliques of a graph[END_REF], a graph G with r minimal separators has O(nr 2 ) potential maximal cliques, and these potential maximal cliques can be enumerated in O(n 2 r 2 ) time. Using the arguments of [START_REF] Fomin | Exact algorithms for treewidth and minimum fill-in[END_REF], our data structures (the good couples and their associated lists of good subflaps, as well as the graph G f lap whose transitive closure is the inclusion order over flaps) can be computed within the required time bounds.

Fig. 1 .

 1 Fig. 1. The partial partitioning tree in P ↑ can be obtained by gluing the given partial partitioning trees in P in this order: ψ ⊕ ρ ⊕ ω ⊕ φ ⊕ σ (see Lemma 2 and definition of ⊕ operator).

Here we use one of the equivalent definitions of brambles, see e.g.[START_REF] Bodlaender | A partial k-arboretum of graphs with bounded treewidth[END_REF] and the Conclusion for further discussions.

We emphasys again that a partial partitioning tree might be of small width even if its leaves are mapped on big edge sets.

Acknowledgement. I.Todinca wishes to thank Fedor Fomin for fruitful discussions on this subject.

A Proofs for Section 2

Proof of Lemma 1. Let (T, τ ) be an arbitrary partial partitioning tree of G. Let us construct the desired connected partial partitioning tree (T ′ , τ ′ ).

Take an internal node i of T other than the root, j its father, and consider the edge subset E(i) (the union of all edge subsets mapped on the leaves of T (i)). If this set forms a flap for δ T (µ(j)), there is nothing to do. If not, then it forms several flaps C 1 , . . . , C p , each of these flaps C l containing one ore more leaves e 1 l , . . . , e q l of T (i). For each flap C l , take the subtree T (i)(l) of T (i) with only the leaves e l , and re-root it to i. In this new tree T ′ , i has as many of G incident to component D is included in some A i , 1 ≤ i ≤ p or some B j , 1 ≤ j ≤ q. Therefore the partition µ ∈ P ↑ k-pmc corresponding to the tree decomposition T D is a refining of (A 1 , . . . , A p , B 1 , . . . , B q ). This achieves the proof of Theorem 3.

⊓ ⊔

Proof of Theorem 4. We give here the proof of [START_REF] Lyaudet | Partitions versus sets: A case of duality[END_REF].

Let us note first that B always exists: indeed take the set B 0 corresponding to all parts of elements of P, except the singletons. It satisfies all conditions of the theorem, except the minimality. Thus it is sufficient to extract an inclusion-minimal B ⊆ B 0 satisfying conditions 2 and 3. We prove that such inclusion-minimal B is a P-bramble.

Suppose that B is not a P-bramble. Let A, B be two minimal disjoint sets in B. Since B is minimal, there exists two partitions (A ′ , A 2 , . . . , A p ), (B ′ , B 2 , . . . , B q ) ∈ P ↑ with only A ′ , B ′ ∈ B and such that A ′ ⊆ A, B ′ ⊆ B. As P ↑ is refining, there exists a partition (C 1 , . . . , C r ) finer than (A 2 , . . . , A p , B 2 , . . . , B q ). As B contains a part of every partition in P ↑ , B contains some C i , which is a subset of some A j (or B k ). Thus, as B is upper closed, it contains this A j (or B k ) -a contradiction.

⊓ ⊔

B The Bramble algorithm: complexity details

Let us detail first the case of "usual" brambles, when we work with P k-f lap . Recall that our UpdateMarks algorithm must ensure that, like in Lemma 5, a flap F will be marked as forbidden if and only if there is a partial partitioning tree T with a subtree T (x) such that all flaps mapped on leaves of T (x) are removed and the union of these flaps is F . We want to restrict to particular types of partitioning trees, which will allow to prove that we can use O(n k+3 ) good couples.

Let us sketch some of the results of Arnborg et al. [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF], on tree decompositions. Recall that we can restrict to connected tree decompositions (see Definition 4 in Appendix A). Given a rooted tree decomposition T D and a node x of T D, we denote by C T D (x) the set of vertices of G appearing in the bags of the subtree T D(x), but not in the bag of the father of x. A connected tree decomposition T D is transformed again into a connected tree decomposition T D ′ , such that each bag of T D ′ is contained in some bag of T ′ , each component C T D (x) is also a component C T D ′ (x ′ ) for some node x ′ of T D ′ , the bag roots of the two trees are the same and, most important, we have the following technical condition: for each node y of T D ′ other than the root, its bag X T D ′ (y) is formed by the neighborhood of C T D ′ (y) in the graph G, plus one vertex. In terms of partial partitioning trees, if we denote by E(y) the set of edges having at least one endpoint in C T D ′ (y), this means that the bag X T D ′ (j) is the border of the partition (E(j), E \ E(j)) of E, plus one vertex. This last result can be read as follows: Lemma 7. Let T be a connected partitioning tree corresponding to some element of P ↑ k-f lap . We can transform the tree T into another connected partitioning tree T ′ , corresponding to the same element of P ↑ k-f lap which has the following properties: 1. The roots of T ′ and T have the same associated partition; 2. For each node x of T different from the root, there is a node x ′ of T ′ such that E T (x) = E T ′ (x ′ ) and the flaps mapped on the leaves of T (x) are exactly the flaps mapped on the leaves of T ′ (x) (E T (x) denotes the union of flaps mapped on leaves of T (x) in the tree T ); 3. For each internal node y of T ′ , different from the root, we have that δ(µ T ′ (y)) is exactly δ((E T ′ (y), E \ E T ′ (y))) plus one vertex.