Guillaume Mescoff

Christophe Paul

Dimitrios M Thilikos

A polynomial time algorithm to compute the connected treewidth of a series-parallel graph *

Keywords: Graph decompositions, Graph Classes, Width parameters, Combinatorial algorithms, Series-parallel graphs, Treewidth, Connected treewidth, Dynamic programming

It is well known that the treewidth of a graph G corresponds to the node search number where a team of searchers is pursuing a fugitive that is lazy and invisible (or alternatively is agile and visible) and has the ability to move with infinite speed via unguarded paths. Recently, monotone and connected node search strategies have been considered. A search strategy is monotone if it prevents the fugitive from pervading again areas from where he had been expelled and is connected if, at each step, the set of vertices that is or has been occupied by the searchers induces a connected subgraph of G. It has been shown that the corresponding connected and monotone search number of a graph G can be expressed as the connected treewidth, denoted ctw(G), that is defined as the minimum width of a rooted treedecomposition (X , T, r), where the union of the bags corresponding to the nodes of a path of T containing the root r is connected in G. In this paper, we initiate the algorithmic study of connected treewidth. We design a O(n 2 • log n)-time dynamic programming algorithm to compute the connected treewidth of biconnected series-parallel graphs. At the price of an extra n factor in the running time, our algorithm generalizes to graphs of treewidth at most two.

Introduction

Since its introduction [START_REF] Bertelé | Nonserial dynamic programming[END_REF][START_REF] Halin | s-functions for graphs[END_REF][START_REF] Robertson | Graph minors III. planar tree-width[END_REF], the concept of treewidth of a graph has led to major advancements in graph theory. The treewidth parameter, denoted by tw, is central to the design of efficient graph algorithms (see [START_REF] Arnborg | Efficient algorithms for combinatorial problems on graphs with bounded decomposability -a survey[END_REF] for a survey on early works in this direction and [START_REF] Bodlaender | Combinatorial optimization on graphs of bounded treewidth[END_REF] for a recent survey). According to the theorem of Courcelle [START_REF] Courcelle | The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues[END_REF], properties expressible in MSO 2 logic can be tested in parameterized linear time on graph of bounded treewidth. This result established treewidth as an important structural parameter in the context of parameterized complexity [START_REF] Downey | Parameterized complexity[END_REF]. Treewidth can be defined in several equivalent ways, while the standard definition is by means of a tree-decomposition (see Section 2). During the last two decades, a number of width-parameters have been introduced as combinatorial variants or alternatives to treewidth (see [START_REF] Hlineny | Width parameters beyond tree-width and their applications[END_REF] for a survey on width parameters). This paper deals with the connected treewidth parameter, a new variant of treewidth that is motivated by the study of connected search games in graphs.

A node search game is a game opposing a group of searchers and a fugitive, occupying the vertices of a graph. In a search strategy, one searcher may either be placed to or removed from a vertex and a winning search strategy is a sequence of moves of the searchers that eventually leads to the capture of the fugitive. The capture of the fugitive happens when a searcher lands on the vertex occupied by the fugitive while the fugitive cannot escape along a searcher-free path. The cost of a search strategy is the maximum number of searchers simultaneously occupying vertices of the graph. The clean territory during some step of the game is the set of vertices from which the fugitive has been, so far, expelled by the searchers' strategy. A strategy is monotone if it guarantees that the fugitive will not be able to visit an already cleaned territory. Also, a strategy is connected if it guarantees, that at any step, the clean territory induces a connected graph. The fugitive can be lazy or agile. Being lazy means that the fugitive is staying at his position, as long as a searcher is not moving on that position. An agile fugitive may move at any time regardless of the move of the searchers. Also a fugitive can be visible or invisible in the sense that the searcher's strategy may or may not take into account the current position of the fugitive. The node search number of a graph (for some of the above variants) is the minimum cost of a winning search strategy.

It is well-known that the search number against an invisible and lazy fugitive is equal to treewidth plus one, while the same quantity is also equal to the search number against a visible and agile fugitive [START_REF] Dendris | Fugitive-search games on graphs and related parameters[END_REF][START_REF] Seymour | Graph searching and min-max theorem for tree-width[END_REF]. On the other hand, if the fugitive is invisible and agile, then the corresponding search number is equal to the parameter of pathwidth plus one [START_REF] Kirousis | Searching and pebbling[END_REF][START_REF] Möhring | Graph problems related to gate matrix layout and PLA folding[END_REF][START_REF] Kirousis | Interval graphs and searching[END_REF][START_REF] Kinnersley | The vertex separation number of a graph equals its path-width[END_REF]. Moreover all the aforementioned versions of the game are monotone in the sense that, for every search strategy, there is a monotone one with the same cost [START_REF] Bienstock | Monotonicity in graph searching[END_REF][START_REF] Seymour | Graph searching and min-max theorem for tree-width[END_REF]. In this paper, we deal only with monotone version node search.

Interestingly, the motivating story of one of the seminal papers [START_REF] Parsons | Pursuit-evasion in a graph[END_REF] on graph searching was inspired by an earlier article of the Breisch in Southwestern Cavers Journal [START_REF] Breisch | An intuitive approach to speleotopology[END_REF]. This paper concerned speleotopological explorations, which are, by essence, connected explorations as the searchers cannot "teleport" to a vertex that is away from the current clean territory. The connectivity constraint was considered for the first time in [START_REF] Barrière | Searching is not jumping[END_REF][START_REF] Barrière | Connected graph searching[END_REF], where the price of connectivity, defined as the ratio between monotone connected node search number (for some of the considered strategy variants) and the node search number, was first considered. In [START_REF] Fraigniaud | Monotony properties of connected visible graph searching[END_REF][START_REF] Fraigniaud | Monotony properties of connected visible graph searching[END_REF], it was proven that the price of connectivity for monotone node search against a visible and agile fugitive (or, equivalently, an invisible and lazy one) is Θ(log n). Dereniowski [START_REF] Dereniowski | From pathwidth to connected pathwidth[END_REF] introduced the notion of connected pathwidth of a graph, denoted cpw(G) and showed its equivalence with the monotone node search number against an invisible and agile fugitive. He proved that, for every graph G, cpw(G) 2 • pw(G) + O(1), henceforth resolving the question of the price of connectivity for a monotone node search against an invisible and agile fugitive. Extending the work of [START_REF] Dereniowski | From pathwidth to connected pathwidth[END_REF], Adler et al. [START_REF] Adler | Connected search for a lazy robber[END_REF] recently introduced a definition of connected treewidth, denoted hereafter ctw(G). They proved that, as for treewidth, the connected treewidth parameter is equivalent to the connected monotone node search number against an invisible and lazy fugitive and, as in the non-connected setting, the same holds for the visible and agile case. Also, they proved that connected treewidth is equivalent to a connected variant of the tree vertex separation number (see Section 2).

In this paper, we are interested in the problem of computing the connected treewidth of a graph. So far, very little is known on the algorithmic aspects of the connected treewidth and connected pathwidth parameters. First of all, checking, given a graph G and an integer k, whether the connected treewidth (or the connected pathwidth) is at most k is an NP-complete problem (see Theorem 4). This means that, in general, we may not expect any polynomial algorithm for computing connected treewidth. Very recently, the problem of deciding cpw(G) ≤ k was shown to be fixed parameterized tractable [START_REF] Kanté | A linear fixed parameter tractable algorithm for connected pathwidth[END_REF], improving an n O(k 2 ) -time algorithm [START_REF] Dereniowski | Finding small-width connected path decomposition in polynomial time[END_REF]. An explanation for this lack of algorithmic results partially relies on the fact that, unlike pathwidth and treewidth, connected treewidth and connected pathwidth parameters do not enjoy nice combinatorial properties such as closeness under taking of minors. Interestingly, both parameters are closed under contractions [START_REF] Adler | Connected search for a lazy robber[END_REF]. However, for graph contractions, there is no analogue of the algorithmic machinery developed in the context of graph minors (see Section 4 for a more developed discussion).

We stress that connected treewidth may be arbitrarily bigger than treewidth. For instance, consider a complete binary tree of height k, introduce a new vertex and make it adjacent to all the leaves of the tree. As observed in [START_REF] Adler | Connected search for a lazy robber[END_REF], this graph has connected treewidth k while it is a series-parallel graph that has treewidth 2.

The above motivated us to initiate the study of computing the connected treewidth on the class of series-parallel graphs. First introduced by Macmahon in 1982 [START_REF] Macmahon | The combinations of resistances. The Electrician[END_REF] (see also [START_REF] Riordan | The number of two-terminal series-parallel networks[END_REF]), seriesparallel graphs are essentially graphs of treewidth at most two [START_REF] Duffin | Topology of series-paralle networks[END_REF]. More precisely, a graph has treewidth at most two if and only if each of its biconnected components induces a series-parallel graph. The recursive construction, by means of series and parallel composition (see Section 2), of series-parallel graphs allows to solve a large number of NP-hard problems in polynomial (or even linear) time, see for example [START_REF] Bern | Why certain subgraph computations require only linear time[END_REF][START_REF] Bern | Linear time computation of optimal subgraphs of decomposable graphs[END_REF][START_REF] Hassin | Efficient algorithms for optimization and selection on seriesparallel graphs[END_REF]. It follows that the class of series-parallel graphs, among others, forms a natural test bed for the existence of efficient graph algorithms [START_REF] Borie | Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families[END_REF].

In this paper, we design a O(n 2 • log n)-time algorithm to compute the connected treewidth of a biconnected series-parallel graph. The algorithm is extended to a O(n 3 • log n)-algorithm for graphs of treewidth at most 2. This result constitutes a first step toward the computation of connected treewidth parameterized by treewidth (see Section 4 for a discussion).

Preliminaries

We use standard notations for graphs, as for example in [START_REF] Diestel | Graph theory[END_REF]. We consider undirected and simple graphs. We let G = (V, E) denote a graph on n vertices, with V = V (G) its vertex set and

E = E(G) its edge set. A vertex x is a neighbor of y if xy is an edge of E. If S is a subset of V, then G[S]
is the subgraph of G induced by S. A path P between vertex x and y is called an (x, y)-path and the vertices of P distinct from x and y are the internal vertices of P . A vertex x ∈ V is a cut vertex if the removal of x strictly increases the number of connected components of the graph. A graph is biconnected if it is connected and does not contain a cut vertex. Given an integer q, we use [q] as a shortcut for the set {1, . . . , q}.

A layout σ of a graph G = (V, E) is a total ordering of its vertices, in other words σ is a bijection from V to [n]. For two vertices x and y, we write x < σ y if σ(x) < σ(y). We define σ <i = {x ∈ V | σ(x) < i} (the sets σ >i , σ ≤i and σ ≥i are similarly defined). If S is a subset of V, then σ[S] is the layout of G[S] such that for every x, y ∈ S, σ(x) < σ(y) if and only if σ[S](x) < σ[S](y). Let σ 1 and σ 2 be two layouts on disjoint vertex sets V 1 and V 2 . Then σ = σ 1 ⊙ σ 2 , the concatenation of σ 1 and σ 2 , is the layout on V 1 ∪ V 2 such that for every

x 1 ∈ V 1 and every x 2 ∈ V 2 , σ(x 1 ) < σ(x 2 ), σ[V 1 ] = σ 1 and σ[V 2 ] = σ 2 .

Series-parallel graphs

A 2-terminal graph is a pair G = (G, (x, y)) where G = (V, E) is a graph and (x, y) is a pair of distinguished vertices, hereafter called the terminals. Consider two 2-terminal graphs (G 1 , (x 1 , y 1 )) and (G 2 , (x 2 , y 2 )), where G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ). Then:

• the series-composition, denoted (G 1 , (x 1 , y 1 )) ⊗ (G 2 , (x 2 , y 2 )), yields the 2-terminal graph (G, (x 1 , y 2 )) with G being the graph obtained by identifying the terminal y 1 with x 2 ;

• the parallel-composition, denoted (G Observe that from the definition above, we may generate multi-graphs. However, in this paper we only consider simple graphs. Our results extend easily to multi-graphs: observe that if G * is the graph obtained from G after suppressing multiple edges to simple ones, then ctw(G) = ctw(G * ). When it is clear from the context, G will denote the 2-terminal series-parallel graph (G, (x, y)). Observe that a series-parallel graph G can be represented by a so-called SPtree T (G). The leaves of T (G) are labelled by the edges of G. Every internal node of T (G) is labelled by a composition operation (⊕ or ⊗) and a pair of terminal vertices. For an internal node t of T (G), we let T t denote the subtree of T (G) rooted at t and V t the subset of vertices incident to an edge labelling a leaf of T t . Suppose that t is labelled (⊗, (x t , y t )), then the node t represents the 2-terminal graph (G[V t ], (x t , y t )). Theorem 1. [START_REF] Eppstein | Parallel recognition of series-parallel graphs[END_REF] If a graph G = (V, E) is a biconnected series-parallel graph and xy ∈ E, then (G, (x, y)) is a 2-terminal series-parallel graph.

Theorem 1 can be rephrased as follows: if xy is an edge of a biconnected series-parallel graph, then G = (G, (x, y)) is a 2-terminal series-parallel graph such that G = (G 1 , (x, y))⊕(G 2 , (x, y)) where G 1 = ({x, y}, {xy}) and G 2 = (V, E \ {xy}). Theorem 2. [START_REF] Valdes | The recognition of series-parallel digraphs[END_REF] The problem of testing whether a graph G is series-parallel can be solved in linear time. Moreover if G is a biconnected series-parallel graph, then a SP-tree of (G, (x, y)), where xy is an edge, can be build in linear time.

Connected tree-decomposition and connected layouts

A tree-decomposition of a graph G = (V, E) is pair (T, F) where T = (V T , E T ) is a tree and

F = {X t ⊆ V | t ∈ V T } such that 1. t∈V T X t = V ;
2. for every edge xy ∈ E, there exists a node t ∈ V T such that {x, y} ⊆ X t ; 3. for every vertex x ∈ V, the set {t ∈ V T | x ∈ X t } induces a connected subgraph of T .

We refer to V T as the set of nodes of T and the sets of F as the bags of (T, F). The width of a tree-decomposition (T,

F) is width(T, F) = max{|X| -1 | X ∈ F} and the treewidth of a graph G is tw(G) = min{width(T, F) | (T, F) is a tree-decomposition of G}
For two nodes u and v of V T , we define P u,v as the unique path between u and v in T and the set V u,v ⊆ V as t∈Puv X t . A tree-decomposition (T, F) is connected if there exists a node r ∈ V T such that for every node

u ∈ V T , the subgraph G[V r,u ] is connected. Then the connected treewidth of a graph G is ctw(G) = min{width(T, F) | (T, F) is a connected tree-decomposition of G} A layout σ of G is connected if for every i ∈ [n], the subgraph G[σ ≤i ] is connected. We let L c (G) be the set of connected layouts of a graph G. For every v ∈ V, we define the supporting set of v as S σ (v) = x ∈ V (G) | σ(x) < σ(v)
and there exists a (x, v)-path P such that every internal vertex y of P satisfies σ(y) > σ(v)}.

We set cost(G, σ) = max{|S σ (v)| | v ∈ V }. The tree vertex separation number of a graph is defined as vs(G) = min{cost(G, σ) | σ ∈ L(G)}.
When restricting to the set of connected layouts, we obtain the connected tree vertex separation number

cvs(G) = min{cost(G, σ) | σ ∈ L c (G)}. Theorem 3 ([1]). For every graph G = (V, E), we have ctw(G) = ctvs(G).
Notice that if in the above definitions we drop the connectivity demand from the considered layouts, we have that tw(G) = vs(G) providing an alternative layout-definition of the parameter of treewidth, as observed in [START_REF] Arnborg | Efficient algorithms for combinatorial problems on graphs with bounded decomposability -a survey[END_REF][START_REF] Dendris | Fugitive-search games on graphs and related parameters[END_REF]. It is known that deciding whether tw(G) ≤ k is an NPcomplete problem [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF]. An easy reduction of treewidth to connected treewidth is the following: consider a graph G, add a vertex v new , and make v new adjacent to all the vertices of G. We call the new graph G + . It follows, as a direct consequence of the layout definitions, that ctw(G + ) = tw(G) + 1. We conclude to the following. Theorem 4. The problem of deciding, given a graph G and an integer k, whether ctw(G) ≤ k is NP-complete.

Rooted graphs and extended graphs

Rooted graphs. A rooted graph is a pair (G, R) where G = (V, E) is a graph and R ⊆ V is a subset of vertices, hereafter called roots. The definition of a rooted graph naturally extends to two-terminal graphs. If G = (G, (x, y)) is a series-parallel graph and R ⊆ V a set of roots, then the corresponding rooted two-terminal graph will be denoted by (G, R). Observe that the set of roots R may be different from the terminal pair (x, y).

A rooted graph (G, R) is connected if and only if every connected component of G contains a root from R. A rooted layout of (G, R) is a layout σ of G such that σ ≤|R| = R. Based on this, the notion of connected layout naturally extends to rooted graphs and rooted layouts as follows.

A rooted layout σ of (G, R) is connected if for every i, |R| < i ≤ n, (G[σ ≤i ], R) is a connected rooted graph. Extended graphs. Let G = (G, (x, y)) be a 2-terminal graph where G = (V, E). Suppose that F ⊆ V 2 \ E(G), i.e.
, F is a subset of non-edges of G. We define the extended graph G +F as the 2-terminal graph (G +F , (x, y)) where G +F = (V, E ∪ F ). The edges in E are called solid edges, while the edges of F are called fictive edges. Hereafter the 2-terminal graph G (and the graph G respectively) is called the solid graph of G +F (and G +F respectively).

We define the connected components of the extended graph G +F as the connected components of its solid graph G. In particular, G +F is connected if and only if G is connected. Thereby, we say a vertex is isolated in G +F if it is isolated in G. Likewise, we say that two vertices are adjacent in G +F if they are in G. Therefore the neighbourhood N (v) of a vertex v in G +F is its neighbourhood in G, while its extended neighbourhood N +F (v) also comprises every vertex u such that uv ∈ F (we say that u is an extended-neighbour of v). The purpose of introducing fictive edges is not to augment the connectivity of the solid graph but to keep track of cumulative cost in the recursive calls of the dynamic programming algorithm while computing the connected treewidth of a series-parallel graph.

This connectivity definition of an extended graph also transfers to (rooted) layouts. More precisely, if R ⊆ V is a set of roots and G +F an extended graph, then (G +F , R) is a rooted extended graph. A layout σ of (G +F , R) is connected if and only if it is a connected layout of (G, R). Observe that if G +F is not connected, then a connected layout of G +F exists if and only if every connected component of G +F contains a root from R.

An extended path of G +F is a path that may contain a fictive edge of F, while a solid path in G +F is a path of G, that is, a path that only contains solid edges. In a layout σ of the extended graph G +F , the extended supporting set of vertex v is:

S (e) σ (v) = x ∈ V | σ(x) < σ(v)
and there exists an extended (x, v)-path P such that every internal vertex y of P belongs to σ >i }.

The definitions of the extended cost ecost(G +F , σ) and of the extended connected tree vertex separation number ectvs(G +F ) follow accordingly:

ecvs(G +F ) = min{ecost(G +F , σ) | σ ∈ L c (G +F )},
where ecost(G +F , σ) = max{|S

(e) σ (v)| | v ∈ V }.

A dynamic programming algorithm

Before describing the dynamic programming algorithm to compute the connected treewidth of treewidth at most 2 graphs, we examine the case of biconnected series-parallel graphs. More precisely, we show how to derive the connected treewidth of a series-parallel graph depending on whether it results from a series or from a parallel composition. To handle these recursion steps, we have to manipulate extended series-parallel graphs.

Biconnected series-parallel graphs

In this section, we let G = (G, (x, y)) be a series-parallel graph such that G = (V, E). We suppose that G results from the series or the parallel composition of

G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ).
When dealing with the 2-terminal graphs G 1 and G 2 , the terminal pairs will be clear from the context.

Parallel composition

Lemma 1. Let (G +∅ , R) be a rooted extended graph such that R = {x, y} and 2). Then

G = G 1 ⊕ G 2 with G 1 = (G 1 , (x, y)) and G 2 = (G 2 , (x, y)) (see Figure
ectvs(G +∅ , R) = max ectvs(G +∅ 1 , R), ectvs(G +∅ 2 , R) .
Proof. Let σ * ∈ L c (G +∅ , R) be a connected layout of minimum cost. From σ * , we define a layout σ of (G +∅ , R) as follows: 1). Observe that as {x, y} separates V 1 from V 2 and as

σ = σ * [V 1 ] ⊙ σ * [V 2 \ {x, y}] (see Figure
σ * ∈ L c (G +∅ , R), it follows that σ ∈ L c (G +∅ , R), σ 1 = σ[V 1 ] ∈ L c (G +∅ 1 , R) and σ 2 = σ[V 2 ] ∈ L c (G +∅ 2 , R). Moreover, {x, y} separating V 1 from V 2 implies that for every vertex v 1 ∈ V 1 \ {x, y}, we have S (e) σ * (v 1 ) = S (e) σ 1 (v 1 ) ⊆ V 1 and that for every vertex v 2 ∈ V 2 \ {x, y}, we have S (e) σ * (v 2 ) = S (e) σ 2 (v 2 ) ⊆ V 2 . It follows that for every vertex v ∈ V \ {x, y}, S (e) σ * (v) = S (e) σ (v), implying that ecost(G +∅ , σ) = ecost(G +∅ , σ * ).
If G = G 1 ⊕ G 2 , then we have ectvs(G +∅ , R) = max ectvs(G +∅ 1 , R), ectvs(G +∅ 2 , R) .
To conclude, we observe that if

τ 1 ∈ L c (G +∅ 1 , R) and τ 2 ∈ L c (G +∅ 2 , R), then τ = τ 1 ⊙ τ 2 [V 2 \ {x, y}] belongs to L c (G +∅ , R) and that ecost(G +∅ , τ ) = max{ecost(G +∅ 1 , τ 1 ), ecost(G +∅ 2 , τ 2 )}. So the optimality of σ * and σ imply that ectvs(G +∅ , R) = max ectvs(G +∅ 1 , R), ectvs(G +∅ 2 , R) . Lemma 2. Let (G +F , R) be a rooted extended graph such that R = {x, r 1 . . . , r k } (with k > 0), r 1 , . . . r k are isolated vertices (in G), F = {yr i | i ∈ [k]} and (G[V \ {r 1 , . . . , r k }], (x, y)) = G 1 ⊕ G 2 with G 1 = (G 1 , (x, y)
) and G 2 = (G 2 , (x, y)) (see Figure 3). Then

ectvs(G +F , R) = min        max ectvs(G[V 1 ∪ R] +F ∪{xy} , R), ectvs(G +∅ 2 , {x, y}) max ectvs(G[V 2 ∪ R] +F ∪{xy} , R), ectvs(G +∅ 1 , {x, y})        .
Proof. We observe that G +F contains k isolated vertices, the root vertices r 1 , . . . , r k , and a connected component resulting from a parallel composition. Let σ * ∈ L c (G +F , R) be a connected layout of minimum cost. Consider the neighbor v of y so that σ * (v) is minimized. By the connectivity of σ * , σ * (v) < σ * (y). Suppose without loss of generality that v ∈ V 1 . The case v ∈ V 2 is symmetric. Observe that v can be the vertex x, in which case it can arbitrarily be considered as a vertex of V 1 and V 2 ). From σ * , we define the layout 1).

σ 1 = σ[V 1 ∪ R] of (G[V 1 ∪ R] +F ∪{xy} , R) and the layout σ 2 = σ[V 2 ] of (G 2 , {x, y}), where σ = r 1 , . . . , r k ⊙ σ * [V 1 ] ⊙ σ * [V 2 \ {x, y}] is a layout of (G +F , R) (see Figure
Claim 1. σ 1 ∈ L c (G[V 1 ∪ R] +F ∪{xy} , R), σ 2 ∈ L c (G 2 , {x, y}) and σ ∈ L c (G +F , R).
Proof of claim. Let v 1 be a vertex of V 1 distinct from x and y. Observe that every neighbor of v 1 belongs to V 1 . By the assumption above, we know that y has a neighbor v ∈ V 1 prior to it in σ * . As the relative ordering between vertices of V 1 is left unchanged, every vertex of V 1 \ {x} has a neighbor prior to it in σ as well. This implies that

σ 1 ∈ L c (G[V 1 ∪ R] +F ∪{xy} , R).
Consider now a vertex v 2 ∈ V 2 distinct from x and y. As in the previous case, every neighbor of v 2 belongs to V 2 . As the relative ordering between vertices of V 2 has only been modified by moving y ahead, v 2 has a neighbor prior to it in σ. This implies that

σ 2 ∈ L c (G 2 , {x, y}) and that σ ∈ L c (G +F , R). ✸ Claim 2. ecost((G +F , R), σ) = ecost((G +F , R), σ * ).
Proof of claim. We first consider a vertex

v 1 ∈ V 1 . By construction, we have σ * [V 1 ] = σ[V 1 ]
and for every vertex

v 2 ∈ V 2 \ {x, y}, σ(v 1 ) σ(v 2 ). It follows that S (e) σ (v 1 ) ⊆ V 1 ∪ R. Suppose that σ(v 1 ) > σ(y). As {x, y} separates v 1 from the vertices of V 2 ∪ {r 1 , . . . , r k }, we have S (e) σ (v 1 ) = S (e) σ * (v 1 ). Suppose that σ(v 1 ) ≤ σ(y). We observe that if for i ∈ [k], r i ∈ S (e)
σ (v 1 ), then there exists a (v 1 , y)-path P in G 1 such that every vertex v ∈ P satisfies σ(v 1 ) ≤ σ(v).

Similarly, if u ∈ V 1 belongs to S (e)
σ (v 1 ), then there exists a (v 1 , u)-path P ′ in G 1 such that every vertex v ′ ∈ P ′ distinct from u satisfies σ(v 1 ) ≤ σ(v ′ ). The existence of the paths P and P ′ is a consequence of the fact that {x, y} separates the vertices of V 1 \ {x, y} from the rest of the graph. As Let v 2 be a vertex of V 2 \ {x, y}. Observe that, as {x, y} separates the vertices of V 2 \ {x, y} from the vertices of R ∪ V 1 \ {x, y} and as σ(x) < σ(y) < σ(v 2 ), we have

σ * [V 1 ∪ R] = σ[V 1 ∪ R], we have σ * (v 1 ) ≤ σ * (v) and σ * (v 1 ) ≤ σ * (v ′ ). It follows that r i , u ∈ S (e) σ * (v 1 ), implying in turn that |S (e) σ (v 1 )| ≤ |S (e) σ * (v 1 )|. G 1 G 2 r 1 r i r k y x G 1 r 1 r i r k y x G 2 y x
S (e) σ (v 2 ) ⊆ V 2 . As σ[V 2 \ {y}] = σ * [V 2 \ {y}], every vertex u ∈ V 2 \ {y} that belongs to S (e) σ (v 2 ) also belongs to S (e) σ * (v 2 ). Suppose that y ∈ S (e)
σ (v 2 ). Then there exists a (y, v 2 )-path P such that every internal vertex

u of P satisfies σ(v 2 ) < σ(u). As σ[V 2 \ {y}] = σ * [V 2 \ {y}], we also have σ * (v 2 ) < σ * (v).
Let us distinguish two cases:

• If σ * (y) < σ * (v 2 ), then y ∈ S (e) σ (v 2 ) implying that S (e) σ (v 2 ) ⊆ S (e) σ * (v 2 ).
• Otherwise, σ * (y) > σ * (v 2 ) and then y / ∈ S (e) σ * (v 2 ). But in that case, let us recall that by assumption the first neighbor v of y in σ * belongs to

V 1 . It follows that v ∈ S (e) σ * (v 2 ). As we argue that S (e) σ (v 2 ) ⊆ V 2 , v ∈ S (e) σ * (v 2 ) \ S (e) σ (v 2 ). So v is a replacement vertex for y in S (e) σ * (v 2 ), implying that |S (e) σ (v 2 )| ≤ |S (e) σ * (v 2 )|. So we proved that ecost((G +F , R), σ) ≤ ecost((G +F , R), σ * ). As by Claim 1, σ ∈ L c (G +F , R), the optimality of σ * implies that ecost((G +F , R), σ) = ecost((G +F , R), σ * ). ✸
Let us now conclude the proof. Claim 1, Claim 2 and the optimality of σ * imply that σ is a connected layout of G +F of minimum cost. By Claim 1, we have

σ 1 = σ[V 1 ∪ R] ∈ L c (G[V 1 ∪ R] +F ∪{xy} , R). Observe that in the extended graph G[V 1 ∪R] +F ∪{xy}
, the edge xy simulates every (x, y)-path of G whose internal vertices belong to V 2 . It follows that for every vertex

v 1 ∈ V 1 ∪R, S (e) σ (v 1 ) = S (e) σ 1 (v 1 ). Likewise, by Claim 1, we know that σ 2 = σ[V 2 ] ∈ L c (G 2 , {x, y}).
As {x, y} separates the vertices of V 2 from the other vertices, for every v 2 ∈ V 2 \ {x, y}, we have

S (e) σ (v 2 ) = S (e) σ 2 (v 2 ). It follows that ectvs(G +F , R) = max ectvs(G[V 1 ∪ R] +F ∪{xy} , R), ectvs(G +∅
2 , {x, y}) . (see Figure 3)

The next lemma shows that, in the case of a parallel composition, a fictive edge between the two terminal vertices is irrelevant. This is because the graph is already biconnected. Lemma 3. Let (G +F ∪{xy} , R) be a rooted extended graph such that R = {x, r 1 . . . , r k } (with k > 0), r 1 , . . . r k are isolated vertices (in G), Proof. Let σ * ∈ L c (G +F ∪{xy} , R) be a connected layout of minimum cost. Consider the neighbor v of y such that σ * (v) is minimum. By the connectivity of σ * , σ * (v) < σ * (y). Suppose without loss of generality that v ∈

F = {yr i | i ∈ [k]} and (G[V \ {r 1 , . . . , r k }], (x, y)) = G 1 ⊕ G 2 with G 1 = (G 1 , (x, y)) and G 2 = (G 2 , (x, y)). Then ectvs(G +F ∪{xy} , R) = ectvs(G +F , R). G 1 G 2 r 1 r i r k y x G 1 G 2 r 1 r i r k y x
V 1 . The case v ∈ V 2 is symmetric.
As in the proof of Lemma 2, we define the layout

σ 1 = σ[V 1 ∪ R] of (G[V 1 ∪ R] +F ∪{xy} , R) and the layout σ 2 = σ[V 2 ] of (G 2 , {x, y}), where σ = r 1 , . . . , r k ⊙ σ * [V 1 ] ⊙ σ * [V 2 \ {x, y}]
is a layout of (G +F ∪{xy} , R). We first observe that Claim 1 applies to σ 1 , σ 2 and σ which are thereby connected layouts. We also remark that the proof of Claim 2 applies to σ even in the presence of the fictive edge xy. So we have σ ∈ L c (G +F , R) and ecost((G +F , R), σ) = ecost((G +F , R), σ * ). Following the proof of Lemma 2, we show that for every

v 1 ∈ V 1 ∪ R, S (e) σ (v 1 ) = S (e) σ 1 (v 1 ) and that for every v 2 ∈ V 2 \ {x, y}, S (e) σ (v 2 ) = S (e) σ 2 (v 2 ). So we proved that ectvs(G +F ∪{xy} , R) = max ectvs(G[V 1 ∪ R] +F ∪{xy} , R), ectvs(G +∅
2 , {x, y}) . Lemma 2 allows us to conclude that ectvs(G +F ∪{x,y} , R) = ectvs(G +F , R) as claimed. In other words the fictive edge xy is irrelevant (see Figure 4).

Series composition

Lemma 4. Let (G +∅ , R) be a rooted extended graph with R = {x, y} and such that G = G 1 ⊗G 2 with G 1 = (G 1 , (x, z)) and G 2 = (G 2 , (z, y)) (see Figure 6). Then

ectvs(G +∅ , R) = min        max ectvs( G+{zy} 1 , R), ectvs(G +∅ 2 , R 2 ) max ectvs( G+{zx} 2 , R), ectvs(G +∅ 1 , R 1 )       
, where G1 (resp. G2 ) is obtained from G 1 (resp. G 2 ) by adding y (resp. x) as an isolated vertex, and where

R 1 = {z, x}, R 2 = {z, y}. Proof. Let σ * ∈ L c (G, R) be a connected layout of minimum cost. Consider the neighbor v of z so that σ * (v) is minimized. By the connectivity of σ * , σ * (v) < σ * (z). Suppose without loss of generality that v ∈ V 1 . The case v ∈ V 2 is symmetric. From σ * , we define σ 1 = σ[V 1 ∪ R] a layout of (ectvs( G+{zy} 1 , R), σ 2 = z, y ⊙ σ[V 2 \ {y, z}] a layout of (G +∅ 2 , R 2 ) and σ = x, y ⊙ σ * [V 1 \ {x}] ⊙ σ * [V 2 \ {y,
z}] a layout of (G +∅ , R) (see Figure 5).

σ * x y z v v 2 σ x y z v v 2 Figure 5: Rearranging a layout σ * of G = G 1 ⊗ G 2 of minimum cost into σ = x, y ⊙ σ * [V 1 \ {x}] ⊙ σ * [V 2 \ {y, z}]. Red diamond vertices belong to V 1 \ {x},
σ * (v 2 ). But as σ(z) < σ(v 2 ), v / ∈ S (e) σ (v 2 ). Instead we have that z ∈ S (e) σ (v 2 ). Claim 3. σ 1 ∈ L c (ectvs( G+{zy} 1 , R), σ 2 ∈ L c (G +∅ 2 , R 2 ) and σ ∈ L c (G +∅ , R). Proof of claim. Let v 1 be a vertex of V 1 distinct from x and z. Every neighbor of v 1 belongs to V 1 . As the relative ordering between vertices of V 1 is left unchanged, vertex v 1 has a neighbor prior to it in σ. It follows that σ 1 ∈ L c (ectvs( G+{zy} 1 , R).
Suppose that v 2 is a vertex of V 2 distinct from y and z. Then as in the previous case, every neighbor of v 2 belongs to V 2 . As the relative ordering in σ 2 and σ between vertices of V 2 has only been modified by moving z ahead, v 2 has a neighbor prior to it in σ. It follows that σ 2 ∈ L c (G +∅ 2 , R 2 ). To prove that σ is connected, we are left with vertex z. By assumption, z has a neighbor v ∈ V 1 such that σ * (v) < σ * (z), implying that σ(v) < σ(z). As every vertex has a neighbor prior to it in σ, the layout σ is connected.

✸ G 1 G 2 z x y G 1 z x y G 2 y z
Figure 6: Decomposition of an extended graph resulting from a series composition.

Claim 4. ecost((G +∅ , R), σ) = ecost((G +∅ , R), σ * ).
Proof of claim. We first consider a vertex

v 1 ∈ V 1 . By construction, we have σ * [V 1 ] = σ[V 1 ]
and for every vertex

v 2 ∈ V 2 \ {x, y}, σ(v 1 ) σ(v 2 ). It follows that S (e) σ (v 1 ) ⊆ V 1 ∪ R. Suppose that σ(v 1 ) > σ(z). As z separates v 1 from the vertices of V 2 , we have that S (e) σ (v 1 ) = S (e) σ * (v 1 ). Suppose now that σ(v 1 ) ≤ σ(z) and let v ∈ V 1 a vertex that belongs to S (e) σ (v 1 ). Then, as z is a cut vertex of G +∅ , there exists a (v, v 1 )-path P in G 1 such that every vertex v ′ ∈ P distinct from v satisfies σ(v 1 ) ≤ σ(v ′ ). As σ * [V 1 ] = σ[V 1 ], the path P certifies that v ∈ S (e) σ * (v 1 ), implying that |S (e) σ (v 1 )| ≤ |S (e) σ * (v 1 )|. Let us now consider a vertex v 2 ∈ V 2 \ {y, z}. Observe that, as z is a cut vertex, σ * (z) < σ * (v 2 ) implies that S (e) σ * (v 2 ) ⊆ V 2 . As σ[V 2 \ {z}] = σ * [V 2 \ {z}], every vertex u ∈ V 2 \ {z} that belongs to S (e)
σ (v 2 ) also belongs to S (e) σ * (v 2 ). Suppose that z ∈ S (e) σ (v 2 ). Then there exists a (z, v 2 )-path P such that every internal vertex u of P satisfies σ(v 2 ) < σ(u). As σ[V 2 \ {z}] = σ * [V 2 \ {z}], we also have σ * (v 2 ) < σ * (v). Let us distinguish two cases:

• If σ * (z) < σ * (v 2 ), then z ∈ S (e) σ (v 2 ) implying that S (e) σ (v 2 ) ⊆ S (e) σ * (v 2 ). • Otherwise, σ * (z) > σ * (v 2 ) and then z / ∈ S (e)
σ * (v 2 ). But in that case, let us recall that by assumption the first neighbor v of z in σ * belongs to

V 1 . It follows that v ∈ S (e) σ * (v 2 ). As we argue that S (e) σ (v 2 ) ⊆ V 2 , v ∈ S (e) σ * (v 2 ) \ S (e) σ (v 2 ). So v is a replacement vertex for z in S (e) σ * (v 2 ), implying that |S (e) σ (v 2 )| ≤ |S (e) σ * (v 2 )|. So we proved that ecost((G +∅ , R), σ) ≤ ecost((G +∅ , R), σ * ). As by Claim 3, σ ∈ L c (G +F , R), the optimality of σ * implies that ecost((G +∅ , R), σ) = ecost((G +∅ , R), σ * ). ✸
Let us now conclude the proof. Claim 3, Claim 4 and the optimality of σ * imply that σ is a connected layout of G +F of minimum cost. By Claim 3, we have

σ 1 = σ[V 1 ∪R] ∈ L c ( G+{xy} 1 , R).
Observe that in the extended graph G+{xy} , the fictive edge xy simulates every (z, y)-path of G whose internal vertices belong to V 2 . It follows that for every vertex

v 1 ∈ V 1 ∪ R, S (e)
σ (v 1 ) = S (e) σ 1 (v 1 ). Likewise, by Claim 3, we know that

σ 2 = σ[V 2 ] ∈ L c (G +∅ 2 , {z, y}).
As z separates the vertices of V 2 from the other vertices, for every

v 2 ∈ V 2 \ {z}, we have S (e) σ (v 2 ) = S (e) σ 2 (v 2 ). It follows that ectvs(G +∅ , R) = max ectvs( G+{zy} 1 , R), ectvs(G +∅ 2 , R 2 ) .
Let us now consider a rooted extended graph (G +F , R) with R = {x, r 1 . . . , r k } and (G[V \ {r 1 , . . . , r k }], (x, y)) = G 1 ⊗ G 2 (see Figure 8). The fact that y is not a root vertex forces that in a connected layout starting from the root x forces the vertex z to be the first vertex of V 2 . Using this observation, one can apply the same arguments than in the proof of Lemma 4.

Lemma 5. Let (G +F , R) be a rooted extended graph such that R = {x, r 1 . . . , r k } (with k > 0), r 1 , . . . r k are isolated vertices (in G), F = {yr i | i ∈ [k]} and (G[V \ {r 1 , . . . , r k }], (x, y)) = G 1 ⊗ G 2 with G 1 = (G 1 , (x, z)) and G 2 = (G 2 , (z, y)). Then ectvs(G +F , R) = max ectvs(G[V 1 ∪ R] +F ′ , R), ectvs(G[V 2 ∪ R ′ ] +F , R ′ ) , where F ′ = {zr i | i ∈ [k]} and R ′ = {z, r 1 , . . . , r k }.
Proof. Let σ * ∈ L c (G +F , R) be a connected layout of minimum cost. From σ * , we define: 7) a layout of (G +F , R). We observe that in this case, as y is not a root,

σ 1 = σ[V 1 ∪R] a layout of (G[V 1 ∪R] +F ′ , R), σ 2 = z, y ⊙σ[V 2 \{y, z}] a layout of (G[V 2 ∪R ′ ] +F , R ′ ) and σ = r 1 , . . . , r k ⊙ σ * [V 1 ] ⊙ σ * [V 2 \ {z}] (see Figure
σ * (z) ≤ σ * (v 2 ) for every vertex v 2 ∈ V 2 . σ * r 1 r 2 r 3 x z y σ r 1 r 2 r 3 x y z Figure 7: Rearranging a layout σ * of minimum cost into σ = r 1 , r 2 , r 3 , x ⊙σ * [V 1 \{x}]⊙σ * [V 2 \ {z}].
Red diamond vertices belong to V 1 \ {x}, blue diamond vertices belong to V 2 \ {z}, red square vertices are the roots.

Claim 5. σ 1 ∈ L c (G[V 1 ∪ R] +F ′ , R), σ 2 ∈ L c (G[V 2 ∪ R ′ ] +F , R ′ ) and σ ∈ L c (G +F , R). Proof of claim. Let v 1 be a vertex of V 1 distinct from x. Every neighbor of v 1 belongs to V 1 . As the relative ordering between vertices of V 1 is left unchanged, vertex v 1 has a neighbor prior to it in σ. It follows that σ 1 ∈ L c (G[V 1 ∪ R] +F ′ , R). Suppose that v 2 is a vertex of V 2 distinct from z.
Then as in the previous case, every neighbor of v 2 belongs to V 2 . As the relative ordering between vertices of V 2 is left unchanged in σ 2 and σ, vertex v 2 has a neighbor prior to it in σ.

It follows that σ 2 ∈ L c (G[V 2 ∪ R ′ ] +F , R ′ ) and σ ∈ L c (G +F , R). ✸ Claim 6. ecost((G +F , R), σ) = ecost((G +F , R), σ * ).
Proof of claim. We first consider a vertex

v 1 ∈ V 1 . Observe that σ * (z) ≤ σ * (v 2 ) for every vertex v 2 ∈ V 2 . It follows that S (e) σ * (v 1 ) ∩ (V 2 \ {z}) = ∅. The fact that σ * [V 1 ∪ R] = σ[V 1 ∪ R] implies S (e) σ (v 1 ) = S (e) σ * (v 1 ). Similar arguments hold for every vertex v 2 ∈ V 2 \{z}. As z separates vertices of V 2 from vertices of V 1 and as σ * (x) < σ * (z) < σ * (v 2 ), we have S (e) σ * (v 2 ) ∩ (V 1 \ {x, z}) = ∅. The fact that σ * [V 2 ∪ R] = σ[V 2 ∪ R] implies S (e) σ (v 2 ) = S (e) σ * (v 2 ). Thereby ecost((G +F , R), σ) = ecost((G +F , R), σ * ). ✸
Let us now conclude the proof of the lemma. Claim 5, Claim 6 and the optimality of σ * imply that σ is a connected layout of G +F of minimum cost. From Claim 5, we have that

G 1 G 2 r 1 r i r k z x y G 1 r 1 r i r k z x G 2 r 1 r i r k y z
Figure 8: Decomposition of an extended graph resulting from a series composition. A connected layout starting at x places z as the first vertex of V 2 .

σ 1 = σ[V 1 ∪ R] ∈ L c (G[V 1 ∪ R] +F ′ , R). Observe that in the extended graph G[V 1 ∪ R] +F ′ , for i ∈ [k],
the fictive edge zr i ∈ F ′ simulates every simple extended (z, r i )-path in G +F . It follows that for every vertex

v 1 ∈ V 1 ∪ R, S (e)
σ (v 1 ) = S (e) σ 1 (v 1 ). Likewise, from Claim 5, we know that

σ 2 = σ[V 2 ∪ R ′ ] ∈ L c (G[V 2 ∪ R ′ ] +F , R ′ ). As noticed before, z separates the vertices of V 2 from vertices of V 1 . It follows for every v 2 ∈ V 2 \ {z}, we have S (e) σ (v 2 ) = S (e) σ 2 (v 2 ), completing the proof.
If there is a fictive edge between the two terminal vertices x and y of G, then , as in Lemma 5, a connected layout starting at x may visit y before z. In this case, we obtain the following lemma. Lemma 6. Let (G +F ∪{xy} , R) be a rooted extended graph such that R = {x, r 1 . . . , r k } (with k > 0), r 1 , . . . r k are isolated vertices (in G),

F = {yr i | i ∈ [k]} and (G[V \ {r 1 , . . . , r k }], (x, y)) = G 1 ⊗ G 2 with G 1 = (G 1 , (x, z)) and G 2 = (G 2 , (z, y)). Then ectvs(G +F ∪{xy} , R) = max ectvs(G[V 1 ∪ R] +F ′ ∪{xz} , R), ectvs(G[V 2 ∪ R ′ ] +F ∪{xy} , R ′ ) ,
where R ′ = {z, r 1 , . . . , r k , x} and

F ′ = {zr i | i ∈ [k]}.
Proof. We proceed as in the proof of Lemma 5. We transform a layout 7). Observe that since the solid graph G is the same as in Lemma 5, Claim 5 applies and thereby σ ∈ L c (G +F ∪{xy} , R).

σ * ∈ L c (G +F ∪{xy} ), R) of minimum cost into the layout σ = r 1 , . . . , r k ⊙ σ * [V 1 ] ⊙ σ * [V 2 \ {z}] (see Figure
Claim 7. ecost((G +F ∪{xy} , R), σ) = ecost((G +F ∪{xy} , R), σ * ).
Proof of claim. The existence of the fictive edge xy does not change the arguments used in the proof of Claim 6. Let us consider

v 1 ∈ V 1 and v 2 ∈ V 2 \ {z}. First as σ * (x) < σ * (z) < σ * (v 2 ) and z separates vertices of V 2 from vertices of V 1 , we obtain that S (e) σ * (v 1 ) ∩ (V 2 \ {z}) = ∅ and S (e) σ * (v 2 ) ∩ (V 1 \ {x, z}) = ∅. Moreover σ * [V 1 ∪ R] = σ[V 1 ∪ R] implies S (e) σ (v 1 ) = S (e) σ * (v 1 ) and σ * [V 2 ∪ R] = σ[V 2 ∪ R] implies S (e) σ (v 2 ) = S (e)
σ * (v 2 ), proving the claim. In other words, σ is a connected layout of G +F ∪{xy} of minimum cost.

✸ Let us now conclude the proof of the lemma. Claim 7, the fact that σ ∈ L c (G +F ∪{xy} , R) and the optimality of σ * imply that σ is a connected layout of G +F of minimum cost. From Claim 5, we have that

G 1 G 2 r 1 r i r k z x y G 1 r 1 r i r k z x G 2 r 1 r i r k x y z
σ 1 = σ[V 1 ∪ R] ∈ L c (G[V 1 ∪ R] +F ′ ∪{xy} , R). Observe that in the extended graph G[V 1 ∪ R] +F ′ , for i ∈ [k], the fictive edge zr i ∈ F ′ (for i ∈ [k]
) simulates every simple extended (z, r i )-path in G +F ∪{xy} . Similarly the fictive edge zx aims at representing extended (z, x)-paths avoiding V 1 \{x} in G +F ∪{xy} . It follows that for every vertex

v 1 ∈ V 1 ∪R, S (e) σ (v 1 ) = S (e) σ 1 (v 1 ). Likewise, from Claim 5, we know that σ 2 = σ[V 2 ∪ R ′ ] ∈ L c (G[V 2 ∪ R ′ ] +F ∪{zx} , R ′ ).
As noticed before, z separates the vertices of V 2 from vertices of V 1 , and thereby for every

v 2 ∈ V 2 , V 1 \ {z} ∩ S (e) σ (v 2 ) = ∅. Observe that despite the fact that x / ∈ V 2 , it is preserved as a (pendant) root in R ′ . It follows for every v 2 ∈ V 2 \ {z}, we have S (e) σ (v 2 ) = S (e)
σ 2 (v 2 ), completing the proof.

The dynamic programming algorithm

The following upper bound on connected treewidth enables us to optimize the size of the DP tables.

Theorem 5 ([21, 22, 23]). Every graph G on n vertices satisfies ctw(G) ≤ tw(G) • (log n+1).

As series-parallel graphs have treewidth at most two, Theorem 5 implies that the connected treewidth of a series-parallel graph on n vertices is at most c sp = ⌈2(log n + 1)⌉. This bound allows us to optimize the size of the table in our dynamic programming algorithm. Moreover this bound is tight [START_REF] Fraigniaud | Monotony properties of connected visible graph searching[END_REF][START_REF] Fraigniaud | Monotony properties of connected visible graph searching[END_REF], even on series-parallel graphs as certified by a construction of contraction obstructions for connected treewidth at most k, for every k ≥ 2 [START_REF] Adler | Connected search for a lazy robber[END_REF]. Let us first focus on the case of biconnected series-parallel graph.

Proposition 1. Let G be a biconnected series-parallel graph on n vertices. Then computing ctw(G) can be done in O(n 2 • log n)-time.

Proof. Let G = (G, (x, y)), with G = (V, E), be a biconnected 2-terminal graph such that xy ∈ E. By Theorem 1, we have G = G 1 ⊕G 2 where G 1 = (G 1 , (x, y)) with G 1 = ({x, y}, {xy}) and G 2 = (G 2 , (x, y)) with G 2 = (V, E \ {xy}). By Theorem 2, in linear time, we can compute T (G), the SP-tree of G. Recall that the root of T (G) corresponds to the parallel composition G 1 ⊕ G 2 . We let G t = (G t , (x t , y t )) with G t = (V t , E t ) denote the subgraph represented by node

• By Lemma 4, we have for k ∈ [c sp -1]:

DP t [0] = min      max {DP t 1 [x t ], DP t 2 [0]} max {DP t 2 [y t ], DP t 1 [0]}      .
• By Lemma 5, we have for k ∈ [c sp -1]:

DP t [k, x t ] = max {DP t 1 [k, x t ], DP t 2 [k, z]} and DP t [k, y t ] = max {DP t 1 [k, y t ], DP t 2 [k, z]} .
• By Lemma 6, we have for k ∈ [c sp -2]:

DP t [k, x t , x t y t ] = max {DP t 1 [k, x t , x t z], DP t 2 [k + 1, z]} and DP t [k, y t , x t y t ] = max {DP t 1 [k, y t , y t z], DP t 2 [k + 1, z]} .
For every non-leaf node t of T (G), the entries of DP t [ • ] are initialized to some dummy value ⊥. Every leaf node t of T (G) represents the single edge graph, that is G t = (V t , E t ) with V = {x t , y t } and E = {x t y t }. Then we can initialize the values associated to a leaf node t as follows:

• DP t [0] = ectvs(G +∅ t , {x t , y t }) = 1 • for k ∈ [c sp -1], DP t [k, x t ] = ectvs( G+F t,k , {x t , r 1 , . . . , r k }) = k + 1 where F = {y t r i | i ∈ [k]}. • for k ∈ [c sp -1], DP t [k, y t ] = ectvs( G+F t,k , {y t , r 1 , . . . , r k }) = k + 1 where F = {x t r i | i ∈ [k]}. • for k ∈ [c sp -2], DP t [k, x t , x t y t ] = ectvs( G+F t,k , {x t , r 1 , . . . , r k }) = k + 1 where F = {y t r i | i ∈ [k]} ∪ {x t y t }. • for k ∈ [c sp -2], DP t [k, y t , x t y t ] = ectvs( G+F t,k , {y t , r 1 , . . . , r k }) = k + 1 where F = {x t r i | i ∈ [k]} ∪ {x t y t }. As the SP-tree T (G) contains O(n) nodes, filling the table DP t [ • ], for every node t, is achieved in O(n•log n)-time. Theorem 3 states that ctw(G) = ctvs(G) = min{ectvs(G +∅ , {x, y}) | xy ∈ E}.
This implies that the whole algorithm runs in O(n 2 • log n)-time.

Generalization to graph of treewidth at most two

Recall that a graph G has treewidth at most two if and only if every biconnected component of G induces a series-parallel graph. So we need a lemma to deal with cut vertices. Lemma 7. Let G = (V, E) be a graph containing a cut vertex x and let G

1 = [C 1 ∪ {x}], . . . , G k = G[C k ∪ {x}] be the induced subgraphs where C 1 , . . . , C k denote the connected components of G -x. Then ctvs(G) = min i∈[k] max ctvs(G i ), max {ctvs(G j , {x}) | j ∈ [k], j = i}
(see Figure 10).

G 3 G 2 G 1 x G 1 x G 2 x G 3 x
= G[C 1 ∪ {x}], then σ * [C 2 ] and σ * [C 3 ] start at x, which becomes a root of G 2 = G[C 2 ∪ {x}] and of G 3 = G[C 3 ∪ {x}].
Proof. Let us consider σ ∈ L (c) (G) and suppose that the first vertex of σ belongs to C 1 . Then observe that σ can be rearranged into τ

= σ[C 1 ] ⊙ σ[C 2 \ {x}] . . . , ⊙σ[C k \ {x}] and that since x is a cut vertex then τ ∈ L (c) (G) as well. The statement follows from the observation that cost(G, τ ) = max {cost(G i , σ[C i ]) | i ∈ [k]}.

Discussion and open problems

We obtained a polynomial time algorithm to compute the connected treewidth for the class of graphs of treewidth at most two. This result naturally leads to the problem of determining the algorithmic complexity of computing the connected treewidth for the class of bounded treewidth graphs. To discuss this, we present the problem as a decision problem:

Connected Treewidth

Input: A graph G and an integer k. Question: ctw(G) ≤ k?

Our result implies that Connected Treewidth can be solved in O(n 3 • k)-time for graphs of treewidth at most 2. Let us discuss the following three conjectures. Our result can be seen as a special case of Conjecture 1 (when tw(G) ≤ 2). A general resolution of Conjecture 1 would require a vast extension of our dynamic programming approach. In our approach (for treewidth at most two) we essentially solve a slightly modified problem where the input is a pair (G, e), where e ∈ E(G), and we return the minimum cost of a layout that begins with the endpoints of e. Then we reduce the computation of connected treewidth to this problem by paying an overhead of O(n 2 ). An interesting question is whether and how a similar approach might work for the general case. Of course, one may try to reduce the O(n 3 • log n)-time complexity of our algorithm by avoiding such reductions and directly build a dynamic programming scheme for Connected Treewidth on graphs of treewidth ≤ k. We believe that this is possible and can reduce the time complexity to O(n c ) for some 1 < c ≤ 3.

For Conjecture 2 one may attempt to use tools related to Courcelle's theorem. This would require to express the question ctw(G) ≤ k in using a formula φ k in Monadic Second Order Logic (MSOL) which is far from being obvious. A possible direction would be to consider the contraction-obstruction set Z k of the class G k = {G | ctw(G) ≤ k}, i.e., the contraction minimal graphs not in G k . Indeed contraction testing is MSOL expressible. However, it turns out that, unlike the case for treewidth and pathwidth with respect to minors, Z k is infinite for every k ≥ 2, as observed in [START_REF] Adler | Connected search for a lazy robber[END_REF]. A possible way to overcome this obstacle is to consider some other partial ordering relation, alternative to contractions, that maintains closeness, MSOL expressibility and gives rise to bounded size obstructions. Such a step can be done using the results of [START_REF] Adler | Connected search for a lazy robber[END_REF] for graphs of connected treewidth at most two. However, it is not clear whether this can be extended for bigger values of connected treewidth. Let us mention that recently, Kanté et al. [START_REF] Kanté | A linear fixed parameter tractable algorithm for connected pathwidth[END_REF] obtained a O(f (k) • n)-time algorithm to compute the connected pathwidth of a graph (that is the analogue of Conjecture 2 for pathwidth). Finally, it is also natural to ask if one can compute in FPT-time the connected treewidth of a graph when parameterized by the pathwidth of the input graph.

A proof of Conjecture 3 would follow if we devise an algorithm to check whether ctw(G) ≤ k in O(n f (k,tw(G)) ) time. This follows directly from the fact that yes-instances of Connected Treewidth have always treewidth at most k. Such a result would be analogous to the one of [START_REF] Dereniowski | Finding small-width connected path decomposition in polynomial time[END_REF] for connected pathwidth and is perhaps the first (and easier) to be attacked among the three above conjectures.

Figure 1 :

 1 Figure 1: Rearranging a layout of minimum cost of an extended graph G = G 1 ⊕ G 2 without a fictive edge. Red vertices belongs to V 1 \ {x, y} and blue vertices belong to V 2 \ {x, y}.

Figure 2 :

 2 Figure 2: Parallel decomposition of an extended graph without fictive edges.If G = G 1 ⊕ G 2 , then we have ectvs(G +∅ , R) = max ectvs(G +∅ 1 , R), ectvs(G +∅ 2 , R) .

Figure 3 :

 3 Figure 3: Decomposition of an extended graph with several isolated roots and resulting from a parallel composition.

Figure 4 :

 4 Figure 4: The fictive edge xy is irrelevant: ectvs(G +F ∪{xy} , R) = ectvs(G +F , R).

1

 1

Figure 9 :

 9 Figure 9: Decomposition of an extended graph resulting from a series composition.

Figure 10 :

 10 Figure 10: Decomposition of a graph with a cut vertex. If an optimal connected layout σ * starts at an arbitrary vertex of G 1 = G[C 1 ∪ {x}], then σ * [C 2 ] and σ * [C 3 ] start at x, which becomes a root of G 2 = G[C 2 ∪ {x}] and of G 3 = G[C 3 ∪ {x}].

Theorem 6 .

 6 Computing the connected treewidth of a graph of treewidth at most 2 requires O(n 3 • log n)-time. Proof. Let G be a graph of treewidth at most 2. The algorithm first computes the biconnected tree decomposition of G. This can be done in linear time. Following Lemma 7, we guess a biconnected component C 1 in which the connected layout will start. This generates for every biconnected component C k distinct from C 1 a root vertex r k . Then using Proposition 1, in O(n 2 • log n) we can compute ctvs(G[C 1 ]) and ctvs(G[C k ], {r k }) for each k = 1. This leads to an O(n 3 • log n)-time algorithm.

Conjecture 1 .

 1 Connected Treewidth can be solved by an O(n f (tw(G)) )-time algorithm.

Conjecture 2 .

 2 Connected Treewidth can be solved by an O(f (k, tw(G))•n)-time algorithm. Conjecture 3. Connected Treewidth can be solved by an O(n f (k) )-time algorithm.

  1 , (x 1 , y 1 ))⊕(G 2 , (x 2 , y 2 )), yields the 2-terminal graph (G, (x 1 , y 1 )) with G being the graph obtained by identifying the terminal x 1 with x 2 and the terminal y 1 with y 2 .

	Definition 1. A 2-terminal graph (G, (x, y)) is series-parallel if either it is the single edge
	graph with {x, y} as vertex set, or if it results from the series or the parallel composition of two
	2-terminal series-parallel graphs. A graph G = (V, E) is a series-parallel graph if for some pair
	of vertices x, y ∈ V, (G, (x, y)) is a 2-terminal series-parallel graph.

  blue diamond vertices belong to V 2 \ {y, z} and red square vertices are the roots. Observe that the path v, z, v 2 certifies that v ∈ S

	(e)

* Research supported by ANR projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010) and the French-German Collaboration ANR/DFG Project UTMA ANR-20-CE92-0027.

t of T (G). We let Gt,k be the graph G t augmented with k isolated vertices r 1 , . . . , r k where k ≤ c sp and denote Gt,k = ( Gt,k , (x t , y t )). In order to apply the rules described in Lemmas 1 -6, the table DP t [ • ] stored at every node t contains the following values:

The bounds on the integer k, determining the number of entries in the table DP t [ • ] of a node t is, are delimited by the upper-bound c sp , as asserted by Theorem 5. The initialization of the table for leaf nodes (see below) guarantees that this bound is respected.

We observe that for every node t, every entry of DP t [ • ] corresponds to an extended rooted two-terminal graph (H +F , R) such that: R contains at least two vertices; at least one vertex of R is a terminal vertex; and every root vertex that is not a terminal vertex is an isolated vertex. These properties implies that every connected component of H +F contains a root vertex, and thereby it guarantees the existence of a connected layout of (H +F , R).

Suppose that t represents a parallel composition

The children t 1 and t 2 of t respectively represent the 2-terminal graphs G ′ 1 = (G ′ 1 , (x t , y t )) and G ′ 2 = (G ′ 2 , (x t , y t )). Then DP t [ • ] is computed as follows:

• By Lemma 2, we have for k ∈ [c sp -1]:

• By Lemma


The implicit measurement of personality (for a better predictive tool in the job performance measurement) ▪ Personality is a field that is widely investigated in recruitment and competitive examinations. However, self-report personality inventories pose a number of problems, particularly in these high-stakes situations.

▪ The biases associated with this type of test are well known: social desirability, acquiescence bias, poor self-knowledge, difficulty in understanding items, etc. An interesting avenue lies in implicit measures of personality.

▪ An implicit measure is an evaluation process in which the measurement processes are not (or very little) identifiable by the people being evaluated. This makes it difficult, if not impossible, for them to implement effective strategies to falsify their answers.

▪ There are several such models: projective methods, implicit association tasks (IATs) and situational judgment tests (SJTs). Depending on the type of responses proposed (ipsative or quasi-ipsative) and by combining several different investigative methods, it is possible to increase the reliability of the measures and their predictivity concerning professional performance.

▪ Objective: Establish a model for indirect measures of personality ▪ Hypotheses:

-Indirect measures offer better predictive validity concerning professional performance and are less subject to the biases previously mentioned.

-The multiplicity of measures (personality, personality disorders, behavioral skills) increases incremental validity and, consequently, the reliability of the measurement performed.

▪ Problems :

-A "totally" indirect measure seems illusory.

-Item comprehension is highly subjective.

-It is not the personality that is measured, but its construct.

▪ Personality has been conceptualized from a variety of theoretical perspectives. Today, a consensus seems to emerge as a general taxonomy of personality traits known as the Big Five :

▪ Cloninger describes a model of the genetic structure of personality based on twin and adoption studies of personality in humans. Based on neuropharmacological studies of humans and animals, a psychobiological model of learning abilities that underlie human personality traits is proposed.. "A review of the literature indicates that people with field-dependent or field-independent cognitive styles are different in their interpersonal behavior in ways predicted by the theory of psychological differentiation. Field-dependent people make greater use of external social referents, but only when the situation is ambiguous and these referents provide information that helps to remove the ambiguity; field-independent people function with greater autonomy under such conditions. Field-dependent people are more attentive to social cues than are field-independent people". Witkin, H. A., & Goodenough, D. R. (1977). Field dependence and interpersonal behavior. Psychological bulletin, 84(4), 661.

link between personality measurement and job performance

ways

And what about the link with the job performance ? -In a recent meta-analysis of 164 studies, Nye, et al. ( 2022) found correlations of up to .49 between the general intelligence factor and occupational performance.

Situational judgment tests (SJTs)

Situational judgment tests (SJTs) are assessments that measure test takers' judgments about different ways of responding to situations (Lievens & Motowidlo, 2016). SJTs have been shown to be excellent predictors of job performance (ρ = 0.34; McDaniel, Hartman, Whetzel, & Grubb, 2007).

An example : You are a team leader in a busy office environment. One of your team members, Sarah, has been consistently arriving late for work over the past week, which is affecting the team's productivity and morale. Sarah is typically a good worker, and you value her contributions. How would you handle this situation? Answer Options: A) Speak with Sarah privately, express your concerns, and ask if there's anything going on in her personal life that might be affecting her punctuality. Offer support and suggest a flexible schedule if necessary. B) Ignore the issue for now, as it might just be a temporary problem. Wait to see if Sarah's punctuality improves on its own. C) Publicly reprimand Sarah in front of the team to send a message to everyone about the importance of punctuality. D) Document Sarah's lateness and report it to upper management immediately, suggesting that she should be disciplined or terminated.

In this SJT question, the candidate is asked to choose the most appropriate response to the situation presented. Option A demonstrates a proactive and supportive approach to address the issue, while options B, C, and D represent less effective or inappropriate responses to the situation.

The incremental validity

▪ Mihura (2012), in a meta-analysis, suggests the importance of coupling selfreported assessment methods with other types of investigation, thereby increasing construct and incremental validity (about projectives methods and personality measurement).

▪ Greenwald (2009) concludes that incremental validity is increased in a reciprocal manner between IATs (implicit association task) and self-report questionnaires: the two coupled measures favor better predictivity.

▪ McDaniel et al (2007), found that IATs explained 6-7% more variance when used in conjunction with a traditional personality inventory (based on the Big Five model).

▪ These diverse findings argue in favor of a multiplicity of measures to increase the reliability of a common measure.

Many thanks for your attention!