Guillaume Ducoffe

Sylvain Legay

Nicolas Nisse

On the complexity of computing treebreadth

During the last decade, metric properties of the bags of treedecompositions of graphs have been studied. Roughly, the length and the breadth of a tree-decomposition are the maximum diameter and radius of its bags respectively. The treelength and the treebreadth of a graph are the minimum length and breadth of its tree-decompositions respectively. Pathlength and pathbreadth are defined similarly for path-decompositions. In this paper, we answer open questions of [Dragan and Köhler, Algorithmica 2014] and [Dragan, Köhler and Leitert, SWAT 2014] about the computational complexity of treebreadth, pathbreadth and pathlength. Namely, we prove that computing these graph invariants is NP-hard. We further investigate graphs with treebreadth one, i.e., graphs that admit a tree-decomposition where each bag has a dominating vertex. We show that it is NP-complete to decide whether a graph belongs to this class. We then prove some structural properties of such graphs which allows us to design polynomial-time algorithms to decide whether a bipartite graph, resp., a planar graph, has treebreadth one.

Introduction

Tree-decompositions [START_REF] Robertson | Graph minors. II. algorithmic aspects of tree-width[END_REF] aim at decomposing graphs into pieces, called bags, organized in a tree-like manner (formal definitions are postponed to Section 1.3). Roughly, the width of a tree-decomposition is the maximum size of its bags. A lot of work has been dedicated to compute tree-decompositions with small width since such decompositions can be efficiently exploited for algorithmic purposes [START_REF] Bodlaender | Treewidth: Characterizations, applications, and computations[END_REF]. Computing the corresponding graph invariant, the treewidth of a graph G (i.e., the minimum width among all tree-decompositions of G), is NP-hard [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF] and no constant-approximation algorithm is likely to exist [START_REF] Wu | Inapproximability of treewidth and related problems[END_REF]. Moreover, reallife networks generally have a large treewidth [START_REF] De Montgolfier | Treewidth and hyperbolicity of the internet[END_REF]. These drawbacks motivated the study of other optimization criteria for tree-decompositions.

In particular, the metric properties of the bags have been studied. Roughly, the length and the breadth of a tree-decomposition are the maximum diameter and radius of its bags respectively. The corresponding graph parameters are the treelength [START_REF] Dourisboure | Tree-decompositions with bags of small diameter[END_REF] and the treebreadth [START_REF] Dragan | An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs[END_REF] respectively. Recent studies suggest that some classes of real-life networks -including biological networks and social networks -have bounded treebreadth [START_REF] Abu-Ata | Metric tree-like structures in real-world networks: an empirical study[END_REF]. This metric tree-likeness can be exploited in algorithms. For instance, bounded treebreadth graphs admit a PTAS for the Traveling Salesman problem [START_REF] Krauthgamer | Algorithms on negatively curved spaces[END_REF]. They also admit compact distance labeling schemes [START_REF] Dourisboure | Spanners for bounded tree-length graphs[END_REF]. Furthermore, the diameter and the radius of bounded treebreadth graphs can be approximated up to an additive constant in linear time [START_REF] Chepoi | Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs[END_REF]. In contrast to the above result, we emphasize that under classical complexity assumptions the diameter of general graphs cannot be approximated up to an additive constant in subquadratic time, that is prohibitive for large graphs [START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF].

On the computational side, it is known that computing the treelength is NPhard [START_REF] Lokshtanov | On the complexity of computing treelength[END_REF]. However, contrary to the treewidth, there exists a 3-approximation algorithm for computing the treelength [START_REF] Dourisboure | Tree-decompositions with bags of small diameter[END_REF]. In [START_REF] Dragan | An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs[END_REF], a 3-approximation algorithm for computing the treebreadth is presented but the computational complexity of this problem is left open. Note that, because treelength and treebreadth differ by at most a factor 2 [START_REF] Dragan | An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs[END_REF], any polynomial-time algorithm for computing the treebreadth, or an α-approximation algorithm for some α < 3/2, would improve the 3-approximation algorithm for treelength [START_REF] Dourisboure | Tree-decompositions with bags of small diameter[END_REF].

A path-decomposition of a graph is a tree-decomposition where the bags are organized according to a path structure. Treelength and treebreadth have their "path counterpart", namely the pathlength and the pathbreadth. In [START_REF] Dragan | Line-distortion, bandwidth and path-length of a graph[END_REF], they have been shown to be useful in the design of approximation algorithms for bandwidth and line-distortion. A 2-approximation (resp., a 3-approximation) algorithm is given for computing the pathlength (resp., the pathbreadth) but the computational complexity of both problems is left open.

The main contributions of this paper are to answer the open problems of [START_REF] Dragan | An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs[END_REF] and [START_REF] Dragan | Line-distortion, bandwidth and path-length of a graph[END_REF]. Namely, we prove that computing the treebreadth, pathlength and pathbreadth of graphs are all NP-hard problems.

Related work.

In contrast with treewidth [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF], deciding whether a graph has treelength at most k is NP-complete for every fixed k ≥ 2 [START_REF] Lokshtanov | On the complexity of computing treelength[END_REF]. However, the reduction used for treelength goes through weighted graphs and then goes back to unweighted graphs using rather elegant gadgets. It does not seem to us these gadgets can be easily generalized in order to apply to the treebreadth.

Relationship between treewidth and treelength (and so, treebreadth) has been investigated in [START_REF] Coudert | Diameter of Minimal Separators in Graphs[END_REF]. The two parameters are uncomparable in general graphs. For instance, cycles have treewidth at most two but treelength n/3 , while cliques have treewidth n -1 but treelength equal to one [START_REF] Dourisboure | Tree-decompositions with bags of small diameter[END_REF]. However, they differ by at most a constant ratio in the graphs with bounded genus and bounded isometric cycles [START_REF] Coudert | Diameter of Minimal Separators in Graphs[END_REF]. Hence we are also motivated in this work to better understand the structure of tree-decompositions with small width for bounded genus graphs, and to improve their computation.

Recently, the minimum eccentricity shortest-path problem -close to the problem of computing the pathlength and pathbreadth -has been proved NP-hard [START_REF] Dragan | On the minimum eccentricity shortest path problem[END_REF]. Let us point out that for every fixed k, it can be decided in polynomial time whether a graph admits a shortest-path with eccentricity at most k [START_REF] Dragan | On the minimum eccentricity shortest path problem[END_REF]. Our results will show the situation is different for pathlength and pathbreadth.

Our contributions.

On the negative side, we prove in Section 2 that computing the treebreadth is NP-hard. More precisely, we first prove that recognizing graphs with treebreadth one is NP-complete. The latter may be a bit surprising since in comparison, graphs with treelength one are exactly the chordal graphs [START_REF] Lokshtanov | On the complexity of computing treelength[END_REF], and so, they can be recognized in linear time. Our reduction has distant similarities with the one for treelength. However, it does not need any detour through weighted graphs. Then, we show that the problem of deciding whether a graph has treebreadth one is polynomially equivalent to the problem of deciding whether a graph has treebreadth at most k, for every fixed k ≥ 1.

Next, we show that deciding if a graph has pathlength at most 2 is NPhard even in the class of graphs with pathlength at most 3. We also show that deciding if a graph has pathbreadth at most 1 is NP-hard even in the class of graphs with pathbreadth at most 2. Hence, for any > 0, the pathlength and the pathbreadth cannot be approximated within a factor 3 2 -and 2 -respectively unless P = N P .

On the positive side, we present polynomial-time algorithms for deciding whether a graph has treebreadth at most one, in the class of bipartite graphs and in the class of planar graphs. Precisely, we prove that a bipartite graph has treebreadth one if and only if it can be clique-decomposed in tree-convex bipartite graphs [START_REF] Wang | Feedback vertex sets on tree convex bipartite graphs[END_REF]. Furthermore, while the planar graphs of treebreadth one are quite specific (in particular, we prove that they have treewidth at most 4), the algorithm is intricate and relies on structural properties of graphs with treebreadth one.

Due to lack of space, several proofs are only sketched or even omitted. They can be found in our technical report [START_REF] Ducoffe | On computing tree and path decompositions with metric constraints on the bags[END_REF].

Definitions and notations

Graphs in this study are finite, simple, connected and unweighted. Given a graph G = (V, E), the set

N G (v) denotes the set of neighbors of v ∈ V in G. Further- more, let N G [v] = N G (v) ∪ {v}. The distance dist G (u, v) between two vertices u, v ∈ V in G
is the minimum length (number of edges) of a path between u and v in G. We will omit the subscript when no ambiguity occurs.

A tree-decomposition (T, X ) of G is a pair consisting of a tree T and of a family X = (X t ) t∈V (T ) of subsets of V indexed by the nodes of T and satisfying:

-t∈V (T ) X t = V ; -for any edge e = {u, v} ∈ E, there exists

t ∈ V (T ) such that u, v ∈ X t ; -for any v ∈ V , {t ∈ V (T ) | v ∈ X t } induces a subtree, denoted by T v , of T .
The sets X t are called the bags of the decomposition. For any t ∈ V (T ), the diameter of the bag X t equals max v,w∈Xt dist G (v, w). We emphasize that the distance is the one in G (not in G[X t ]). The radius of X t equals min v∈V max w∈Xt dist G (v, w). We point out that the vertex v in previous definition does not necessarily belong to X t . The length of (T, X ) is the maximum diameter of its bags, while the breadth of (T, X ) is the maximum radius of its bags.

The treelength and the treebreadth of G, respectively denoted by tl(G) and tb(G), are the minimum length and breadth of its tree-decompositions, respectively. Pathlength and pathbreadth are defined similarly in the case of path decompositions, that is, when T is a path. It has been observed in [START_REF] Dragan | An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs[END_REF][START_REF] Dragan | Line-distortion, bandwidth and path-length of a graph[END_REF] that the four above parameters are contraction-closed invariants.

A tree-decomposition is called reduced if no bag is included in another one. Starting from any tree-decomposition, a reduced tree-decomposition can be obtained in polynomial time by contracting any two adjacent bags with one contained in the other until it is no more possible to do that. Note that such a process does not modify the width, the length nor the breadth of the decomposition.

In the following we will make use of the well-known Helly property in our proofs: any family of pairwise intersecting subtrees in a tree has a nonempty intersection.

Hardness of treebreadth, pathlength and pathbreadth

The main result of this section is the NP-completeness of deciding whether tb(G) ≤ k, for any fixed k ≥ 1. We first prove that the problem is NP-complete for k = 1. Then, we show that the problem of deciding the treebreadth of a graph is polynomially equivalent to the problem of recognizing graphs with treebreadth one. Using similar techniques, we prove that computing pathlength, resp., pathbreadth, is NP-hard.

We start by a structural result on graphs with treebreadth one which will be a key lemma used throughout the paper. A tree-decomposition (T, X ) of a graph is a star-decomposition if for each

t ∈ V (T ), X t ⊆ N [v] for some v ∈ X t .
That is, star-decompositions are similar to decompositions of breadth one, but the dominator of each bag has to belong to the bag itself. Lemma 1 shows that both definitions are actually equivalent.

Lemma 1. For any graph G with tb(G) ≤ 1, every reduced tree-decomposition of G of breadth one is a star-decomposition.

Proof. Let (T, X ) be any reduced tree-decomposition of G of breadth one. We will prove it is a star-decomposition. To prove it, let X t ∈ X be arbitrary and let v ∈ V be such that max w∈Xt dist G (v, w) = 1, which exists because X t has radius one. We now show that v ∈ X t . Indeed, since the subtree T v and the subtrees T w , w ∈ X t , pairwise intersect, then it comes by the Helly Property that T v ∩ w∈Xt T w = ∅ i.e., there is some bag containing {v} ∪ X t . As a result, we have that v ∈ X t because (T, X ) is a reduced tree-decomposition. The latter implies that (T, X ) is a star-decomposition because X t is arbitrary.

We then show the main result of this section.

Theorem 1. Deciding whether a graph has treebreadth one is NP-complete.

In order to prove Theorem 1, we reduce the following particular instance of Chordal Sandwich (proved to be NP-hard in [START_REF] Bodlaender | Two strikes against perfect phylogeny[END_REF]) to our problem. In [START_REF] Lokshtanov | On the complexity of computing treelength[END_REF], the author also proposed a reduction from Chordal Sandwich in order to prove that computing treelength is NP-hard. However, we will need different gadgets than in [START_REF] Lokshtanov | On the complexity of computing treelength[END_REF], and we will need different arguments to prove correctness of the reduction.

Problem 1 ( Chordal Sandwich with nK 2 ).

Input: graphs G 1 = (V, E 1 ) and G 2 = (V, E 2 ) such that E 1 ⊆ E 2 , |V | is
even and the complementary Ḡ2 of G 2 induces a perfect matching. Question: Is there a chordal graph

H = (V, E) such that E 1 ⊆ E ⊆ E 2 ?
Perhaps surprisingly, the restriction on the structure of Ḡ2 is a key element in our reduction. Indeed, we will need the following technical lemma whose proof can be found in [START_REF] Ducoffe | On computing tree and path decompositions with metric constraints on the bags[END_REF].

Lemma 2. Let G 1 = (V, E 1 ), G 2 = (V, E 2 ) such that E 1 ⊆ E 2 and Ḡ2 is a per- fect matching. Suppose that G 1 , G 2 is a yes-instance of Chordal Sandwich with nK 2 .
There exists a tree-decomposition (T,

X ) of G 1 with |X | = |V |/2+1 bags such that for every {u, v} / ∈ E 2 , T u ∩ T v = ∅ and there are two adjacent bags B u ∈ T u and B v ∈ T v such that B u \ u = B v \ v.
Proof of Theorem 1. The problem is in NP. To prove the NP-hardness, let G 1 , G 2 be any instance of Chordal Sandwich with nK 2 . Let G be the graph constructed from G 1 as follows. First, a clique V of 2n = |V | vertices is added to G 1 . Vertices v ∈ V are in one-to-one correspondance with vertices v ∈ V . Then, for every {u, v} / ∈ E 2 , u and v are respectively made adjacent to all vertices in V \ v and V \ u . Finally, we add a copy of the gadget F uv , depicted in Figure 1(a), and the vertices s uv and t uv are made adjacent to the four vertices u, v, u , v .

We will prove tb(G ) = 1 if and only if G 1 , G 2 is a yes-instance of Chordal Sandwich with nK 2 .

In one direction, assume tb(G ) = 1, let (T, X ) be a star-decomposition of G (which exists by Lemma 1). We prove that the triangulation of G 1 obtained from this star-decomposition is the desired chordal sandwich. Let (b) A subtree of the star-decomposition of G (bottom) obtained from an internal bag with degree four of (T, X ) (top). Subtrees Ti are stardecompositions of the gadgets Fu i v i . Fig. 1.

H = (V, {{u, v} | T u ∩ T v = ∅}). H is a chordal graph such that E 1 ⊆ E(H). To prove that G 1 , G 2 is a yes-instance of Chordal Sandwich with nK 2 , it suffices to prove that T u ∩ T v = ∅ for every {u, v} / ∈ E 2 . We claim that it is implied by T suv ∩ T tuv = ∅. Indeed, assume T suv ∩ T tuv = ∅ and T u ∩ T v = ∅. Since s uv , t uv ∈ N (u) ∩ N (v), T u , T v , T suv , T tuv pairwise intersect,
adjacent bags B s ∈ T suv , B t ∈ T tuv such that B s ⊆ N [s uv ] and B t ⊆ N [t uv ].
In particular, B s ∩ B t must intersect the path (y uv , w uv , z uv ) because y uv ∈ N (s uv ) and z uv ∈ N (t uv ). However, N [s uv ] ∩ N [t uv ] ∩ {y uv , w uv , z uv } = ∅, that is a contradiction. As a result, T suv ∩T tuv = ∅ and so, T u ∩T v = ∅ for any {u, v} / ∈ E 2 . Conversely, assume that G 1 , G 2 is a yes-instance of Chordal Sandwich with nK 2 . Since Ḡ2 is a perfect matching by the hypothesis, let (T, X ) be as stated in Lemma 2. We will modify (T, X ) in order to obtain a star-decomposition of G . To do so, we will use the fact that there are |V |/2 = n edges in E(T ) and the properties stated by Lemma 2. Indeed, this implies that there is a one-to-one mapping α : E(T ) → E( Ḡ2 ) between the edges of T and the non-edges of G 2 . Precisely, for any edge e = {t, s} ∈ E(T ), let α(e) = {u, v} ∈ E( Ḡ2 ) be the non-edge of G 2 such that u ∈ X t , v ∈ X s and X t \ u = X s \ v.

Intuitively, the star-decomposition (T , X ) of G is obtained as follows. For any t ∈ V (T ) with incident edges e 1 , • • • , e d , we first replace X t by a pathdecomposition (Y t,e1 , • • • , Y t,e d ). Then, for any edge e = {t, s} ∈ E(T ), an edge is added between Y t,e and Y s,e . Finally, the center-bag of some star-decomposition of the gadget F α(e) is made adjacent to Y t,e (see Figure 1(b) for an illustration).

More formally, let t ∈ V (T ) and e ∈ E(T ) incident to t, and let {u, v} = α(e). Let Y t,e = V ∪ X t ∪ {s uv , t uv } (note that Y t,e is dominated by u ∈ V ). Let e 1 , • • • , e d be the edges incident to t in T , in any order. For 1 ≤ i < d, add an edge between Y t,ei and Y t,ei+1 . For any edge e = {t, s} ∈ E(T ), add an edge between Y t,e and Y s,e . Finally, add the star-decomposition (T e , X e ) for the gadget F α(e) as depicted in Figure 1(a) and add an edge between its center and Y t,e .

The resulting (T , X ) is a star-decomposition of G , hence tb(G ) = 1.

We next show that computing the treebreadth is polynomially equivalent to the recognition of graphs with treebreadth one. Lemma 3. For every graph G, for every positive integer r, there exists a graph G r computable in polynomial time such that tb(G) ≤ r if and only if tb(G r ) ≤ 1.

Proof. Let G have vertices v 1 , v 2 , . . . , v n , and let r > 0. The graph G r is obtained from G by adding a clique U = {u 1 , u 2 , . . . , u n } so that for every 1

≤ i ≤ n, u i is adjacent to all vertices in B G (v i , r) = {x ∈ V (G) | dist G (v i , x) ≤ r}.
If tb(G) ≤ r then we claim that given a tree-decomposition (T, X ) of G with breadth at most r, one obtains a star-decomposition of G r by adding the clique U in every bag in X . Indeed, for every bag X t ∈ X , by the hypothesis there

is v i ∈ V (G) such that max x∈Xt dist G (v i , x) ≤ r, hence X t ∪ U ⊆ N G r [u i ].
Conversely, if tb(G r ) ≤ 1 then we claim that given a star-decomposition (T , X ) of G r , one obtains a tree-decomposition of G with breadth at most r by removing every vertex of the clique U from every bag in X . Indeed, for every bag X t ∈ X , by the hypothesis there is y ∈ X t such that X t ⊆ N G r [y]. Furthermore, y ∈ {u i , v i } for some 1 ≤ i ≤ n, and so, since

N G r [v i ] ⊆ N G r [u i ] by construction, X t \ U ⊆ N G r (u i ) \ U = {x ∈ V (G) | dist G (v i , x) ≤ r}.
Lemma 4. For every graph G, for every positive integer r, there exists a graph G computable in polynomial time such that tb(G) ≤ 1 if and only if tb(G ) ≤ r.

Proof. For every {u, v} ∈ E(G), let F r uv be obtained from F uv in Figure 1(a) by adding an edge {s uv , t uv } then subdividing each edge r -1 times. The graph G is obtained from G by substituting each edge {u, v} ∈ E(G) with a distinct copy of F r uv then identifying u, v with s uv , t uv .

If tb(G) ≤ 1 then let us modify a star-decomposition (T, X ) of G in a treedecomposition (T , X ) of G of breadth at most r. Clearly, every bag in X has radius at most r in G . Furthermore, let (T uv , X uv ) be the star-decomposition of F uv in Figure 1(a), with three leaf-bags and one central bag. It can be modified in a tree-decomposition of F r uv by i) adding in each bag containing both endvertices of an edge in F uv the r-1 vertices in F r uv that result from its subdivision, and ii) adding a new leaf-bag with {u, v} and the r -1 vertices that result from its subdivision. Finally, let (T , X ) be obtained from (T, X ) by adding an edge between some bag in T u ∩ T v and the central bag of T uv for every {u, v} ∈ E(G). Since (T , X ) has breadth r, tb(G ) ≤ r.

Conversely, if tb(G ) ≤ r then we claim that given a tree-decomposition (T , X ) of G of breadth at most r, one obtains a tree-decomposition of G of breadth one by removing every vertex of V (G ) \ V (G) from the bags in X . Before proving the claim, observe that no vertex in V (G ) \ V (G) can be at distance at most r from three vertices in V (G), and in case it is at distance at most r from two vertices u, v ∈ V (G) then {u, v} ∈ E(G). Therefore, in order to prove the claim it suffices to prove that u = s uv and v = t uv are in a common bag of X for every {u, v} ∈ E(G). The latter can be proved by elaborating on the same arguments as for Theorem 1.

From Lemmas 3, 4 and Theorem 1, it follows that: Theorem 2. For any fixed k ≥ 1, deciding whether a graph G has treebreadth at most k is NP-complete.

To conclude this section, we consider pathlength and pathbreadth. Due to lack of space, the proofs are postponed in [START_REF] Ducoffe | On computing tree and path decompositions with metric constraints on the bags[END_REF].

Theorem 3. For any > 0, the pathlength (resp., the pathbreadth) cannot be approximated within a factor 3 2 -(resp., 2 -) unless P = N P .

3 Graphs with treebreadth one: some polynomial cases

In this section, we investigate further the class of graphs with treebreadth one. It strictly contains chordal graphs and dually chordal graphs, well-studied graph classes in algorithmic graph theory [START_REF] Brandstädt | Dually chordal graphs[END_REF]. We first show some useful lemmas that somehow state that we can restrict our study on graphs without clique-separator. Then, we show that the problem of recognizing graphs with treebreadth one can be solved in polynomial time in the class of bipartite graphs and in the class of planar graphs.

Let G = (V, E) be a connected graph. Recall that a set S ⊂ V is a separator if G \ S is disconnected. It is called a clique-separator if S induces a complete graph. A full component for S is any connected component C of G \ S such that N (C) = S.
If C is a full component for S then we call the induced subgraph G[C ∪ S] a block. Finally, S is a minimal separator if there exist at least two full components for S.

Our objective is to prove that if a graph G has treebreadth one then so do all its blocks. In fact, we will prove a slightly more general result: Lemma 5. Let G = (V, E), S be a separator and W be the union of some connected components of

G \ S. If tb(G) = 1 and W contains a full component for S, then tb(G[W ∪ S]) = 1.
Proof. Let (T, X ) be a star-decomposition of G. We remove vertices in V \(W ∪S) from bags in X , that yields a tree-decomposition (T, X ) of G[W ∪ S]. We will prove that (T, X ) has breadth one (but is not necessarily a star-decomposition). Indeed, let X t ∈ X . By construction,

X t ⊆ X t with X t ∈ X . Let v ∈ X t satisfy X t ⊆ N G [v]. If v ∈ X t ,
then we are done. Else, since for all x / ∈ S ∪ W, N (x) ∩ (S ∪ W ) ⊆ S (because S is a separator by the hypothesis), we must have that X t ⊆ S. Let A ⊆ W be a full component for S, that exists by the hypothesis, let T A be induced by the bags intersecting A. Since T A and the subtrees T x , x ∈ X t pairwise intersect -because for all x ∈ X t , x ∈ S and so, x has a neighbour in A -, then by the Helly property there is a bag in X containing X t and intersecting A. Furthermore, any u ∈ V dominating this bag must be either in S or in A, so, in particular there is

u ∈ A ∪ S such that X t ⊆ N [u].
The converse of Lemma 5 does not hold in general (see Fig. 2), yet there are interesting cases when it does. The proof of Lemma 6 is deferred to [START_REF] Ducoffe | On computing tree and path decompositions with metric constraints on the bags[END_REF]. Recall that computing the cliqueminimal-decomposition of a graph G takes O(nm)-time, where m denotes the number of edges [START_REF] Berry | An introduction to clique minimal separator decomposition[END_REF]. By doing so, one replaces a graph G with the maximal subgraphs of G that have no clique-separator, a.k.a. atoms. So, in the following we will only consider graphs without a clique-separator, a.k.a., prime graphs.

Bipartite graphs

Bipartite graphs with treebreadth one are an interesting subclass of their own since they contain the convex bipartite graphs and the chordal bipartite graphs (i.e., bipartite graphs with no induced cycle of length at least six). In this section, we present a linear-time algorithm that decides whether a prime bipartite graph has treebreadth one, and computes a corresponding decomposition if any. Since the clique-decomposition of a given bipartite graph can be computed in linear time, this proves combined with Lemma 6 that it can be decided in linear time whether a bipartite graph has treebreadth one.

More precisely, we show that prime bipartite graphs with treebreadth one coincide with tree-convex bipartite graphs, a generalization of convex bipartite graphs [START_REF] Wang | Feedback vertex sets on tree convex bipartite graphs[END_REF]. A bipartite graph is called tree-convex if it admits a treedecomposition where the bags are the close neighbourhoods of any one side of its bipartition. By definition, tree-convex graphs have treebreadth one. The following lemma is a converse of this result. Lemma 7. Let G = (V 0 ∪V 1 , E) be a prime bipartite graph with treebreadth one. There is (T, X ) a star-decomposition of G such that either

X = {N [v 0 ] | v 0 ∈ V 0 }, or X = {N [v 1 ] | v 1 ∈ V 1 }.
Proof. Let (T, X ) be a star-decomposition of G minimizing |X |. Suppose there is some v 0 ∈ V 0 , there is t ∈ V (T ) such that X t ⊆ N G [v 0 ] (the case when there is some

v 1 ∈ V 1 , there is t ∈ V (T ) such that X t ⊆ N G [v 1 ]
is symmetrical to this one). We claim that for every t ∈ V (T ), there is

v 0 ∈ V 0 such that X t ⊆ N G [v 0 ]. By contradiction, let v 0 ∈ V 0 , v 1 ∈ V 1 , let t, t ∈ V (T ) be such that X t ⊆ N G [v 0 ], X t ⊆ N G [v 1 ]
. By connectivity of the tree T we may assume w.l.o.g. that {t, t } ∈ E(T ). Moreover, N G (v 0 ) ∩ N G (v 1 ) = ∅ because G is bipartite. Therefore, X t ∩ X t ⊆ {v 0 , v 1 }, and in particular if X t ∩ X t = {v 0 , v 1 } then v 0 , v 1 are adjacent in G. However, by the properties of a tree-decomposition this implies that X t ∩ X t is a clique-separator (either an edge or a single vertex), thus contradicting the fact that G is prime.

Let v 0 ∈ V 0 be arbitrary. We claim that there is a unique bag X t , t ∈ V (T ), containing v 0 . Indeed, any such bag X t must satisfy X t ⊆ N G [v 0 ], hence the subtree T v0 can be contracted into a single bag t∈Tv 0 X t without violating the property for the tree-decomposition to be a star-decomposition. As a result, the uniqueness of the bag X t follows from the minimality of |X |. Since X t is unique and

X t ⊆ N G [v 0 ], therefore X t = N G [v 0 ] and so, X = {N [v 0 ] | v 0 ∈ V 0 }.
As shown in [START_REF] Wang | Feedback vertex sets on tree convex bipartite graphs[END_REF], tree-convex graph recognition can be reduced to hypertree recognition, that can be done in linear time [START_REF] Brandstädt | Dually chordal graphs[END_REF]. Altogether, we obtain the following characterization of bipartite graphs with treebreadth one. Corollary 1. A bipartite graph has treebreadth one if and only if every of its atoms is tree-convex, which can be decided in linear time.

Planar graphs

In this section, we sketch a quadratic algorithm to recognize prime planar graphs of treebreadth one. Combined with Lemma 6, this shows that planar graphs of treebreadth one can be recognized in quadratic time. Our algorithm also allows to compute a corresponding decomposition in cubic time. Since the full analysis is lengthy, all proofs in this section are deferred to [START_REF] Ducoffe | On computing tree and path decompositions with metric constraints on the bags[END_REF].

Our work in this section brings more insights on tree-decompositions with small width for planar graphs. Indeed, we prove the following. Lemma 8. For every planar graph G, tb(G) ≤ 1 implies tw(G) ≤ 4.

The algorithm is recursive. Given G = (V, E), we search for a specific vertex, called a leaf-vertex, whose closed neighborhood must be a leaf-bag of a stardecomposition if tb(G) = 1. Basing on Lemma 5 and a delicate case-by-case analysis of the structure of star-decompositions, we define three types of leafvertices (e.g., see Figure 3). A vertex v is a leaf-vertex if one of the following conditions hold. Ideally, we would like to remove v from G and apply recursively our algorithm on G \ v. However, in some case tb(G \ v) = 1 while tb(G) > 1 (see Fig. 2). So, we must also add edges between vertices that must be in a common bag of a star-decomposition of G if tb(G) = 1 4 . The choice of the edges to add is made more difficult by the need for the resulting graph G to stay prime and planar in order to apply our algorithm recursively on G . To show that tb(G) = 1 if and only if the resulting graph has treebreadth one also requires tedious lemmas. Theorem 4. Recognizing planar graphs of treebreadth one can be done in quadratic time. Moreover, a star-decomposition (if any) can be computed in cubic time.

Sketch proof. Let G = (V, E) be a prime planar graph. We can assume |V | ≥ 8 and G has no star-decomposition with two bags (both cases are treated separately by exhaustive search). In such case, tb(G) = 1 implies there exists a leaf-vertex v, that can be found in linear time.

If G \ v is prime then we prove tb(G) = 1 if and only if tb(G \ v) = 1, except in the special case when v is of Type 2 or 3 and |(N (a v ) ∩ N (c v )) \ v| ≤ 2. Furthermore, we prove for the latter case that a v , c v must have two common neighbours u v , b v in G \ v (else, tb(G) > 1) and G , obtained from G by adding the edges {v, u v }, {v, b v }, is planar and prime, and it satisfies tb(G) = 1 if and only if tb(G ) = 1. So, we call the algorithm either on G or on G \ v5 .

The most difficult situation is when G \ v contains a clique-separator. This case is reduced to the one when v is of Type 2, there is an edge-separator (b v , u v ) of G \ v, and {a v , u v } / ∈ E. Then, we aim at applying the algorithm recursively on G , obtained from G\v by adding the edge {a v , c v }. However, tb(G ) = 1 does not imply tb(G) = 1 in general. We prove it is the case if u v , c v are nonadjacent or N (u v ) ∩ N (a v ) does not disconnect a v from u v in G \ (c v , v).

Else, we compute a plane embedding of G, and a vertex x ∈ N (a v ) ∩ N (u v ) such that: v, c v and all other common neighbours of a v , u v are in a same region R, bounded by (a v , x, u v , b v ). We wish to create an a v u v -path in V \R by adding edges in N (b v ) ∩ N (x). In doing so, we go back to the previous subcase as now N (a v ) ∩ N (u v ) is no more a a v u v -separator of G \ (c v , v). However, we have to ensure that it is possible to add such a path in V \ R, and that its addition does not affect the value of treebreadth for the graph. We prove it is the case unless V ⊆ R (in which case we apply the algorithm recursively on G , obtained from G by identifying b v with x), or if there is a leaf-vertex l ∈ N (b v ) ∩ N (x). Furthermore, in the latter case we replace v with l in the above analysis, i.e., l becomes the actual leaf-vertex to be considered.

Additional properties are needed in order to prove the algorithm terminates, and that it does so in a linear number of steps.

Conclusion.

We conclude this paper by some questions that remain open. First, it would be interesting to know the complexity of deciding the treebreadth of planar graphs. Second, all the reductions presented in this paper rely on constructions containing large clique or clique-minor. We left open the problem of recognizing graphs with tree-breadth one in the class of graphs with bounded treewidth or bounded clique-number. More generally, is the problem of computing the treebreadth Fixed-Parameter Tractable when it is parameterized by the treewidth or by the size of a largest clique-minor?

  there is a bag with u, v, s uv , t uv by the Helly property. The latter contradicts that (T, X ) is a stardecomposition because no vertex dominates the four vertices. Hence the claim is proved. So, let us prove that T suv ∩ T tuv = ∅. By contradiction, if T suv ∩ T tuv = ∅ then every bag B onto the path between T suv and T tuv must contain c uv , x uv . Since N [c uv ] ∩ N [x uv ] = {s uv , t uv } and (T, X ) is a star-decomposition, it implies either s uv ∈ B and B ⊆ N [s uv ] or t uv ∈ B and B ⊆ N [t uv ]. So, there are two Gadget Fuv (top) with a star-decomposition of Fuv (bottom).

Fig. 2 .Lemma 6 .

 26 Fig. 2. S = {u, v} separates G in two subgraphs of treebreadth 1. However, = 2.

Type 1 . 3 Fig. 3 .

 133 Fig. 3. The three kinds of leaf-vertices.

We aim at turning the separator N (v) into a clique. However, we cannot do that directly since it would break the distances in G, and the graph needs to stay planar.

When v is of Type 1 we call the algorithm on G , obtained from G \ v by contracting the internal nodes of Πv to an edge, in order to obtain a quadratic complexity.

This work is partially supported by ANR project Stint under reference ANR-13-BS02-0007 and ANR program "Investments for the Future" under reference ANR-11-LABX-0031-01.