Benjamin Bergougnoux

Mamadou Kanté

FAST EXACT ALGORITHMS FOR SOME CONNECTIVITY PROBLEMS PARAMETERIZED BY CLIQUE-WIDTH

Keywords: 1991 Mathematics Subject Classification. F.2.2, G.2.1, G.2.2 clique-width, module-width, single exponential algorithm, feedback vertex set, connected σ, ρ-domination

Given a clique-width k-expression of a graph G, we provide 2 O(k) • n time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree, Connected Dominating Set, or Connected Vertex Cover. We also propose a 2 O(k) • n time algorithm for Feedback Vertex Set. The best running times for all the considered cases were either 2 O(k•log(k)) • n O(1) or worse.

Introduction

Tree-width [START_REF] Robertson | Graph minors. II. algorithmic aspects of tree-width[END_REF] is probably the most well-studied graph parameter in the graph algorithm community, and particularly by people working in Fixed Parameter Tractable (FPT for short) algorithms, due partly to its numerous structural and algorithmic properties [START_REF] Courcelle | Graph structure and monadic second-order logic[END_REF][START_REF] Downey | Fundamentals of parameterized complexity[END_REF]. For a while, people used to think that for many connectivity constraints problems, e.g., Hamiltonian Cycle, Steiner Tree, the naive k O(k) • n O (1) time algorithm, k the tree-width of the input graph, cannot be improved. Indeed, it seems necessary to know the connected components of the partial solutions in order to be able to extend them and also certify that the given solution is really connected. But, quite surprisingly, Cygan et al showed in [START_REF] Cygan | Solving connectivity problems parameterized by treewidth in single exponential time[END_REF] that some of these connectivity constraints problems admit randomized 2 O(k) •n O (1) time algorithms. The first deterministic 2 O(k) • n O (1) time algorithms for these problems was due to Bodlaender et al. in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF]. First, let us say that S represents the set of partial solutions S if whenever there is S ∈ S such that S can be completed into an optimum solution, there is S ∈ S that can be also completed into an optimum solution. Most of the dynamic programming algorithms are based on this notion of representativity, and proposing a fast algorithm is usually reduced to defining the adequate set S . For instance, one can define, for each node u of a tree-decomposition, a matrix M u over the binary field where M u [F, F ] = 1 if and only if the partial solutions F and F can be "joined" into a valid solution of the instance (F is usually intended to be a subset of a solution, subset included in the already processed part of the graph, and F the remaining part of the solution, that is not yet known).

The main contribution of [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] was to show that, for some connectivity constraints problems, for each node u of a tree-decomposition of width k, the rank of M u is at most 2 O(k) ; moreover, a maximum weighted basis -such that the solutions indexing its rows represent the solutions indexing the rows of M u -can be computed in time 2 O(k) .

Nevertheless, despite the broad interest on tree-width, only sparse graphs can have bounded tree-width. But, on many dense graph classes, some NP-hard problems admit polynomial time algorithms, and many of these algorithms can be explained by the boundedness of their clique-width, a graph parameter introduced by Courcelle and Olariu [START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF] and that emerges from the theory of graph grammars.

Clique-width is defined in terms of the following graph operations: (1) addition of a single vertex labeled i ∈ N, (3) renaming label i into j (ren i→j ), (3) addition of edges between vertices labeled i and those labeled j (add i,j ), (4) disjoint union (⊕). The clique-width of a graph is the minimum number of labels needed to construct it, and the expression constructing it is called k-expression, k the number of used labels. Clique-width generalizes tree-width in the sense that if a graph class has bounded tree-width, then it has bounded clique-width [START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF], but the converse is false as cliques have clique-width at most 2 and unbounded tree-width. Furthermore, clique-width appears also to be of big importance in FPT algorithms [START_REF] Courcelle | Graph structure and monadic second-order logic[END_REF]. While it is still open whether there exists an FPT algorithm to compute an optimal kexpression of a given graph, one can ask when clique-width behaves similarly as treewidth. It is known that clique-width is far from behaving similarly as tree-width on some well-studied and well-known difficult problems such as Hamiltonicity [START_REF] Fedor | Almost optimal lower bounds for problems parameterized by clique-width[END_REF]. On the other hand, Bui-Xuan et al. [START_REF] Bui-Xuan | Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems[END_REF], and Ganian et al. [START_REF] Ganian | On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width[END_REF][START_REF] Ganian | Clique-width: when hard does not mean impossible[END_REF] managed to prove, after more substantial work than for tree-width, that for locally checkable properties and some sparse problems, one can get 2 k O (1) • n O (1) time algorithms, k the clique-width of the input graph. For some of these algorithms, the exponential in their running times are proved to have a linear dependence on the clique-width, while for others only a polynomial dependence is known.

However, nothing is known on connectivity constraints problems, except some special cases such as Feedback Vertex Set which was proved to admit a k O(k) • n O (1) time algorithm in [START_REF] Bui-Xuan | Feedback vertex set on graphs of low clique-width[END_REF], provided the graph is given with a k-expression.

Our Contributions. We investigate connectivity constraints on locally checkable properties, such as Connected Dominating Set, or Connected Vertex Cover. All these problems are the connected variant of a problem in the family of problems called (σ, ρ)-Dominating Set problems. The family of (σ, ρ)-Dominating Set problems was introduced in [START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF] and studied in graphs of bounded clique-width in [START_REF] Bui-Xuan | Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems[END_REF][START_REF] Oum | Faster algorithms for vertex partitioning problems parameterized by clique-width[END_REF]. We recall its definition at the end of Section 2. It is not hard to modify the dynamic programming algorithm from [START_REF] Bui-Xuan | Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems[END_REF] that computes a minimum (σ, ρ)-dominating set in order to compute a minimum connected (σ, ρ)-dominating set in time k O(k) • n O (1) , since it suffices to keep track, for each family of partial solutions, the possible partitions of the label classes induced by them. We modify slightly this naive algorithm and prove that one can define representative sets of size 2 O(k) , yielding 2 O(k) • n time algorithms resolving this family of problems.

We also consider the Feedback Vertex Set problem, which asks to compute a minimum set of vertices to delete so that the resulting graph is acyclic, and propose similarly a 2 O(k) • n time algorithm. But, the algorithm, even in the same spirit as the one for connected (σ, ρ)-dominating set, is less trivial since one has to check also the acyclicity, a task that is not trivial when dealing with clique-width operations as a bunch of edges can be added at the same time. Indeed, at each step of the dynamic programming algorithm, when dealing with tree-width the number of vertices that have a neighbor in the rest of the graph is bounded, but for clique-width they can be only classified into a bounded number of equivalence classes (with respect to having the same neighborhood in the rest of the graph); these equivalence classes are the label classes of the given k-expression.

In both cases, we use the same rank-based approach as in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF], but we need to adapt in the Feedback Vertex Set's case the operations on partitions to fit with clique-width operations. The main difficulty is to deal with the acyclicity, which the authors of [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] also encountered but solved by counting the number of edges. In our case, counting the number of edges would yield an n O(k) time algorithm. Let's explain the ideas of the algorithms with two examples: (1) Connected Dominating Set, asking to compute a minimum connected set D such that each vertex in V (G) \ D has a neighbor in D and (2) Maximum Induced Tree, that consists in computing a maximum induced tree.

Let G be a graph, for which a k-expression is given, and let (X, Y ) be a bipartition of its vertex set induced by a subexpression of the k-expression. Let us denote the labels of vertices in X by {1, 2, . . . , k}. It is worth noticing that at the time we are processing the set X, may be not all the edges between the vertices of X are known (those edges may be added in the forthcoming add i,j operations). To facilitate the steps of the dynamic programming algorithm, we first assume that either all the edges between the vertices of X labeled i and the vertices of X labeled j are already known, or none of them, for all distinct i, j. A k-expressions fulfilling this constraint can be computed from any k-expression in linear time [START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF].

(1) Let D be a connected dominating set of G and let D X := D ∩ X. First, D is not necessarily connected, neither a dominating set of G[X]. So, the usual dynamic programming algorithm keeps, for each such D X , the pair (R, R ) of sequences over {0, 1} k , where R i := 1 if and only if D X contains a vertex labeled i, and R i := 1 if and only if X has a vertex labeled i not dominated by D X . One first observes that if D X and D X have the same pair of sequences (R, R ), then D X ∪ D Y is a dominating set of G if and only if D X ∪ D Y is a dominating set. Therefore, it is sufficient to keep for each pair (R, R ) of sequences in {0, 1} k the possible partitions of {1, . . . , k} corresponding, informally, to the connected components of the graphs induced by the D X 's, and for each possible partition, the maximum weight among all corresponding D X 's. Notice that the graphs induced by the D X 's are not necessarily induced subgraphs of G. One easily checks that these tables can be updated without difficulty following the cliquewidth operations in time k O(k) • n O (1) . In order to obtain 2 O(k) • n time algorithms, we modify this algorithm so that the partitions instead of corresponding to the connected components of the graphs induced by the D X 's, do correspond to the connected components of the induced subgraphs G[D X ]. For doing so, we do not guess the existence of vertices labeled i that are not dominated, but rather the existence of a vertex that will dominate the vertices labeled i (if not already dominated). With this modification, the steps of our dynamic programming algorithms can be described in terms of the operations on partitions defined in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF]. We can therefore use the same notion of representativity in order to reduce the time complexity.

(2) We consider this example because we reduce the computation of a minimum feedback vertex set to that of a maximum tree. We first observe that we cannot use the same trick as in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] to ensure the acyclicity, that is counting the number of edges induced by the partial solutions. Indeed, whenever an add i,j operation is used, many edges can be added at the same time.

Hence, counting the edges induced by a partial solution would imply to know, for each partial solution, the number of vertices labeled i, for each i. But, this automatically leads to an n O(k) time algorithm. We overcome this difficulty by first defining a binary relation acyclic on partitions where acyclic(p, q) holds whenever there are forests E and F , on the same vertex set, such that E ∪ F is a forest, and p and q correspond, respectively, to the connected components of E and F . In a second step, we redefine some of the operations on partitions defined in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] in order to deal with the acyclicity. These operations are used to describe the steps of the algorithm. They informally help updating the partitions after each clique-width operation by detecting partial solutions that may contain cycles. We also define a new notion of representativity, ac-representativity, where S ac-represents S if, whenever there is S ∈ S that can be completed into an acyclic connected set, there is S ∈ S that can be completed into a connected acyclic set.

We then prove that one can also compute an ac-representative set of size 2 O(k) , assuming the partitions are on {1, . . . , k}.

It remains now to describe the steps of the dynamic programming algorithm in terms of the new operations on partitions. First, we are tempted to keep for each forest F of X, the partition induced by the transitive closure of ∼ where i ∼ j whenever there is a vertex x labeled i, connected in F , to a vertex y labeled j. However, this is not sufficient because we may have in a same connected component two vertices labeled i, and any forthcoming add i,j operation will create a cycle in F if there is a vertex labeled j in F . To overcome this difficulty we index our dynamic programming tables with functions s that inform, for each i, whether there is a vertex labeled i in the partial solutions, and if yes, in exactly 1 vertex, or in at least 2 vertices. Indeed, knowing the existence of at least two vertices is sufficient to detect some cycles when we encounter an add i,j operation. We need also to make a difference when we have all the vertices labeled i in different connected components, or when at least two are in a same connected component. This will allow to detect all the partial solutions F that may contain triangles or cycles on 4 vertices with a forthcoming add i,j operation. Such cycles cannot be detected by the acyclic binary relation on partitions since this latter does not keep track of the number of vertices in each label. However, the other kinds of cycles are detected through the acyclic binary relation. We refer the reader to Section 4 for a more detailed description of the algorithm.

One might notice that our algorithms are optimal under the well-know Exponential Time Hypothesis (ETH) [START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF]. Indeed, from known Karp-reductions, there are no 2 o(n) time algorithms for the considered problems. Since the clique-width of a graph is always smaller than its number of vertices, it follows that, unless ETH fails, there are no 2 o(k) • n O (1) time algorithms, for these problems.

The remainder of the paper is organised as follows. The next section is devoted to the main notations, and for the definition of clique-width and of the considered problems. The notion of ac-representativity and the modified operations on partitions are given in Section 3. We also propose the algorithm for computing an ac-representative set of size 2 O(|V |) , for sets of weighted partitions on a finite set V . The algorithms for computing a minimum feedback vertex set and connected (σ, ρ)-dominating sets are given in, respectively, Sections 4 and 5.

Preliminaries

The size of a set V is denoted by |V | and its power set is denoted by 2 V . We write A \ B for the set difference of A from B, and we write A B for the disjoint union of A and B. We often write x to denote the singleton set {x}. For a mapping

f : A → B, we let f -1 (b) := {a ∈ A : b = f (a)} for b ∈ B.
We let min(∅) := +∞ and max(∅) := -∞. We let [k] := {1, . . . , k}. We denote by N the set of nonnegative integers and by F 2 the binary field.

Partitions. A partition p of a set V is a collection of non-empty subsets of V that are pairwise non-intersecting and such that pi∈p p i = V ; each set in p is called a block of p. The set of partitions of a finite set V is denoted by Π(V ), and (Π(V ), ) forms a lattice where p q if for each block p i of p there is a block q j of q with p i ⊆ q j . The join operation of this lattice is denoted by . For example, we have

{{1, 2}, {3, 4}, {5}} {{1}, {2, 3}, {4}, {5}} = {{1, 2, 3, 4}, {5}}.
Let block(p) denote the number of blocks of a partition p. Observe that ∅ is the only partition of the empty set. A weighted partition is an element of Π(V ) × N for some finite set V .

For p ∈ Π(V ) and X ⊆ V , let p ↓X ∈ Π(X) be the partition {p i ∩X :

p i ∈ p}\{∅},
and for Y ⊇ V , let p ↑Y ∈ Π(Y ) be the partition p ∪ y∈Y \V {{y}} .

Graphs. Our graph terminology is standard, and we refer to [START_REF] Diestel | Graph Theory[END_REF]. The vertex set of a graph G is denoted by V (G) and its edge set by E(G). An edge between two vertices x and y is denoted by xy (or yx). The subgraph of G induced by a subset X of its vertex set is denoted by G[X], and we write G \ X to denote the induced subgraph

G[V (G) \ X].
The set of vertices that are adjacent to x is denoted by N G (x), and for

U ⊆ V (G), we let N G (U ) := (∪ v∈U N G (v)) \ U . For a graph G, we denote by cc(G) the partition {V (C) : C is a connected component of G} of V (G). Clique-Width. A k-labeled graph is a pair (G, lab G ) with G a graph and lab G a function from V G to [k], called the labeling function; each set lab -1 G (i) is called a label class and vertices in lab -1 G (i) are called i-vertices.
The notion of clique-width is defined by Courcelle et al. [START_REF] Courcelle | Handle-rewriting hypergraph grammars[END_REF] and is based on the following operations.

(1) Create a graph, denoted by 1(x), with a single vertex x labeled with 1.

(2) For a labeled graph G and distinct labels i, j ∈ [k], relabel the i-vertices of G with j (denoted by ren i→j (G)). Notice that there are no more i-vertices in ren i→j (G).

(3) For a labeled graph G and distinct labels i, j ∈ [k], add all the non-existent edges between the i-vertices and the j-vertices (denoted by add i,j (G)). (4) Take the disjoint union of two labeled graphs G and H, denoted by G ⊕ H,

with lab G⊕H (v) := lab G (v) if x ∈ V (G), lab H (v) otherwise.
A k-expression is a finite well-formed term built with the four operations above. Each k-expression t evaluates into a k-labeled graph (val(t), lab(t). The clique-width of a graph G, denoted by cwd(G), is the minimum k such that G is isomorphic to val(t) for some k-expression t. We can assume without loss of generality that any k-expression defining a graph G uses O(n) disjoint union operations and O(nk 2 ) unary operations [START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF].

It is worth noticing that from the recursive definition of k-expressions, one can compute in time linear in |t| the labeling function lab(t) of val(t), and hence we will always assume that it is given.

To simplify our algorithms, we will use irredundant k-expressions (see for instance Section 4). Definition 2.1 (Irredundant k-expressions [START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF]). A k-expression is irredundant if whenever the operation add i,j is applied on a graph G, there is no edge between an i-vertex and a j-vertex in G.

It is proved in [START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF] that any k-expression can be transformed in linear time into an irredundant k-expression.

Considered Connectivity Problems. For all the problems in this article, we consider the weight function to be on the vertices. Observe that putting weights on the edges would make some of the considered problems such as Steiner Tree NP-hard even on graphs of clique-width two (since cliques have clique-width two).

A subset X ⊆ V (G) of the vertex set of a graph G is a feedback vertex set if G\X is a forest. The problem Feedback Vertex Set consists in finding a minimum feedback vertex set. It is not hard to verify that X is a minimum feedback vertex set of G if and only if G \ X is a maximum induced forest.

The problem Node-weighted Steiner Tree asks, given a subset of vertices

K ⊆ V (G) called terminals, a subset T of minimum weight such that K ⊆ T ⊆ V (G) and G[T ] is connected.
Let σ and ρ be two (non-empty) finite or co-finite subsets of N. We say that a subset

D of V (G) (σ, ρ)-dominates a subset U ⊆ V (G) if for every vertex u ∈ U , |N G (u) ∩ D| ∈ σ if u ∈ D, otherwise |N G (u) ∩ D| ∈ ρ. We say that a set X is a (σ, ρ)-dominating set (resp. co-(σ, ρ)-dominating set) of a graph G, if V (G) is (σ, ρ)-dominated by X (resp. V (G)\X).
In the connected version, we are moreover asking X to be connected.

Examples of Connected (Co-)(σ, ρ)-Dominating Set problems are shown in Table 1.

σ ρ Version Standard name N N + Normal Connected Dominating Set N + N + Normal Connected Total Dominating Set {d} N Normal Connected Induced d-Regular Subgraph N {1} Normal Connected Perfect Dominating Set {0} N Co Connected Vertex Cover

Representing Sets of Acyclic Weighted Partitions by Matrices

We recall that a weighted partition is an element of Π(V ) × N for some finite set V . Our algorithms compute a set of weighted partitions A ⊆ Π(V ) × N, for each labeled graph H used in the k-expression of the given graph G and for every subset

V ⊆ lab -1 H (V (H))
. Each weighted partition (p, w) ∈ A ⊆ Π(V ) × N is intended to mean the following: there is a solution S ⊆ V (H) of weight w such that p is the transitive closure of the following equivalence relation ∼ on V : i ∼ j if there exist an i-vertex and a j-vertex in the same component of H[S]. Moreover, for every label i in V , there is at least one i-vertex in S. For each label i in V , we expect the i-vertices of S to have an additional neighbor in any extension of S into an optimum solution. This way, for each label i ∈ V , we can consider the i-vertices of S as one vertex in terms of connectivity, since they will have a common neighbor in any extension of S. On the other hand, the labels j ∈ [k] \ V such that S contains at least one j-vertex are expected to have no additional neighbor in any extension of S into an optimum solution. Consequently, the vertices in S with a label in [k] \ V do no longer play a role in the connectivity. These expectations allow us to represent the connected components of H[S] by p. Our algorithms will guarantee that the weighted partitions computed from (p, w) are computed accordingly to these expectations.

When considering the Feedback Vertex Set problem, as said in the introduction, the trick used in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] to deal with acyclicity and that consists in counting the number of edges induced by the partial solutions would yield an n O(k) time algorithm in the case of clique-width. Since the partial solutions for the Feedback Vertex Set problem are represented by weighted partitions, we need to certify that whenever we join two weighted partitions and keep it as a partial solution, it does not correspond to a partial solution with cycles. We introduce in the following a notion of acyclicity between two partitions so that we can identify the joins of partitions which do not produce cycles. Definition 3.1. Let V be a finite set. We let acyclic be the relation on Π(V )×Π(V ) where acyclic(p, q) holds exactly when |V |+ block(p q)-( block(p)+ block(q)) = 0.

Observe that, if F p := (V, E p ) and F q := (V, E q ) are forests with components p = cc(F p ) and q = cc(F q ) respectively, then acyclic(p, q) holds if and only if E p ∩ E q = ∅ and (V, E p E q ) is a forest. The following is then quite easy to deduce. Fact 3.2. Let V be a finite set. For all partitions p, q, r ∈ Π(V ), acyclic(p, q) ∧ acyclic(p q, r) ⇔ acyclic(q, r) ∧ acyclic(p, q r).

Proof. For a partition p ∈ Π(V ), let f (p) := |V | -block(p). One easily checks that acyclic(p, q) holds if and only if f (p q) equals f (p)+f (q). One can therefore deduce, by an easy calculation from this equivalence, that acyclic(p q, r) ∧ acyclic(p, q) is equivalent to saying that f (p q r) equals f (p) + f (q) + f (r). The same statement holds for acyclic(q, r) ∧ acyclic(p, q r).

By definition of acyclic and of , we can also observe the following. Fact 3.3. Let V be a finite set. Let q ∈ Π(V ) and let X ⊆ V such that no subset of X is a block of q. Then, for each p ∈ Π(V \ X), we can observe the following equivalences p ↑X q = {V } ⇐⇒ p q ↓(V \X) = {V \ X} and (1) acyclic(p ↑X , q) ⇐⇒ acyclic(p, q ↓(V \X) ).

(2)

We modify in this section the operators on weighted partitions defined in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] in order to express our dynamic programming algorithms in terms of these operators, and also to deal with acyclicity. Let V be a finite set. First, for A ⊆ Π(V ) × N, let

rmc(A) := {(p, w) ∈ A : ∀(p, w ) ∈ A, w ≤ w)}.
This operator, defined in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF], is used to remove all the partial solutions whose weights are not maximum w.r.t. to their partitions.

Ac-Join. Let V be a finite set. For A ⊆ Π(V ) × N and B ⊆ Π(V ) × N, we define acjoin(A, B) ⊆ Π(V ∪ V ) × N as acjoin(A, B) := {(p ↑V
q ↑V , w1 + w2) : (p, w1) ∈ A, (q, w2) ∈ B and acyclic(p ↑V , q ↑V )}.

This operator is more or less the same as the one in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF], except that we incorporate the acyclicity condition. It is used to construct partial solutions while guaranteeing the acyclicity.

Project. For X ⊆ V and A ⊆ Π(V ) × N, let proj(A, X) ⊆ Π(V \ X) × N be proj(A, X) := {(p ↓(V \X) , w) : (p, w) ∈ A and ∀p i ∈ p, (p i \ X) = ∅}.
This operator considers all the partitions such that no block is completely contained in X, and then remove X from those partitions. We index our dynamic programming tables with functions that informs on the label classes playing a role in the connectivity of partial solutions, and this operator is used to remove from the partitions the label classes that are required to no longer play a role in the connectivity of the partial solutions. If a partition has a block fully contained in X, it means that this block will remain disconnected in the future steps of our dynamic programming algorithm, and that is why we remove such partitions (besides those with cycles).

One needs to perform the above operations efficiently, and this is guaranteed by the following, which assumes that log(|A|) ≤ |V | O (1) for each A ⊆ Π(V ) × N (this can be established by applying the operator rmc). We now define the notion of representative sets of weighted partitions which is the same as the one in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF], except that we need to incorporate the acyclicity condition as for the acjoin operator above. Definition 3.5. Let V be a finite set and let A ⊆ Π(V ) × N. For q ∈ Π(V ), let ac-opt(A, q) := max{w : (p, w) ∈ A, p q = {V } and acyclic(p, q)}.

A set of weighted partitions

A ⊆ Π(V ) × N ac-represents A if for each q ∈ Π(V ), it holds that ac-opt(A, q) = ac-opt(A , q).
Let Z and V be two finite sets. A function f : 2

Π(V )×N × Z → 2 Π(V )×N is said to preserve ac-representation if for each A, A ⊆ Π(V ) × N and z ∈ Z, it holds that f (A , z) ac-represents f (A, z) whenever A ac-represents A.
At each step of our algorithm, we will compute a small set S that ac-represents the set S containing all the partial solutions. In order to prove that we compute an ac-representative set of S, we show that S = f (R 1 , . . . , R t ) with f a composition of functions that preserve ac-representation, and R 1 , . . . , R t the sets of partials solutions associated with the previous steps of the algorithm. To compute S , it is sufficient to compute f (R 1 , . . . , R t ), where each R i is an ac-representative set of R i . The following lemma guarantees that the operators we use preserve acrepresentation.

Lemma 3.6. The union of two sets in 2 Π(V )×N and the operators rmc, proj, and acjoin preserve ac-representation.

Proof. Let V be a finite set and let A and A be two subsets of Π(V ) × N. The proof for the union follows directly from the definition of ac-opt.

Rmc. Let q ∈ Π(V ). By the definition of rmc, whenever (p, w) ∈ A is such that p q = {V }, acyclic(p, q) and ac-opt(A, q) = w, then (p, w) ∈ rmc(A), otherwise there would exist (p, w ) ∈ A with w > w which would contradict w = ac-opt(A, q). Therefore, ac-opt(rmc(A), q) = ac-opt(A, q). We can then conclude that if A ac-represents A, it holds that rmc(A ) ac-represents rmc(A).

Projections. Because proj(A, X) = proj(proj(A, x), X \ {x}) for all X ⊆ V and x ∈ X, we can assume that X = {x}. Let q ∈ Π(V \ {x}). For every (p, w) ∈ A, if {x} ∈ p, then p q ↑x = {V }, and (p ↓V \x , w) / ∈ proj(A, {x}). Otherwise, (p ↓V \x , w) ∈ proj(A, {x}), and by Fact 3.3 we have p ↓V \x q = {V \ {x}} ⇐⇒ p q ↑x = {V } and acyclic(p ↓V \x , q) ⇐⇒ acyclic(p, q ↑x ).

Therefore, we have ac-opt(proj(A, {x}), q) = ac-opt(A, q ↑x ). From this equality, we can conclude that proj(A , {x}) ac-represents proj(A, {x}), for all A ⊆ A such that A ac-represents A.

Ac-Join. Let V be a finite set and let

B ⊆ Π(V ) × N. Let r ∈ Π(V ∪ V ).
Observe that for all (q, w 2 ) ∈ B, if a subset of V \V is a block of q ↑V r, then for all p ∈ Π(V ), we have p ↑V q ↑V r = {V ∪V }. Therefore, ac-opt(acjoin(A, B), r) = ac-opt(acjoin(A, B ), r) where B is the set of all (q, w) ∈ B such that no subset of V \ V is a block of q ↑V r.

By definition, ac-opt(acjoin(A, B ), r) equals

max{w1 + w2 : (p, w1) ∈ A ∧ (q, w2) ∈ B ∧ (p ↑V q ↑V r) = {V ∪ V } ∧ acyclic(p ↑V , q ↑V ) ∧ acyclic(p ↑V q ↑V , r)}.
By Fact 3.2, ac-opt(acjoin(A, B ), r) is then equal to

max{w1 + w2 : (p, w1) ∈ A ∧ (q, w2) ∈ B ∧ (p ↑V q ↑V r) = {V ∪ V } ∧ acyclic(q ↑V , r) ∧ acyclic(p ↑V , q ↑V r)}.
We deduce, by Fact 3.3 and the definition of B , that ac-opt(acjoin(A, B ), r)

equals max{w1 + w2 : (p, w1) ∈ A ∧ (q, w2) ∈ B ∧ (p (q ↑V r) ↓V ) = {V } ∧ acyclic(q ↑V , r) ∧ acyclic(p, (q ↑V r) ↓V )}.
Therefore, we can conclude that ac-opt(acjoin(A, B), r) equals max{ac-opt(w2 + A, (q ↑V r) ↓V ) : (q, w2) ∈ B ∧ acyclic(q ↑V , r)}.

Therefore, if A ac-represents A, then we can conclude that ac-opt(acjoin(A, B), r) equals ac-opt(acjoin(A , B), r). As this statement is true for all r ∈ Π(V ∪ V ), we can conclude that acjoin(A , B) ac-represents acjoin(A, B) whenever A ac-represents A. Symmetrically, we deduce that acjoin(A, B ) ac-represents acjoin(A, B) whenever B ac-represents B.

In the remaining, we will prove that, for every set

A ⊆ Π(V ) × N, we can find, in time |A| • 2 O(|V |) , a subset A ⊆ A of size at most |V | • 2 |V | that ac-represents A.
As in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF], we will encode the ac-representativity by a matrix over F 2 and show that this one has rank at most the desired bound. Next, we show that an optimum basis of this matrix ac-represents A and such a basis can be computed using the following lemma from [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF]. The constant ω denotes the matrix multiplication exponent.

Lemma 3.7 ([2]

). Let M be an n × m-matrix over F 2 with m ≤ n and let w : {1, . . . , n} → N be a weight function. Then, one can find a basis of maximum weight of the row space of M in time O(nm ω-1 ). Theorem 3.8. There exists an algorithm ac-reduce that, given a set of weighted partitions

A ⊆ Π(V ) × N, outputs in time |A| • 2 (ω-1)•|V | • |V | O(1) a subset A of A that ac-represents A and such that |A | ≤ |V | • 2 |V |-1 .
Proof. If V = ∅, then it is enough to return A := {(∅, w)}, where (∅, w) ∈ A and w is maximum because ∅ is the only partition of the empty set.

Assume from now that |V | = ∅ (this will ensure that the following definitions exist). Let us first define the matrix that encodes the property that the join of two partitions corresponds to a partition arising from a connected solution.

Let v 0 be a fixed element of V and let cuts(V

) := {(V 1 , V 2 ) : V 1 V 2 = V and v 0 ∈ V 1 }. Let M and C be, respectively, a (Π(V ), Π(V ))-matrix and a (Π(V ), cuts(V ))- matrix, both over F 2 , such that M [p, q] := 0 if p q = {V }, 1 otherwise. C[p, (V1, V2)] := 0 if p (V1, V2), 1 otherwise.
As in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF][START_REF] Cygan | Solving connectivity problems parameterized by treewidth in single exponential time[END_REF], we fix an element v 0 to ensure that for all p ∈ Π(V ), the number of cuts

(V 1 , V 2 ) such that p q (V 1 , V 2 )
is odd if and only if p q = {V }. In fact, this number equals 2 block(p)-1 . This property is used in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] to prove that

M = C • C t .
Let A be a set of weighted partitions. In order to compute an ac-representative set of A, we will decompose A into a small number of sets A i . Then, for each set A i , we compute a set A i ⊆ A i of A i such that the union of the sets A i ac-represents A. To compute A i , we use Lemma 3.7 to find a maximum basis of the row space of C restricted to A i .

For each

0 ≤ i ≤ |V |-1, let A i be the set {p : (p, w) ∈ A and |V |-block(p) = i}

, and let C i

A be the restriction of C to rows in A i . Let B i be a basis of the row space of C i A of maximum weight, where the weights are the weights 1 of the considered weighted partitions in A. Observe that 1) . By Lemma 3.7, we can compute B i in time

|B i | ≤ 2 |V |-1 because the rank of C i A is bounded by |cuts(V )| = 2 |V |-1 . For p ∈ A i , let B i (p) be the subset of B i such that C[p, (V 1 , V 2 )] = q∈Bi(p) C[q, (V 1 , V 2 )] for all (V 1 , V 2 ) ∈ cuts(V ). Let A i be the subset of A corresponding to the rows in B i , and let A := A 0 • • • A |V |-1 . Notice that |A | ≤ |V | • 2 |V |-1 . Since C i A has |A i | rows and 2 |V |-1 columns, A i is computable in time |A i | • 2 |V |-1 • |V | O(
|A i | • 2 (ω-1)•|V | • |V | O(1) . Hence, we can compute A in time |A| • 2 (ω-1)•|V | • |V | O(1) because {A 0 , . . . , A |V |-1 } is a partition of {p : (p, w) ∈ A}.
Let us show that for all p ∈ A i and r

∈ Π(V ), if M [p, r] = 1, then there is q ∈ B i (p) such that M [q, r] = 1. Now, from the equality M = C • C t , we have M [p, r] = (V1,V2)∈cuts(V ) C[p, (V 1 , V 2 )] • C t [(V 1 , V 2 ), r] = (V1,V2)∈cuts(V )   q∈Bi(p) C[q, (V 1 , V 2 )]   • C t [(V 1 , V 2 ), r] = q∈Bi(p)   (V1,V2)∈cuts(V ) C[q, (V 1 , V 2 )] • C t [(V 1 , V 2 ), r]   = q∈Bi(p) M [q, r]. So, M [p, r] = 1 if and only if there is an odd number of q ∈ B i (p) such that M [q, r] = 1.
It remains now to show that A ac-represents A. Since by construction A ⊆ A, for each q ∈ Π(V ), we have ac-opt(A, q) ≥ ac-opt(A , q). Assume towards a contradiction that A does not ac-represent A. Thus, there is q ∈ Π(V ) such that ac-opt(A, q) > ac-opt(A , q), and hence there is (p, w) ∈ A \ A such that p q = {V }, acyclic(p, q) holds and w > ac-opt(A , q). Let i := |V | -block(p).

Hence, p ∈ A i and there exists

p ∈ B i (p) such that M [p , q] = 1 that is p q = {V }. Let (p , w ) ∈ A i such that p ∈ B i (p), p q = {V } and w is maximum. Since (p , w ) ∈ A i , we have |V | -block(p ) = |V | -block(p) = i.
We can conclude that acyclic(p , q) holds because acyclic(p, q) holds. Indeed, by definition, acyclic(p, q) holds if and only if |V |+ block(p q)-( block(p)+ block(q)) = 0. Since p q = {V }, we deduce that acyclic(p, q) holds if and only if i = |V | + 1 -block(q). Because p q = {V } and |V | -block(p ) = i, we can conclude that acyclic(p , q) holds.

Hence, we have ac-opt(A , q) ≥ w . Since w > ac-opt(A , q), it must hold that w > w . But, (B i \ {p }) ∪ {p} is also a basis of C i A since the set of independent row sets of a matrix forms a matroid. Since w > w , the weight of (B i \ {p }) ∪ {p} is strictly greater than the weight of B i , yielding a contradiction.

Feedback Vertex Set

We will use the weighted partitions defined in the previous section to represent the partial solutions. At each step of our algorithm, we will ensure that the stored weighted partitions correspond to acyclic partial solutions. However, the framework in the previous section deals only with connected acyclic solutions. So, instead of computing a maximum induced forest (the complementary of a minimum feedback vertex set), we will compute a maximum induced tree. As in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF], we introduce a hypothetical new vertex, denoted by v 0 , that is universal and we compute a pair (F, E 0 ) so that F is a maximum induced forest of G, E 0 is a subset of edges incident to v 0 , and (V (F )∪{v 0 }, E(F )∪E 0 ) is a tree. For a weight function w on the vertices of G and a subset S ⊆ V (G), we denote by w(S) := v∈S w(v). In order now to reduce the sizes of the dynamic programming tables, we will express the steps of the algorithm in terms of the operators on weighted partitions defined in the previous section.

Let us explain the idea of the algorithm before defining the dynamic programming tables and the steps. Let H be a k-labeled graph. We are interested in storing ac-representative sets of all induced forests of H that may produce a solution. If F is an induced forest of H, we would like to store the partition p corresponding to the quotient set of the transitive closure of the relation ∼ on V (F ) where x ∼ y if x and y have the same label or are in the same connected component.

If J ⊆ [k] is such that x∈V (F ) lab H (x) = J,
then this is equivalent to storing the partition p of J where i and j are in the same block if there are, respectively, an i-vertex x and a j-vertex y in the same connected component of F . Now, if H is used in a k-expression of a k-labeled graph G, then in the cliquewidth operations defining G we may add edges between the i-vertices and the j-vertices of H, for some i, j ∈ J. Now, this has no effect if there are exactly one i-vertex and one j-vertex at distance one in H[F ], otherwise cycles may be created, e.g., whenever an i-vertex and a j-vertex are non-adjacent and belong to the same connected component, or the number of i-vertices and j-vertices are both at least 2. Nevertheless, we are not able to handle all these cases with the operators on weighted partitions. To resolve the situation where an i-vertex and a jvertex are already adjacent, we consider irredundant k-expressions, i.e., whenever an operation add i,j is used there are no edges between i-vertices and j-vertices. For the other cases, we index the dynamic programming tables with functions s :

[k] → {γ 0 , γ 1 , γ 2 , γ -2 } that tells, for each i ∈ [k], if the label class lab -1 H (i) does not intersect F (s(i) = γ 0 ), or if it does, in one vertex (s(i) = γ 1 )
, or in at least two (s(i) ∈ {γ 2 , γ -2 }) vertices. We have two possible values for label classes intersecting V (F ) in at least two vertices because whenever two i-vertices belong to the same connected component of F , F does not produce a valid solution once an operation add i, is applied to H with s( ) = γ 0 . So, if a label class lab -1 H (i) intersects V (F ) in at least two vertices, since we do not know whether a clique-width operation add i, with s( ) = γ 0 will be applied to H, we guess it in the function s, and whenever s(i) equals γ -2 , we throw p when we encounter an add i, operation (with s( ) = γ 0 ), and if s(i) = γ 2 , we force F to not having two i-vertices in the same connected component.

Nonetheless, even though we are able to detect the partitions corresponding to induced subgraphs with cycles, taking p as the transitive closure of the relation ∼ on [k] describe above may detect false cycles. Indeed, let x i , x j and x , x be, respectively, an i-vertex, a j-vertex and two -vertices, such that x i and x belong to the same connected component in F , and similarly, x j and x in another connected component of F . Now, if we apply an operation add i,j on H, we may detect a cycle with p (through the acjoin operation), which may not exist when for instance there are only one i and one j-vertex in F , both in different connected components. We resolve this case with the functions s indexing the dynamic programming tables by forcing each label i in s -1 (γ 2 ) to wait for exactly one clique-width operation add i,t for some t ∈ [k]. We, therefore, translate all the acyclicity tests to the acjoin operation. Indeed, the case explained will be no longer a false cycle as x i and x j will be adjacent (with the add i,j operation), and we know that x and x will be connected to some other vertex in F , and since x i is connected to x and x j to x , we have a cycle. The following notion of certificate graph formalizes this requirement.

Definition 4.1 (Certificate graph of a solution). Let G be a k-labeled graph, F an induced forest of G, s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }, and E 0 a subset of edges incident to v 0 . Let β be a bijection from s -1 (γ 2 ) to a set V + s disjoint from V (G) ∪ {v 0 }.
The certificate graph of (F, E 0 ) with respect to s, denoted by CG(F, E 0 , s), is the graph

(V (F ) ∪ V + s ∪ {v 0 }, E(F ) ∪ E 0 ∪ E + s ) with E + s := i∈s -1 (γ2) {{v, β(i)} : v ∈ (V (F ) ∩ lab -1 G (i))}.
In a certificate graph of (F, E 0 ), the vertices in V + s represent the expected future neighbors of all the vertices in V (F ) ∩ lab -1 G (s -1 (γ 2 )). For convenience, whenever we refer to a vertex v + i of V + s , we mean the vertex of V + s adjacent to the i-vertices in CG(F, E 0 , s). See Figure 2 for an example of a certificate graph.

1 v + 2 v + 3 2 3 4 v 0 5 6 7 8 Figure 2. Example of a certificate graph; here p = {{v 0 , 1}, {2, 3}, {4}}, s -1 (γ 0 ) = {7, 8}, s -1 (γ 1 ) = {1, 4}, s -1 (γ 2 ) = {2, 3} and s -1 (γ -2 ) = {5, 6}. The set V + s is {v + 2 , v + 3 } with v + 2
mapped to 2 and v + 3 mapped to 3.

We are now ready to define the sets of weighted partitions which representatives we manipulate in our dynamic programming tables.

Definition 4.2 (Weighted partitions in

A G [s]). Let G be a k-labeled graph and let s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 } be a total function. The entries of A G [s] are all weighted partitions (p, w) ∈ Π(s -1 ({γ 1 , γ 2 }) ∪ {v 0 }) × N such that there exist an induced forest F of G and E 0 ⊆ {v 0 v : v ∈ V (F )} so that w(V (F )) = w, and
(1) The sets s -1

(γ 0 ) = {i ∈ [k] : |V (F ) ∩ lab -1 G (i)| = 0} and s -1 (γ 1 ) = {i ∈ [k] : |V (F ) ∩ lab -1 G (i)| = 1}. (2) The certificate graph CG(F, E 0 , s) is a forest. (3) Each connected component C of CG(F, E 0 , s) has at least one vertex in lab -1 G (s -1 ({γ 1 , γ 2 })) ∪ {v 0 }. (4) The partition p equals (s -1 ({γ 1 , γ 2 }) ∪ {v 0 })/ ∼ where i ∼ j if and only if a vertex in lab -1 G (i) ∩ V (F ) is connected, in CG(F, E 0 , s), to a vertex in lab -1 G (j) ∩ V (F ); we consider lab -1 G (v 0 ) = {v 0 }.
Conditions ( 1) and ( 3) are as explained above, and automatically imply that, 2) and (4) guarantee that (V (F ) ∪ {v 0 }, E(F ) ∪ E 0 ) can be extended into a tree, if any. They also guarantee that cycles detected through the acjoin operation correspond to cycles, and each cycle can be detected with it.

for each i in s -1 ({γ 2 , γ -2 }), we have |V (F ) ∩ lab -1 G (i)| ≥ 2. Conditions (
In the sequel, we call any triplet (F, E 0 , (p,

w(F ))) a candidate solution in A G [s] if Condition (4) is satisfied, and if in addition Conditions (1)-(3) are satisfied, we call it a solution in A G [s].
Given a k-labeled graph G, the size of a maximum induced tree of G corresponds to the maximum, over all s :

[k] → {γ 0 , γ 1 , γ 2 , γ -2 } with s -1 (γ 2 ) = ∅, of max{w : ({s -1 (γ 1 ) ∪ {v 0 }}, w) ∈ A G [s]}. Indeed, by definition, if ({s -1 (γ 1 ) ∪ {v 0 }}, w) belongs to A G [s]
, then there exist an induced forest F of G with w(F ) = w and a set E 0 of edges incident to v 0 such that (V (F ) ∪ {v 0 }, E(F ) ∪ E 0 ) is a tree. This follows from the fact that if s -1 (γ 2 ) = ∅, then we have CG(F, E 0 , s) = (V (F ) ∪ {v 0 }, E(F ) ∪ E 0 ). Our algorithm will store, for each k-labeled graph G and each function s

: [k] → {γ 0 , γ 1 , γ 2 , γ -2 }, an ac-representative set tab G [s] of A G [s].
We are now ready to give the different steps of the algorithm, depending on the clique-width operations.

Computing tab G for G = 1(x). For s : {1} → {γ 0 , γ 1 , γ 2 , γ -2 }, let tab G [s] :=      {({{1, v 0 }}, w(x)), ({{1}, {v 0 }}, w(x))} if s(1) = γ 1 , {({{v 0 }}, 0)} if s(1) = γ 0 , ∅ if s(1) ∈ {γ 2 , γ -2 }.
Since |V (G)| = 1, there is no solution intersecting the label class lab -1 G (1) on at least two vertices, and so the set of weighted partitions satisfying Definition 4.2 equals the empty set for s(1) ∈ {γ 2 , γ -2 }. If s(1) = γ 1 , there are two possibilities, depending on whether

E 0 = ∅ or E 0 = {xv 0 }. We can thus conclude that tab G [s] = A G [s] is correctly computed. Computing tab G for G = add i,j (H). We can suppose that H is k-labeled. Let s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }. (a) If s(i) = γ 0 or s(j) = γ 0 , then let tab G [s] := tab H [s].
We just copy all the solutions not intersecting lab -1 H (i) or lab -1 H (j). In the following cases, we assume that s(i) = γ 0 and s(j) = γ 0 . In this case, we do not need to use the operators ac-reduce and rmc since we update tab G [s] with one table from tab H . (b) If s(i) = γ 2 or s(j) = γ 2 , then we let tab G [s] = ∅. In this case A G [s] = ∅. Indeed, for every set X ⊆ V (G) respecting Condition (1), the graph CG(X, E 0 , s) contains a cycle, for all subsets E 0 ⊆ {xv 0 : x ∈ X}. For example, if s(i) = γ 2 and s(j) = γ 1 , then the two i-vertices in X are adjacent in CG(X, ∅, s) to v +

A := proj(s -1 (γ -2 ) ∩ {i, j}, acjoin(tab H [s H ], {({{i, j}}, 0)})
where s H ( ) := s( ), for ∈ [k] \ {i, j}, and

(s H (i), s H (j)) :=      (γ 1 , γ 1 ) if s(i) = s(j) = γ 1 , (γ 2 , γ 1 ) if (s(i), s(j)) = (γ -2 , γ 1 ), (γ 1 , γ 2 ) if (s(i), s(j)) = (γ 1 , γ -2 ).
Observe that this case corresponds to s(i), s(j) ∈ {γ 1 , γ -2 } with s(i) = γ 1 or s(j) = γ 1 . Intuitively, we consider the weighted partitions (p, w) ∈ tab H [s H ] such that i and j belong to different blocks of p, we merge the blocks containing i and j, remove the elements in s -1 (γ -2 ) ∩ {i, j} from the resulting block, and add the resulting weighted partition to A. Notice that it is not necessarily to call the operator ac-reduce in this case since we update tab G [s] with only one table from tab H . Now, we assume that we are in Case (d), that is s(i), s(j) ∈ {γ 1 , γ -2 } with s(i) = γ 1 or s(j) = γ 1 . We can assume w.l.o.g. that s

Lemma 4.3. Let G = add i,j (H) be a k-labeled graph. For each function s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }, tab G [s] ac-represents A G [s] assuming that tab H [s ] ac-represents A H [s ] for all s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }. Proof. We first recall that lab G (x) = lab H (x) for all x ∈ V (G) = V (H). If
(j) = γ 1 . Let (F, E 0 , (p, w)) be a solution in A G [s]. We prove that (p, w) ∈ A. Let {x j } := V (F ) ∩ lab -1 G (j) (by assumption s(j) = γ 1 ), X i := V (F ) ∩ lab -1 G (i), E i,j := {vx j : v ∈ X i }, and
F H := (V (F ), E(F ) \ E i,j
). Because we consider only irredundant k-expressions, we know that E i,j ∩ E(H) = ∅, i.e., F H is an induced forest of H. Let p be the partition on s -1

H ({γ 1 , γ 2 }) ∪ {v 0 } such that (F H , E 0 , (p , w)) is a candidate solution in A H [s H ]. We claim that (F H , E 0 , s H ) is a solution in A H [s H ]. By the definition of s H , Condition (1) is trivially satisfied. If |X i | = 1, then CG(F H , E 0 , s H ) is a subgraph of CG(F, E 0 , s) and so Condition (2) is satisfied. And if |X i | ≥ 2 and CG(F H , E 0 , s H ) contains a cycle, then the cycle should contain the vertex v + i ∈ V +
s H , but this vertex may be replaced by x j in CG(F, E 0 , s), contradicting the fact this latter is acyclic. Condition (3) is also satisfied because s H (i), s H (j) ∈ {γ 1 , γ 2 } and for every connected component

C of CG(F H , E 0 , s H ), either C is a connected component of CG(F, E 0 , s) or C contains an -vertex with ∈ {i, j}. Therefore, (F H , E 0 , (p , w)) is a solution in A H [s H ].
It remains to prove that (p, w) is added in A. We claim that acyclic(p , {{i, j}} ↑V ) holds with V = s -1 (γ 1 , γ 2 ) ∪ {v 0 }. By definition of acyclic it is equivalent to prove that i and j cannot belong to a same block of p . Assume towards a contradiction that i and j belong to a same block of p . Then, there is a path, in CG(F H , E 0 , v 0 ), between an i-vertex x i and the j-vertex x j of F . Let us choose this path P to be the smallest one. One first notices that P cannot contain the vertex v

+ i of V + s H , if any, because v + i is only adjacent to i-vertices. Because V (CG(F H , E 0 , s H )) \ {v + i } = V (CG(F, E 0 , s)), we would conclude that CG(F, E 0 , s) contains a cycle as x i x j ∈ E(F ) \ E(F H ), contradicting that (F, E 0 , (p, w)) is a solution in A G [s]
. Therefore, acyclic(p , {{i, j}} ↑V ) holds. By assumption s(j) = γ 1 , thus s -1 (γ -2 ) ∩ {i, j} ⊆ {i}. Since i and j are in the same block of the partition p {{i, j}} ↑V , we conclude that (p, w) ∈ proj(s -1 (γ -2 ) ∩ {i, j}, acjoin({(p , w)}, {({{i, j}}, 0)})).

It remains to prove that each weighted partition (p, w)

∈ A belongs to A G [s]. Let (F H , E H 0 , (p , w)) be a solution in A H [s H ] so that (p, w) ∈ proj(s -1 (γ -2 ) ∩ {i, j}, acjoin({(p , w)}, {({{i, j}}, 0)})). Let F = G[V (F H )].
By assumption s(j) = γ 1 , and thus s 1) is trivially satisfied by the definition of s H .

H (j) = γ 1 . Let {x j } := V (F H ) ∩ lab -1 H (j), X i := V (F H ) ∩ lab -1 H (i), and E i,j := {x j v : v ∈ X i }. Notice that E(F ) \ E(F H ) = E i,j . We claim that (F, E H 0 , (p, w)) is a solution in A G [s]. • First, Condition (
• Secondly, CG(F, E H 0 , s) is a forest. Indeed, {i, j} cannot be a block of p , otherwise the acjoin operator would discard p .

If |X i | = 1, then CG(F, E H 0 , s) = (V (CG(F H , E H 0 , s H )), E(CG(F H , E H 0 , s H )) ∪ E i,j ) and it is clearly a forest. Otherwise, if |X i | ≥ 2, then CG(F, E H 0 , s) can be obtained from CG(F H , E H
0 , s H ) by fusing the vertex v + i and the vertex x j . Clearly, this operation keeps the graph acyclic since x j and v

+ i are not connected in CG(F H , E H 0 , s H ). Thus (F, E H 0 , (p, w)) satisfies Condition (2). • Each connected component of CG(F H , E H 0 , s H ) is contained in a connected component of CG(F, E H 0 , s)
, and the i-vertices are in the same connected component, in CG(F, E H 0 , s), as x j . Therefore, Condition (3) is satisfied by (F, E H 0 , (p, w)) as s(j) = γ 1 and s( ) = s H ( ) for all ∈ [k] \ {i, j}. • Also, Condition (4) is satisfied as p is then obtained from p by merging the blocks of p which contains i and j, and by removing i if s(i) = γ -2 . We can therefore conclude that (F,

E H 0 , (p, w)) is a solution in A G [s].
Computing tab G for G = ren i→j (H). We can suppose that

H is k-labeled. Let s : [k] \ {i} → {γ 0 , γ 1 , γ 2 , γ -2 }. (a) Let A 1 := tab H [s 1 ]
where s 1 (i) = γ 0 and s 1 ( ) = s( ) for all ∈ [k] \ {i}. This set contains all weighted partitions corresponding to solutions not intersecting lab -1 H (i). They are trivially solutions in

A G [s]. (b) If s(j) = γ 0 , then let A 2 = ∅, otherwise let s 2 : [k] → {γ 0 , γ 1 , γ 2 , γ -2 } such that s 2 (j) = γ 0 , s 2 (i) = s(j) and s 2 ( ) = s( ) for all ∈ [k] \ {i, j} and let A 2 := tab H [s 2 ] if s(j) = γ -2 , proj({i}, acjoin(tab H [s 2 ], {({{i, j}}, 0)})) otherwise.
This set contains all weighted partitions corresponding to solutions not intersecting lab -1 H (j). They are solutions in A G [s] by replacing i by j with the acjoin operator, if necessary, in the corresponding weighted partitions. Notice that if s(j) = γ 0 , then s 1 = s 2 , this is why we let A 2 = ∅ in this case. (c) If s(j) = γ -2 , then let A 3 := ∅, otherwise let

A 3 := s3∈S3 proj({i, j}, tab H [s 3 ]),
where S 3 is the set of functions s 3 with s 3 (i), s 3 (j) ∈ {γ 1 , γ -2 }, and s 3 ( ) = s( ) for all ∈ [k] \ {i, j}. Intuitively, S 3 is the set of functions coherent with s if s(j) = γ -2 . The set A 3 corresponds to partial solutions intersecting lab -1 H (i)

and lab -1 H (j) when s(j) = γ -2 . In this case, we have to ensure that the partial solutions in A 3 respect Condition (3) of Definition 4.2. We do that by removing all the partitions with a block included in {i, j}. (d) We now define the last set considering the other cases. If s(j) = γ 2 , then let A 4 = ∅, otherwise let

A 4 := s4∈S4 proj({i}, acjoin(tab H [s 4 ], {({{i, j}}, 0)})),
where S 4 is the set of functions s 4 with s 4 (i), s 4 (j) ∈ {γ 1 , γ 2 } and s 4 ( ) = s( ) for all ∈ [k] \ {i, j}. Informally, S 4 is the set of functions compatible with s if s(j) = γ 2 . The set A 4 corresponds to partial solutions intersecting lab -1 H (i) and lab -1 H (j) when s(j) = γ 2 . We have to force that i-vertices and j-vertices belong to different connected components. We check this with the function acyclic in the operator acjoin.

We let tab G [s] := ac-reduce(rmc(A 1 ∪ A 2 ∪ A 3 ∪ A 4 )). Lemma 4.4. Let G = ren i→j (H) with H a k-labeled graph. For each s : [k]\{i} → {γ 0 , γ 1 , γ 2 , γ -2 }, the table tab G [s] ac-represents A G [s] assuming that tab H [s ] ac- represents A H [s ] for all s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }.

Proof. Since the used operators preserve ac-representation, it is enough to prove

that A G [s] = A 1 ∪ A 2 ∪ A 3 ∪ A 4 if we let tab H [s ] = A H [s ] for every s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }. Let (F, E 0 , (p, w)) be a solution in A G [s]. We want to prove that (p, w) ∈ A 1 ∪ A 2 ∪ A 3 ∪ A 4 . If V (F ) does not intersect lab -1 H (i), then (F, E 0 , (p, w)) is a solution in A H [s 1 ]. Assume now that V (F ) intersects lab -1 H (i). If V (F ) ∩ lab -1 H (j) = ∅ and s(j) = γ -2 , (F, E 0 , (p, w)) is a solution in A H [s 2 ]. If V (F ) ∩ lab -1
H (j) = ∅ and s(j) ∈ {γ 1 , γ 2 }, then it is easy to check that (F, E 0 , (p , w)) is a solution in A H [s 2 ] where p is obtained from p by replacing j by i.

We may assume now that V (F ) ∩ lab -1

H (i) = ∅, V (F ) ∩ lab -1 H (j) = ∅. Then, we have s(j) ∈ {γ 2 , γ -2 } as |lab -1 G (j) ∩ V (F )| ≥ 2.
Let s be a function from [k] such that s ( ) := s( ) for all ∈ [k] \ {i, j}, and for t ∈ {i, j},

s (t) := γ 1 if |V (F ) ∩ lab -1 H (t)| = 1, s(j) if |V (F ) ∩ lab -1 H (t)| ≥ 2.
By definition, if s(j) = γ -2 , then s belongs to S 3 and if s(j) = γ 2 , then s belongs to S 4 . Let p be the partition on s

-1 ({γ 1 , γ 2 }) ∪ {v 0 } such that (F, E 0 , (p , w)) is a candidate solution in A H [s ]. We claim that (F, E 0 , (p , w)) is a solution in A H [s ]
. By Definition of s and of (F, E 0 ), Condition (1) is satisfied by (F, E 0 , (p , w)). Suppose first that s(j) = γ -2 . Observe that Condition (2) is satisfied because the certificate graphs of (F, E 0 ) with respect to s and s are the same. Condition (3) is also satisfied by definition of s and because CG(F, E 0 , s) = CG(F, E 0 , s ). So, (F, E 0 , (p , w)) is a solution in A H [s ].

Assume now that s(j) = γ 2 . Condition (2) is satisfied. Indeed, if s (i) = γ 1 , then CG(F, E 0 , s) is a subgraph of CG(F, E 0 , s ). Otherwise, if s (i) = γ 2 , then CG(F, E 0 , s) can be obtained from CG(F, E 0 , s ) by fusing v + i with v + j . In both cases, it is easy to see that CG(F, E 0 , s ) is acyclic as CG(F, E 0 , s) is acyclic. Condition (3) is satisfied because each connected component C of CG(F, E 0 , s) contains at least a vertex in lab -1 G (s -1 ({γ 1 , γ 2 })) ∪ {v 0 }, and we have from the definition of s lab -1

H (s -1 ({γ 1 , γ 2 })) = lab -1 G (s -1 ({γ 1 , γ 2 })).
In both cases, (F, E 0 , (p , w)) is a solution in A H [s ], and depending on s(j), we can clearly conclude that (p, w) is obtained from (p , w).

Let us now prove that for any weighted partition (p, w)

∈ A 1 ∪ A 2 ∪ A 3 ∪ A 4 , there is a pair (F, E 0 ) such that (F, E 0 , (p, w)) is a solution in A G [s]. This is clear if (p, w) ∈ A 1 ∪ A 2 .
Assume that s(j) = γ -2 and let (p, w) ∈ A 3 . Let s 3 ∈ S 3 and (p , w) be the weighted partition from tab H [s 3 ] from which (p, w) is obtained. Let (F, E 0 , (p , w)) be a solution in

A H [s 3 ]. We claim that (F, E 0 , (p, w)) is a solution in A G [s]. By definition of S 3 , we clearly have |V (F ) ∩ lab -1 H ({i, j})| = |V (F ) ∩ lab -1 G (j)| ≥ 2.
We deduce that Condition (1) is satisfied. Condition ( 2) is also satisfied because CG(F, E 0 , s 3 ) is the same as CG(F, E 0 , s). We claim that Condition (3) is satisfied.

Notice that s -1 ({γ 1 , γ 2 }) = s -1 3 ({γ 1 , γ 2 }) \ {i, j}. Moreover, if i ∈ s -1 3 ({γ 1 , γ 2 })
, by definition of s 3 , we have s 3 (i) = γ 1 , that is F has exactly one i-vertex (the same statement is true for j). Since we use the operator proj with {i, j}, there is no block of p included in {i, j}. Hence, if F contains one i-vertex (one j-vertex), then, by Condition (4), this vertex is connected in CG(F, E 0 , s 3 ) to either v 0 or an -vertex with ∈ s -1 ({γ 1 , γ 2 }). We can conclude that each connected component of F must contain a vertex in lab -1 G (s -1 ({γ 1 , γ 2 })) ∪ {v 0 }, i.e. Condition (3) is satisfied. Condition ( 4) is satisfied owing to the fact that p is obtained from p by doing a projection on {i, j}.

Assume now that s(j) = γ 2 and let (p, w) ∈ A 4 . Let s 4 ∈ S 4 and (p , w) be the weighted partition from tab H [s 4 ] from which (p, w) is obtained, and let (F, E 0 , (p , w)) be a solution in A H [s 4 ]. By definition of S 4 , we deduce that Condition (1) is satisfied (see the case s(j) = γ -2 ). If there is a cycle in CG(F, E 0 , s), then it must be between an i-vertex and a j-vertex of H, but then we must have a path between them in CG(F, E 0 , s 4 ), i.e., i and j belong to a same block of p , contradicting that (p, w) is produced from (p , w) (because the acjoin operator would detect that acyclic(p, {{i, j}} ↑[k] ) does not hold). So, Condition (2) is satisfied. We deduce that Condition (3) is satisfied from the fact that by definition of s 4 , we have lab -1 G (s -1 ({γ 1 , γ 2 })) = lab -1 H (s -1 4 ({γ 1 , γ 2 })). Also, as p is obtained from p by merging the blocks containing i and j, and by removing i, we deduce that Condition (4) is satisfied.

In both cases, we can conclude that (F,

E 0 , (p, w)) is a solution in A G [s]. Computing tab G for G = G a ⊕ G b . We can suppose w.l.o.g. that G a and G b are both k-labeled 2 . Let s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }. We say that s a : [k] → {γ 0 , γ 1 , γ 2 , γ -2 } and s b : [k] → {γ 0 , γ 1 , γ 2 , γ -2 } u-agree on s if, (u1) for each i ∈ s -1 a (γ 0 ), s(i) = s b (i). Similarly, for each i ∈ s -1 b (γ 0 ), s(i) = s a (i), (u2) for each i ∈ s -1 (γ 1 ), either s a (i) = γ 0 or s b (i) = γ 0 , (u3) for each i ∈ [k] \ (s -1 a (γ 0 ) ∪ s -1 b (γ 0 )), if s(i) = γ 2 , then s a (i), s b (i) ∈ {γ 1 , γ 2 }, (u4) for each i ∈ [k]\(s -1 a (γ 0 )∪s -1 b (γ 0 )), if s(i) = γ -2 , then s a (i), s b (i) ∈ {γ 1 , γ -2 }.
)), in respectively, A Ga [s a ] and A G b [s b ]. The first condition tells that if F a (resp. F b ) does not intersect lab -1 G (i), then the intersection of F with lab -1 G (i) depends only on V (F b ) ∩ lab -1 G (i) (resp. V (F a ) ∩ lab -1 G (i))
, and so if V (F ) does not intersect lab -1 G (i), then F a and F b do not intersect lab -1 G (i). The second condition tells that

2 If J ⊂ [k]
is the set of labels Ga (or G b ), we can extend the domain of any function s :

J → {γ 0 , γ 1 , γ 2 , γ -2 } to [k] by setting s (i) = γ 0 for all i ∈ [k] \ J. if |F ∩ lab -1 G (i)| = 1, then either F ∩ lab -1 G (i) = F a ∩ lab -1 G (i) or F ∩ lab -1 G (i) = F b ∩ lab -1 G (i).
The other two conditions tell when F intersects both lab -1 Ga (i) and lab -1 G b (i). Notice that we may have s(i) set to γ -2 (or γ 2 ), while F a and F b each intersects lab -1 G (i) in exactly one vertex. We let tab G [s] := ac-reduce(rmc(A)) where,

A := sa,s b u-agree on s acjoin proj(s -1 (γ-2), tabG a [sa]) , proj(s -1 (γ-2), tabG b [s b ]) .
The weighted partitions (p, w) added in tab G [s] are all the weighted partitions that are joins of weighted partitions (p a , w a ) and (p b , w b ) from tab Ga [s a ] and tab G b [s b ], respectively. We need to do the projections before the join because we may have

s a (i) = s b (i) = γ 1 , s(i) = γ -2 ,
and there is j such that s(j) = γ 2 with j in the same block as i in both partitions p a and p b . If we do the projection after the acjoin operator, this latter will detect that acyclic(p a , p b ) does not hold, and won't construct (p, w), which indeed corresponds to a solution in

A G [s]. Lemma 4.5. Let G = G a ⊕ G b be a k-labeled graph. For each function s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }, the table tab G [s]ac-represents A G [s] assuming that tab Ga [s ] and tab G b [s ] ac-represent, respectively, A Ga [s ] and A G b [s ], for each s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }.

Proof. Since the used operators preserve ac-representation, it is enough to prove

that A G [s] = A if we let tab Gt [s ] = A Gt [s ], for every t ∈ {a, b} and s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }. Let (F, E 0 , (p, w)) be a solution in A G [s]. We claim that (p, w) ∈ A. For t ∈ {a, b}, let F t := G t [V (F ) ∩ V (G t )], E t 0 := {v 0 v ∈ E 0 : v ∈ V (F t )}
, and w t := w(V (F t )), and let

s t : [k] → {γ 0 , γ 1 , γ 2 , γ -2 } such that s t (i) :=      γ 0 if V (F t ) ∩ lab -1 Gt (i) = ∅, γ 1 if |V (F t ) ∩ lab -1 Gt (i)| = 1, s(i) if |V (F t ) ∩ lab -1 Gt (i)| ≥ 2.
It is straightforward to verify that s a and s b u-agree on s. Observe that, by definition, s -1 t (γ -2 ) ⊆ s -1 (γ -2 ) and s -1 t (γ 2 ) ⊆ s -1 (γ 2 ), for each t ∈ {a, b}. Let p a and p b be, respectively, partitions on s -1 a ({γ

1 , γ 2 }) ∪ {v 0 } and s -1 b ({γ 1 , γ 2 }) ∪ {v 0 } such that (F a , E a 0 , (p a , w a )) and (F b , E b 0 , (p b , w b )) are, respectively, candidate solutions in A Ga [s a ] and A G b [s b ].
We claim that (F a , E a 0 , (p a , w a )) is a solution in A Ga [s a ]. By definition of p a , s a , and of (F a , E a 0 ), Conditions ( 1) and ( 4) are clearly satisfied. Because

s -1 a (γ 2 ) ⊆ s -1 (γ 2 ), and F = F a ⊕ F b , we can conclude that CG(F a , E a 0 , s a ) is an induced subgraph of CG(F, E 0 , s), and because CG(F, E 0 , s) is acyclic, we can conclude that CG(F a , E a 0 , s a ) is acyclic, i.e., Condition (2) is satisfied. If a con- nected component C of CG(F a , E a 0 , s a ) does not intersect s -1 a ({γ 1 , γ 2 }) ∪ {v 0 }, then C is entirely contained in lab -1
Ga (s -1 a (γ -2 )). But, this yields a contradiction with (F, E 0 , (p, w)) satisfying Condition (3) because C is a connected component of CG(F, E 0 , s), and s -1 a (γ -2 ) ⊆ s -1 (γ -2 ). Therefore Condition (3) is also satisfied. We can thus conclude that

(F a , E a 0 , (p a , w a )) is a solution in A Ga [s a ]. Similarly, one can check that (F b , E b 0 , (p b , w b )) is a solution in A G b [s b ]. It remains to prove that (p, w) ∈ acjoin(proj(s -1 (γ-2), {(pa, wa)}), proj(s -1 (γ-2), {(p b , w b )})).
First, recall that each connected component of F is either a connected component of F a or of F b . Then, because (F, E 0 , (p, w)) satisfies Condition (3), we have that proj(s -1 (γ -2 ), {(p a , w a )})) = ∅, and similarly proj(s -1 (γ -2 ), {(p b , w b )})) = ∅. We deduce that p a := p a↓(s -1 (γ-2)) ∈ proj(s -1 (γ -2 ), {(p a , w a )}),

p b := p b↓(s -1 (γ-2)) ∈ proj(s -1 (γ -2 ), {(p b , w b )}).
Let p a := p a↑([k]\s -1 ({γ0,γ-2})) and p b := p b↑([k]\s -1 ({γ0,γ-2})) . We claim that acyclic(p 1 , p 2 ) holds. Assume towards a contradiction that it is not the case. We let ∼ a (resp. ∼ b ) be an equivalence relation on

[k] \ s -1 ({γ 0 , γ -2 }) ∪ {v 0 } where i ∼ a j (resp. i ∼ b j) if there is an i-vertex 3 and a j-vertex that are connected in CG(F a , E a 0 , s a ) (resp. CG(F b , E b 0 , s b ))
. By the graphical definition of acyclic, we can easily see that if acyclic(p a , p b ) does not hold, then there is a sequence i 0 , . . . , i 2r-1 of s -1 ({γ 1 , γ 2 })∪{v 0 } such that 4 , for all 0 ≤ α < r-1, we have i 2α ∼ b i 2α+1 and i 2α+1 ∼ a i 2α+2 . We can thus construct a cycle in CG(F, E 0 , s) from this sequence since V (F a ) ∩ V (F b ) = ∅, CG(F a , E a 0 , s a ) and CG(F b , E b 0 , s b ) are induced subgraphs of CG(F, E 0 , s), and all the vertices labeled with a label from s -1 (γ 2 ) are at distance at most two in CG(F, E 0 , s). This yields a contradiction as CG(F, E 0 , s) is acyclic by assumption. Therefore, acyclic(p 1 , p 2 ) holds.

Finally, p = p a p b because one easily checks that there is an i-vertex x connected to a j-vertex y in CG(F, E 0 , s) if and only if iRj where R is the transitive closure of (i ∼ a j or i ∼ b j). This follows from the fact that for every i ∈ [k] \ s -1 ({γ 0 , γ -2 }), either there is exactly one i-vertex in F or the i-vertices of F are all adjacent to v + i in CG(F, E 0 , s). In both cases, the i-vertices of F are in the same connected component of CG(F, E 0 , s). Since, the equivalence classes of R correspond to the blocks of p 1 p 2 , and w = w a + w b , we can conclude that

(p, w) ∈ acjoin(proj(s -1 (γ -2 ), {(p a , w a )}), proj(s -1 (γ -2 ), {(p b , w b )})).
We now prove that if (p, w) is added to tab G

F := (V (F 1 ) ∪ V (F 2 ), E(F 1 ) ∪ E(F 2 )) and E 0 := E a 0 ∪ E b 0 .
Because s a and s b u-agree on s, we clearly have that Condition (1) is satisfied.

Let ∼ a and ∼ b as defined above. Assume towards a contradiction that there exists a cycle C in CG(F, E 0 , s). Since both CG(F a , E a 0 , s a ) and CG(F b , E b 0 , s b ) are acyclic, C must be a cycle alternating between paths in CG(F a , E a 0 , s a ) and paths in CG(F b , E b 0 , s b ). One can easily check that this implies the existence of a sequence i 0 , . . . , i 2r-1 of s -1 ({γ 1 , γ 2 })∪{v 0 } such that 4 , for all 0 ≤ α < r-1, we have i 2α ∼ b i 2α+1 and i 2α+1 ∼ a i 2α+2 . Moreover, it is easy to infer, from this sequence and the graphical definition of acyclic, that acyclic p a↑V , p b↑V does not hold with

p a := p a↓(s -1 (γ-2)) , p b := p b↓(s -1 (γ-2)) and V = ([k] \ s -1 ({γ 0 , γ -2 })), contradicting the fact that (p, w) = acjoin(proj(s -1 (γ -2 ), {(p a , w a )}), proj(s -1 (γ -2 ), {(p b , w b )})).
Therefore, CG(F, E 0 , s) is acyclic and so Condition (2) is satisfied.

If we suppose that Condition (3) is not satisfied, then there is a connected component C of CG(F, E 0 , s) that does not intersect s

-1 ({γ 1 , γ 2 })∪{v 0 }, i.e., C is fully contained in lab -1 G (s -1 (γ -2 )). Since F = F a ⊕F b , C is either a connected component of F a or of F b . Suppose w.l.o.g. that C is a connected component of F a . Observe that C intersects lab -1 Ga (s -1 a ({γ 1 , γ 2 })) because (F a , E a 0 , (p a , w a )) is a solution in A Ga [s a ]. Moreover, C does not intersect lab -1 Ga (s -1 a (γ 2 )), otherwise C would inter- sect lab -1 G (s -1 (γ 2 )) since if s a (i) = γ 2 , then s(i) = γ 2 , for all i ∈ [k]. Thus C is a connected component of CG(F a , E a 0 , s a ) and b C := {i ∈ s -1 a (γ 1 ) : C∩lab -1 Ga (i) = ∅} is a block of p a because (F a , E a 0 , (p a , w a )) is a candidate solution in A Ga [s a ].
Thus, by definition of proj, we have proj(s -1 (γ -2 ), {(p a , w a )}) = ∅, which contradicts the fact that (p, w) = acjoin(proj(s -1 (γ -2 ), {(p a , w a )}), proj(s -1 (γ -2 ), {(p b , w b )})). So, Condition (3) is also satisfied. We deduce that Condition ( 4) is satisfied by observing that, for i, j ∈ s -1 ({γ 1 , γ 2 }) ∪ {v 0 }, there is an i-vertex connected to a j-vertex in CG(F, E 0 , s) if and only if iRj where R is the transitive closure of (i ∼ a j or i ∼ b j). This concludes the proof that (F,

E 0 , (p, w)) is a solution in A G [s].
Theorem 4.6. There is an algorithm that, given an n-vertex graph G and an irredundant k-expression of G, computes a minimum feedback vertex set in time

O(15 k • 2 (ω+1)•k • k O(1) • n).
Proof. We do a bottom-up traversal of the k-expression and at each step we update the tables as indicated above. The correctness of the algorithm follows from Lemmas 4.3-4.5. From the definition of A G [s], we conclude that the size of a maximum induced forest is the maximum over all s :

[k] → {γ 0 , γ 1 , γ 2 , γ -2 } with s -1 (γ 2 ) = ∅, of max{w : ({{v 0 } ∪ s -1 (γ 1 )}}, w) ∈ tab G [s]} because tab G [s] ac-represents A G [s] for all s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }.
Let us discuss the time complexity now. If G = add i,j (H) or G = ren i→j (H), and s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }, then we update tab G [s] from a constant number of tables from tab H , each identified in constant time from s. Since each table contains at most 2 k-1 • k entries, we call the function ac-reduce with a set of size at most O(2 k-1 • k) as input. By Theorem 3.8, we can thus update tab G in time 1) . Therefore, we can compute the tables from tab G in time 1) . Now, observe that there are at most 15 k functions s, s a , s b : [k] → {γ 0 , γ 1 , γ 2 , γ -2 } such that s a and s b u-agree on s. Indeed, for all i ∈ [k], if s a and s b u-agree on s, then the tuple (s a (i), s b (i), s(i)) can take up to 15 values. See Table 1 for all the possible values.

2 ω•k • k O(1) . If G = G a ⊕ G b , then we claim that the tables from tab G are computable in time O(15 k • 2 (ω+1)•k • k O(1) ). For s : [k] → {γ 0 , γ 1 , γ 2 , γ -2 }, we let A[s] := sa,s b u-agree on s acjoin proj(s -1 (γ-2), tabG a [sa]) , proj(s -1 (γ-2), tabG b [s b ]) .

By Theorem 3.8, computing tab G [s] := ac-reduce(rmc(A[s])) can be done in time

|A[s]| • 2 (ω-1)•k • k O(
s:[k]→{γ0,γ1,γ2,γ-2} |A[s]| • 2 (ω-1)•k • k O(
s b (i) = γ 0 s b (i) = γ 1 s b (i) = γ 2 s b (i) = γ -2 s a (i) = γ 0 γ 0 γ 1 γ 2 γ -2 s a (i) = γ 1 γ 1 γ 2 , γ -2 γ 2 γ -2 s a (i) = γ 2 γ 2 γ 2 γ 2 forbidden s a (i) = γ -2 γ -2 γ -2 forbidden γ -2
Table 1. Possibles values of s(i) depending on the value of s a (i) and s b (i) when s a and s b u-agree on s, there are 15 possible values for the tuple (s a (i), s b (i), s(i)).

Because each table of tab Ga and tab

G b contains at most 2 k-1 • k values, we have |acjoin proj(s -1 (γ -2 ), tab Ga [s a ]) , proj(s -1 (γ -2 ), tab G b [s b ]) | ≤ 2 2k-2 • k 2 . It follows that s:[k]→{γ0,γ1,γ2,γ-2} |A[s]| ≤ 15 k • 2 2k • k 2 . Hence, we can conclude that the tables from tab G can be computed in time O(15 k • 2 (ω+1)•k • k O(1) ).
Because the size of a k-expression is O(n • k 2 ), we can conclude that a minimum feedback vertex set can be computed in the given time.

Connected (Co-)(σ, ρ)-Dominating Sets

We will show here how to use the operators defined in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] in order to obtain a 2 O(d•k) • n time algorithm for computing a minimum or a maximum connected (σ, ρ)-dominating set, given a k-expression, with d a constant that depends only on (σ, ρ). We deduce from this algorithm a 2 O(k) • n O (1) time algorithm for computing a minimum node-weighted Steiner tree, and a 2 O(d•k) • n O (1) time algorithm for computing a maximum (or minimum) connected co-(σ, ρ)-dominating set.

We let opt ∈ {min, max}, i.e., we are interested in computing a connected (σ, ρ)dominating set of maximum (or minimum) weight if opt = max (or opt = min). Let us first give some definitions. As defined in Section 3, rmc works only for the case opt = max, we redefine it as follows in order to take into account minimization problems.

rmc(A) := {(p, w) ∈ A : ∀(p, w ) ∈ A, opt(w, w ) = w}. Join. Let V be a finite set. For A ⊆ Π(V ) × N and B ⊆ Π(V ) × N, we define join(A, B) ⊆ Π(V ∪ V ) × N as join(A, B) := {(p ↑V q ↑V , w 1 + w 2 ) : (p, w 1 ) ∈ A, (q, w 2 ) ∈ B}.
This operator is the one from [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF]. It is used mainly to construct partial solutions of G ⊕ H from partial solutions of G and H.

The following proposition assumes that log(|A|) ≤ |V | O (1) for each A ⊆ Π(V )×N (this can be established by applying the operator rmc). The following is the same as Definition 3.5, but does not require acyclicity.

Definition 5.2 ([2]

). For A ⊆ Π(V ) × N, with V a finite set, and q ∈ Π(V ), let opt(A, q) := opt{w : (p, w) ∈ A, p q = {V }}.

A set of weighted partitions B ⊆ Π(V ) × N represents A if for each q ∈ Π(V ), it holds that opt(A, q) = opt(B, q).
Let Z and V be two finite sets. A function f : 2

Π(V )×N × Z → 2 Π(V )×N is said to preserve representation if for each A, B ⊆ Π(V ) × N and z ∈ Z, it holds that f (B, z) represents f (A, z) whenever B represents A. Lemma 5.3 ([2]
). The operators rmc, proj and join preserve representation.

Theorem 5.4 ([2]

). There exists an algorithm reduce that, given a set of weighted partitions

A ⊆ Π(V ) × N, outputs in time |A| • 2 (ω-1)|V | • |V | O(1) a subset B of A that represents A, and such that |B| ≤ 2 |V |-1 .
We use the following function to upper bound the amount of information we need to store in our dynamic programming tables concerning the (σ, ρ)-domination. For every non-empty finite or co-finite subset µ ⊆ N, we define d(µ) such as

d(µ) := 0 if µ = N, 1 + min(max(µ), max(N \ µ)) otherwise.
For example, d(N + ) = 1 and for every c ∈ N, we have d({0, . . . , c}) = c + 1.

The definition of d is motivated by the following observation which is due to the fact that, for all µ ⊆ N, if d(µ) ∈ µ, then µ is co-finite and contains N\{1, . . . , d(µ)}. Let us describe with a concrete example the information we need concerning the (σ, ρ)-domination. We say that a set

D ⊆ V (G) is a 2-dominating set if every vertex in V (G) has at least 2 neighbors in D. It is worth noticing that a 2-dominating set is an (N \ {0, 1}, N \ {0, 1})-dominating set and d(N \ {0, 1}) = 2. Let H be a k-labeled graph used in an irredundant k-expression of a graph G. Assuming D H ⊆ V (H) is a subset of a 2-dominating set D of G, we would like to characterize the sets Y ⊆ V (G) \ V (H) such that D ∪ Y is a 2-dominating set of G. One first observes that D H is not necessarily a 2-dominating set of H, and D \ D H also is not necessarily a 2-dominating set of G[V (G) \ V (H)].
Since we want to 2-dominate V (H), we need to know for each vertex x in V (H) how many neighbors it needs in addition to be 2-dominated by D H . For doing so, we associate D H with a sequence R = (r 1 , . . . , r k ) over {0, 1, 2} k such that, for each i ∈ [k], every vertex in lab -1 H (i) has at least 2 -r i neighbors in D H . For example, if r i = 1, then every i-vertex has at least one neighbor in D H . Notice that D H can be associated with several such sequences. This sequence is enough to characterize what we need to 2-dominate V (H) since the vertices with the same label in H have the same neighbors in the graph (V (G), E(G) \ E(H)) and each vertex needs at most 2 additional neighbors to be 2-dominated.

In order to update the sequence R = (r 1 , . . . , r k ) associated with a set D H , we associate with D H another sequence R = (r 1 , . . . , r k ) over {0, 1, 2} k such that r i corresponds to the minimum between 2 and the number of i-vertices in D H , for each i ∈ [k]. This way, when we apply an operation add i,j on H, we know that every i-vertex has at least 2 -r i + r j neighbors in D H in the graph add i,j (H). For example, if r j = 1 and every i-vertex has at least one neighbor in H that belongs D H , then we know that every i-vertex is 2-dominated by D H in the graph add i,j (H).

Let (σ, ρ) be a fixed pair of non-empty finite or co-finite subsets of N. Let's first show how to compute an optimum connected (σ, ρ)-dominating set. We consider node-weighted Steiner tree and connected co-(σ, ρ)-dominating set at the end of the section. Let d := max{d(σ), d(ρ)}.

The following definitions formalize the intuitions we give for 2-dominating set to the (σ, ρ)-domination. Definition 5.6 (Certificate graph of a solution). Let G be a k-labeled graph, and

R := (r 1 , . . . , r k ) ∈ {0, . . . , d} k . Let V + := {v 1 1 , . . . , v 1 d , v 2 1 , . . . , v 2 d , . . . , v k 1 , . . . , v k d } be a set disjoint from V (G) and of size d • k. Let V + (R ) := V + 1 (R ) ∪ • • • ∪ V + k (R ) with V + i (R ) := ∅ if r i = 0, {v i 1 , . . . , v i r i } otherwise.
The certificate graph of G with respect to R , denoted by CG(G, R ), is the graph The motivation behind these two sequences is that for computing an optimum (σ, ρ)-dominating set, it is enough to compute, for any k labeled graph H used in an irredundant k-expression of a graph G and for each R, R ∈ {0, . . . , d} k , the optimum weight of a set

(V (G) ∪ V + (R ), E(G) ∪ E + 1 ∪ • • • ∪ E + k ) with E + i = {{v, v i t } : v i t ∈ V + i (R ) ∧ v ∈ lab -1 G (i)}. It is worth noticing that E + i is empty if lab -1 G (i) = ∅ or V + i (R ) = ∅. Definition 5.7. Let G be a k-labeled graph. For each D ⊆ V (G) and i ∈ [k], let r d i,G (
D ⊆ V (H) such that • r H (D) = R, • D ∪ V + (R ) (σ, ρ)-dominates V (H) in the graph CG(H, R ).
It is worth noticing that the sequences r d H (D) and R are similar to the notion of d-neighbor equivalence introduced in [START_REF] Bui-Xuan | Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems[END_REF].

We can assume w.l.o.g. that d = 0, that is σ = N or ρ = N. Indeed, if σ = ρ = N, then the problem of finding a minimum (or maximum) (co-)connected (σ, ρ)dominating set is trivial. For computing an optimum connected (σ, ρ)-dominating set, we will as in Section 4 keep partitions of a subset of labels corresponding to the connected components of the sets D (that are candidates for the (σ, ρ)domination). As d = 0, we know through r H (D) the label classes intersected by D. Moreover, we know through R = (r 1 , . . . , r k ) whether the i-vertices in such a D will have a neighbor in any extension D of D into a (σ, ρ)-dominating set. It is enough to keep the partition of the labels i with r i,H (D) = 0 and r i = 0 that corresponds to the equivalence classes of the equivalence relation ∼ on {i ∈ [k]\r i = 0 and r i = 0} where i ∼ j if and only if an i-vertex is connected to a j-vertex in

CG(G, R )[D ∪ V + ].
We use the following definition to simplify the notations. We are now ready to define the sets of weighted partitions which representative sets we manipulate in our dynamic programming tables.

r d G (D) = R, (2) D ∪ V + (R ) (σ, ρ)-dominates V (G) in CG(G, R ), (3) if active(R, R ) = ∅, then G[D] is connected, otherwise for each connected component C of G[D], we have C ∩ lab -1 G (active(R, R )) = ∅, (4) p = active(R, R )/ ∼ where i ∼ j if and only if an i-vertex is connected to a j-vertex in CG(G, R )[D ∪ V + (R )].
Conditions ( 1) and (2) guarantee that (p, w) corresponds to a set D that is coherent with R and R . Condition [START_REF] Bui-Xuan | Feedback vertex set on graphs of low clique-width[END_REF] guarantees that each partial solution can be extended into a connected graph. Contrary to Section 4, the set of labels expected to play a role in the connectivity (i.e. active(R, R )) can be empty. In this case, we have to make sure that the weighted partitions represent a connected solution. It is worth mentioning that G[∅], i.e. the empty graph, is considered as a connected graph. Observe that for each (p, w) ∈ D G [R, R ], the partition p has the same meaning as in Section 4. It is worth noticing that ∼ is an equivalence relation because if i ∈ active(R, R ), then all the vertices in lab It is straightforward to check that the weight of an optimum solution is the optimum over all R ∈ {0, . . . , d} k of opt{w : (∅, w)

∈ D G [R, {0} k ]} for a k-labeled graph G.
Analogously to Section 4 our dynamic programming algorithm will store a subset of

D G [R, R ] of size 2 k-1 that represents D G [R, R ].
Recall that we suppose that any graph is given with an irredundant k-expression.

Computing tab G for G = 1(x). For (r 1 ) ∈ {0, . . . , d}, (r 1 ) ∈ {0, . . . , d}, let tabG[(r1), (r 1 )] :=

     {(∅, 0)} if r1 = 0 and r 1 ∈ ρ, {({{1}}, w(x))} if r1 = 1 and r 1 ∈ σ, ∅ otherwise.
Since there is only one vertex in G labeled 1, D G [(r 1 ), (r 1 )] is empty whenever r 1 / ∈ {0, 1}. Also, the possible solutions are either to put x in the solution (r 1 = 1) or to discard it (r 1 = 0); in both cases we should check that x is (σ, ρ)-dominated by V + 1 (R ). We deduce then that tab G [(r 1 ), (r 1 )] = D G [(r 1 ), (r 1 )]. Computing tab G for G = ren i→j (H). We can suppose that H is k-labeled and that i = k. Let R = (r 1 , . . . , r k-1 ), R = (r 1 , . . . , r k-1 ) ∈ {0, . . . , d} k-1 .

To compute tab G [R, R ], we define S, the set of tuples coherent with respect to R and Condition (1), as follows It is worth noticing that we always have (r 1 , . . . , r k-1 , 0) ∈ S. Moreover, if r j = 0, then S = {(r 1 , . . . , r k-1 , 0)}. We define also S = (s 1 , . . . , s k ) ∈ {0, . . . , d} k with s k = r j and s = r for all ∈ [k -1]. Notice that S is the only tuple compatible with R and Condition (2) since for every v ∈ lab -1 G (j), the number of vertices in V + (R ) adjacent to v in CG(G, R ) is the same as the number of vertices in V + (S ) adjacent to v in CG(H, S ). (a) If r j = 0 or r j = 0, then we let

tab G [R, R ] := reduce rmc S∈S tab H [S, S ]
.

In this case, the vertices in lab -1 G (j) are not expected to play a role in the future as either we expect no neighbors for them in the future or they are not intersected by the partial solutions. Computing tab G for G = add i,j (H). We can suppose that H is k-labeled. Let R = (r 1 , . . . , r k ) ∈ {0, . . . , d} k , R = (r 1 , . . . , r k ) ∈ {0, . . . , d} k .

Let S := (s 1 , . . . , s k ) ∈ {0, . . . , d} k such that s i := min(d, r i + r j ), s j := min(d, r j + r i ), and s = r for all ∈ [k] \ {i, j}. It is easy to see that S is the only tuple compatible with R and Condition (2).

G [R, R ] represents D G [R, R ] because the function f : 2 Π(V )×N → 2 {∅}×N with f (A) := {(∅, w) : (p, w) ∈ A} preserves representation. (b) If r i = 0 or r j = 0, we let tab G [R, R ] := tab H [R, S ].
We just copy all the solutions not intersecting lab -1 G (i) or lab -1 G (j). In this case, the connectivity of the solutions is not affected by the add i,j operation. (c) Otherwise, we let tab G [R, R ] := rmc(A), where

A := proj({t ∈ {i, j} : r t = 0}, join(tab H [R, S ], {({{i, j}}, 0)})).
In this last case, we have i, j ∈ active(R, S ). We put in tab G [R, R ], the weighted partitions of tab H [R, S ] after merging the blocks containing i and j, and removing i or j if, respectively, r i = 0 and r j = 0, i.e., if they don't belong, respectively, to active(R, R ).

It is worth noticing that if |tab H [R, S ]| ≤ 2 k-1 , then we have |tab G [R, S ]| ≤ 2 k-1 .
Thus, we do not have to use the function reduce to compute tab G . Lemma 5.11. Let G = add i,j (H) be a k-labeled graph. For all tuples R =

(r 1 , . . . , r k ), R = (r 1 , . . . , r k ) ∈ {0, . . . , d} k , the table tab G [R, R ] is a representative set of D G [R, R ] assuming that tab H [R, S ] is a representative set of D H [R, S ].
(v) = lab H (v) for all v ∈ V (G). We claim that Condition (2) is satisfied, that is D ∪ V + (S ) (σ, ρ) dominates V (H) in CG(H, S ). It is quite easy to see that D ∪ V + (S ) (σ, ρ) dominates V (H) \ lab -1 H ({i, j}). Let v ∈ lab -1 H (i).
We claim that v is (σ, ρ) dominated by D ∪ V + (S ). Because we consider only irredundant k-expressions, there is no edge between an i-vertex and a j-vertex in H. Therefore, we have

|N G (v) ∩ D| = |N H (v) ∩ D| + |D ∩ lab -1 G (j)|. Since D ∪ V + (R ) (σ, ρ)-dominates V (G), if v ∈ D, then |N G (v) ∩ D| + r i ∈ σ, otherwise, |N G (v) ∩ D| + r i ∈ ρ. By Fact 5.5, we conclude that min(d, |N H (v)∩D|+|D ∩lab -1 G (j)|+r i ) belongs to σ if v ∈ D, otherwise it belongs to ρ. As min(d, r i + |D ∩ lab -1 G (j)|) = min(d, r i + r j ) = s i , we deduce that D ∪ V + (S ) (σ, ρ) dominates v. Thus, every i-vertex is (σ, ρ)- dominated by D ∪ V + (S ) in CG(H, S )
. Symmetrically, we deduce that every j-vertex is (σ, ρ)-dominated by D ∪ V + (S ) in CG(H, S ). Hence, Condition (2) is satisfied.

In order to prove that Condition (3) is satisfied, we distinguish the following cases. First, suppose that active(R, R ) = ∅. By Condition (3), G[D] is connected. As G = add i,j (H), the graph H[D] is obtained from G[D] by removing all edges between the i-vertices and the j-vertices. We deduce that either H[D] is connected (if r i = 0 or r j = 0), or that every connected component of H[D] contains at least one vertex whose label is i or j (otherwise G[D] would not be connected). In both cases, Condition (3) is satisfied.

Assume now that active(R, R ) = ∅. If r i = 0 (resp. r j = 0), then, by definition of S , we have s j = r j (resp. s i = r i ). Therefore, if r i = 0 or r j = 0, then we have active(R, R ) = active(R, S ), and Condition (3) is trivially satisfied. Otherwise, if r i = 0 and r j = 0, then, by definition of S , we have s i = 0, s j = 0, and thus i, j ∈ active(R, S ). In this case, we conclude that Condition 1) is satisfied. We deduce that Condition (2) is satisfied from the definition of S and the previous arguments. We claim that Condition (3) is satisfied. Suppose first that R = {0} k . Then either S = {0} k or {i, j} = active(R, S ). Indeed, we have active(R, S ) ⊆ {i, j}. Now, i ∈ active(R, S ) if and only if r i = 0 and s i = 0, and then, by definition of S , s j = r i = 0 and s i = r j = 0. Thus, i ∈ active(R, S ) if and only if j ∈ active(R, S ). Therefore, we conclude that either H[D] is connected or every connected component C of H[D] contains at least a vertex whose label is i or j. As G[D] is obtained from H[D] by adding all the edges between the i-vertices and the j-vertices, we conclude that, in both cases, G[D] is connected.

It remains to prove that every weighted partition added to tab

G [R, R ] belongs to D G [R, R ]. Let (p, w) be a weighted partition added to tab G [R, R ] from (p , w) ∈ tab H [R, S ] and let D ⊆ V (H) such that (D, (p , w)) is a solution in D H [R, S ]. We claim that (D, (p, w)) is a solution in D G [R, R ]. Obviously, Condition (
Otherwise, if R = {0} k , then every connected component of H[D] contains at least one vertex whose label is in active(R, S ). If r i = 0 or r j = 0, then we are done because active(R, R ) = active(R, S ) by definition of S . Suppose now that r i = 0 and r j = 0. In this case, we have i, j ∈ active(R, S ) from the definition of S . Assume towards a contradiction that there exists a connected

component C in G[D] such that C does not intersect lab -1 G (active(R, R )). Notice that C intersects lab -1 G (active(R, S )) because C is a union of connected components of H[D].
As active(R, S ) \ active(R, R ) ⊆ {i, j}, we deduce that C contains at least one vertex whose label is i or j. Since the i-vertices and the j-vertices of D are in the same connected component of G

[D], we have lab -1 G ({i, j}) ∩ D ⊆ C. Therefore, we conclude that active(R, S ) \ active(R, R ) = {i, j}. It follows, that all the connected components of H[D] that intersect lab -1 G ({i, j}) does not intersect lab -1
G (active(R, S ) \ {i, j}) because they are contained in C. We can conclude that {i, j} is a block of p := p {{i, j}} ↑active(R,S ) . Hence, we have proj({t ∈ {i, j} : r t = 0}, {(p , w)}) = ∅ because {t ∈ {i, j} : r t = 0} = {i, j}. This contradicts the fact that (p, w) is obtained from (p , w ). Thus, Condition (3) is satisfied.

We deduce from the previous observations concerning Condition (4) that this condition is also satisfied. Thus, every solution (p, w)

added to tab G [R, R ] belongs to D G [R, R ].
Computing tab G for G = G a ⊕ G b . We can suppose w.l.o.g. that G a and G b are k-labeled 5 . Let R = (r 1 , . . . , r k ), R = (r 1 , . . . , r k ) ∈ {0, . . . , d} k . 5 For example, if the set of labels of Ga (or G b ) is [k] \ 1, then we can extend any tuples R = (r 2 , . . . , r k ), R = (r 2 , . . . , r k ) ∈ {0, . . . , d} k-1 , to {0, . . . , d} k by adding r 1 = 0 to R and r 1 = * to R with * a special value considered as equal to all the integers in {0, . . . , d}.

Since 2 2(k-1) • 2 (ω-1)•k ≤ 2 (ω+1)•k , we conclude from Observations (1)-( 2) that we can compute the tables tab G [R, R ], for every R ∈ {1, . . . , d} k , in time (d + 1) 2k • 2 (ω+1)•k • k O (1) .

Hence, we can update tab G in time (d + 1) 3k • 2 (ω+1)•k • k O (1) .

Hence, in the worst case, the tables of tab G takes (d + 1) 3k • 2 (ω+1)•k • k O (1) time to be computed. Because the size of a k-expression is O(n • k 2 ), we can conclude that a maximum (or minimum) (σ, ρ)-dominating set can be computed in the given time.

As a consequence of Theorem 5.13, we have the following corollary.

Corollary 5.14. There is an algorithm that, given an n-vertex graph G, a subset K ⊆ V (G) and an irredundant k-expression of G, computes a minimum nodeweighted Steiner tree for (G, K) in time 2 (ω+4)•k • k O (1) • n.

Proof. We can assume w.l.o.g. that |K| ≥ 2. We can reduce the problem Nodeweighted Steiner Tree to a variant of (σ, ρ)-Dominating Set where σ = N + and ρ = N. This variant requires K to be included in the (σ, ρ)-dominating set. We can add this constraint, by modifying how we compute the table tab G , when G = 1(x) and x ∈ K. For (r 1 ), (r 1 ) ∈ {0, 1}, we let It is straightforward to check that this modification implements this constraint and our algorithm with this modification computes a minimum node-weighted Steiner tree. The running time follows from the running time of Theorem 5.13 with d = 1.

More modifications are needed in order to compute a maximum (or minimum) connected co-(σ, ρ)-dominating set.

Corollary 5.15. There is an algorithm that, given an n-vertex graph G and an irredundant k-expression of G, computes a maximum (or minimum) co-(σ, ρ)-dominating set in time (d + 2) 3k • 2 (ω+1)•k • k O (1) • n.

Proof. First, we need to modify the definition of the tables D G . Let H be a k-labeled graph, R, R ∈ {0, . . . , d} k , and R, R ∈ {0, 1} k . The entries of D H [R, R , R, R ] are all the weighted partitions (p, w) ∈ Π(active(R, R )) × N such that there exists a set X ⊆ V (G) so that w = w(X) and

(1)

r d H (V (H) \ X) = R and r 1 H (X) = R, (2) (V (H) \ X) ∪ V + (R ) (σ, ρ)-dominates V (H) in CG(H, R ), (3) if active(R, R ) = ∅, then H[X] is connected, otherwise every connected component of H[X] intersects lab -1 H (active(R, R )), (4
) p = active(R, R )/ ∼ where i ∼ j if and only if an i-vertex is connected to a j-vertex in CG(H, R )[X ∪ V + (R )].

As a solution is a set X such that V (G) \ X is a (σ, ρ)-dominating set and G[X] is a connected graph, we need information about X ∩V (H) and (V (H)\X). Intuitively, R, R are the information we need to guarantee the (σ, ρ)-domination, and R, R are the information we need to guarantee the connectedness. In particular, R specifies which label classes are intersected and R tells which label classes are expected to have at least one neighbor in the future. These modifications imply in particular to change the notion of R-compatibility. For each t ∈ {a, b, c}, let R t = (r t 1 , . . . , r t k ) ∈ {0, . . . , d} k , and R t = (r t 1 , . . . , r t k ) ∈ {0, 1} k , we say that (R a , R a , R b , R b ) is (R c , R c )-compatible if for all i ∈ [k], we have r c i = min(d, r a i + r b i ) and r c i = min(1, r a i + r b i ). It is now an exercise to modify the algorithm of Theorem 5.13 in order to update the tables tab H through the different clique-width operations. The weight of an optimum solution corresponds to the optimum over all R ∈ {0, . . . , d} k , R ∈ {0, 1} k of opt{w : (∅, w)

∈ tab G [R, {0} k , R, {0} k ]}, since tab G [R, {0} k , R, {0} k ] represents D G [R, {0} k , R, {0} k ].
Let us discuss the time complexity now. Let H be a k-labeled graph that is used in the k-expression of G. First, observe that we do not need to compute tab H [R, R , R, R ] for all R, R ∈ {0, . . . , d} k , and R, R ∈ {0, 1} k . Indeed, for all X ⊆ V (H) and i ∈ [k], if we have r d i,H (V (H) \ X) < d, then

r 1 i,H (X) = 0 if |lab -1 H (i)| = r d i,H (V (H) \ X), 1 otherwise.
Hence, we deduce that there are at most (d+2) k pairs (R, R) ∈ {0, . . . , d} k ×{0, 1} k such that R = r d H (V (H) \ X) and R = r 1 H (X). Indeed, whenever r d i,H (V (H) \ X) < d, there is only one possible value for r 1 i,H (X), and when r d i,H (V (H) \ X) = d, there are at most 2 possible values for r 1 i,H (X). With the same arguments used to prove the running time of Theorem 5.13, one easily deduces that there are at most (d+2

) 2k tuples (R a , R a , R b , R b , R c , R c ) such that (R a , R a , R b , R b ) is (R c , R c )-compatible.
Moreover, it is sufficient to consider (d + 2) k pairs (R , R ) ∈ {0, . . . , d} k × {0, 1} k when we update tab H . For every i ∈ [k], we let c i H := |N G (lab -1 H (i)) \ N H (lab -1 H (i))|. Notice that for every vertex v ∈ lab -1

H (i), we have |N G (v)| = |N H (v)|+c i
H . Informally, we cannot expect more than c i H neighbors in the future for the i-vertices of H. Hence, it is enough to consider the pairs (R , R ) ∈ {0, . . . , d} k × {0, 1} k , with R = (r 1 , . . . , r k ) and R = (r 1 , . . . , r k ), such that for all i ∈ [k], if r i < d, then

r i = 0 if r i ≥ c H i , 1 otherwise.
That is, for every i ∈ [k], if r i < d, then there is one possible value for r i because if we expect r i < d neighbors for the i-vertices in V (H) \ X, then we must expect min(0, c i H -r i ) neighbors for the i-vertices in X. If r i = d, then there are no restrictions on the value of r i . Thus, the pairs (r i , r i ) can take up to (d + 2) values. We conclude that there are at most (d + 2) k pairs (R , R ) ∈ {0, . . . , d} k × {0, 1} k worth to looking at. With these observations and the arguments used in the running time proof of Theorem 5.13, we conclude that we can compute a maximum (or minimum) co-(σ, ρ)-dominating set in the given time.

Concluding Remarks

We combine the techniques introduced in [START_REF] Bui-Xuan | Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems[END_REF] and the rank-based approach from [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] to obtain 2 O(k) • n time algorithms for several connectivity constraints problems such as Connected Dominating Set, Node-Weighted Steiner Tree, Feedback Vertex Set, Connected Vertex Cover, etc. While we did not consider connectivity constraints on locally vertex partitioning problems [START_REF] Bui-Xuan | Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems[END_REF], it seems clear that we can adapt our algorithms from the paper to consider such connectivity constraints: if the solution is {D 1 , . . . , D q }, each block D i is connected or a proper subset of the blocks form a connected graph. We did not consider counting versions and it would be interesting to know if we can adapt the approach in [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF] based on the determinant to the clique-width.

In [START_REF] Fedor | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF] Fomin et al. use fast computation of representative sets in matroids to provide deterministic 2 O(k) • n O (1) time algorithms parameterized by tree-width for many connectivity problems. Is this approach also generalizable to clique-width ?

The main drawback of clique-width is that, for fixed k, there is no known FPT polynomial time algorithm that produces a k-expression, that even approximates within a constant factor the clique-width of the given graph. We can avoid this major open question, by using other parameters as powerful as clique-width. Oum and Seymour introduced the notion of rank-width and its associated rank-decomposition [START_REF] Oum | Approximating clique-width and branch-width[END_REF] such that rank-width(G) ≤ clique-width(G) ≤ 2 rank-width(G)+1 -1. Furthermore there is a 2 O(k) • n 3 time algorithm for computing it [START_REF] Hliněný | Finding branch-decompositions and rank-decompositions[END_REF][START_REF] Oum | Approximating rank-width and clique-width quickly[END_REF]. If we use our approach with a rank-decomposition, the number of twin-classes is bounded by 2 k , and so we will get a 2 2 O(k) • n O(1) time algorithm. We can circle it and obtain 2 O(k 2 ) • n O (1) as done for example in [START_REF] Ganian | On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width[END_REF] for Feedback Vertex Set by using Myhill-Nerode congruences.

In [START_REF] Bergougnoux | Rank based approach on graphs with structured neighborhood[END_REF], the authors adapted the rank-based approach to the notion of d-neighbor equivalence from [START_REF] Bui-Xuan | Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems[END_REF]. They deduce, in particular, 2 O(k) • n O(1) , 2 O(k•log(k)) • n O(1) , and 2 O(k 2 ) • n O(1) time algorithms parameterized respectively by clique-width, Qrank-width (a variant of rank-width [START_REF] Oum | Faster algorithms for vertex partitioning problems parameterized by clique-width[END_REF]), and rank-width for all the problems considered in this paper. The results in [START_REF] Bergougnoux | Rank based approach on graphs with structured neighborhood[END_REF] generalize, simplify, and unify several results including [START_REF] Hans | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF][START_REF] Ganian | On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width[END_REF] and those from this paper. However, for each considered problem in this article, the algorithms parameterized by clique-width from [START_REF] Bergougnoux | Rank based approach on graphs with structured neighborhood[END_REF] have a worse running time than the algorithms from this paper.

We recall that, it is still open whether we can obtain a 2 O(k) •n O (1) time algorithm parameterized by rank-with (or Q-rank-width) to solve the problems considered in this paper, or more basic problems such as Independent Set or Dominating Set.

Figure 1 .

 1 Figure 1. Examples of Connected (Co-)(σ, ρ)-Dominating Set problems, N + := N \ {0}.

Proposition 3 . 4 (

 34 Folklore). The operator acjoin can be performed in time|A| • |B| • |V ∪ V | O(1) and the size of its output is upper-bounded by |A| • |B|. The operators rmc and proj can be performed in time |A| • |V | O(1) , and the sizes of their outputs are upper-bounded by |A|.

i

  and to the j-vertex in X, thus CG(X, ∅, s) contains a cycle of length 4. (c) If s(i) = s(j) = γ -2 , then we let tab G [s] = ∅. Similarly to Case (b), we have A G [s] = ∅ because every vertex set with two i-vertices and two j-vertices induce a cycle of length 4 in G. (d) Otherwise, we let tab G [s] := rmc(A)) with

  we are in Cases (b)-(c), then we are done since we clearly have A G [s] = ∅. Since the used operators preserve ac-representation, it is enough to prove that in Case (a), we have A G [s] = A H [s], and in Case (d), we have A G [s] = A if we let tab H [s H ] = A H [s H ]. If we are in Case (a), then we are done because one easily checks that (F, E 0 , (p, w)) is a solution in A H [s] if and only if (F, E 0 , (p, w)) is a solution in A G [s], i.e., we have A H [s] = A G [s].

  The functions s a and s b inform about the indices to look at tab Ga and tab G b in order to construct tab G [s]. Let (F, E 0 , (p, w)) be a solution in A G [s], and assume that it is constructed from solutions (F a , E 0 a , (p a , w a )) and (F b , E 0 b , (p b , w b

  [s] from (p a , w a ) ∈ A Ga [s a ] and (p b , w b ) ∈ A G b [s b ], then there exists a pair (F, E 0 ) such that (F, E 0 , (p, w)) is a solution in A G [s]. Let (F a , E a 0 ) and (F b , E b 0 ) such that (F a , E a 0 , (p a , w a )) and (F b , E b 0 , (p b , w b )) are solutions in, respectively, A Ga [s a ] and A G b [s b ] with s a and s b u-agreeing on s. We claim that (F, E 0 , (p, w)) is a solution in A G [s] with

Proposition 5 . 1 (

 51 Folklore). The operator join can be performed in time |A| • |B| • |V ∪ V | O(1) and the size of its output is upper-bounded by |A| • |B|.

Fact 5 . 5 .

 55 For every a, b ∈ N and µ a finite or co-finite subset of N, we have a+b ∈ µ if and only if min(d, a + b) ∈ µ.

  D) := min(d, |lab -1 G (i) ∩ D|) and let r d G (D) := (r d 1,G (D), . . . , r d k,G (D)). The sequence r d G (D) describes how each label class is intersected by D up to d vertices. Moreover, notice that |{r d G (D) : D ⊆ V (G)}| ≤ |{0, . . . , d} k | ≤ (d + 1) k .

Definition 5 . 8 .

 58 For R = (r 1 , . . . , r k ), R = (r 1 , . . . , r k ) ∈ {0, . . . , d} k , we define active(R, R ) = {i ∈ [k] : r i = 0 and r i = 0}.

Definition 5 . 9 (

 59 Weighted partitions in D G [R, R ]). Let G be a k-labeled graph, and R, R ∈ {0, . . . , d} k . The entries of D G [R, R ] are all the weighted partitions (p, w) ∈ Π(active(R, R )) × N so that there exists a set D ⊆ V (G) such that w(D) = w, and (1)

- 1 G

 1 (i) are connected in CG(G, R ) through the vertex in V + i (R ). In fact, the relation ∼ is equivalent to the transitive closure of the relation where i j if there exists an i-vertex and a j-vertex in the same connected component of G[D].In the sequel, we call a pair (D, (p,w(D))) a candidate solution in D G [R, R ] if p = active(R, R )/ ∼ where i ∼ j if and only if an i-vertex is connected to a j-vertex in CG(G, R )[D ∪ V + (R )].If in addition Conditions (1)-(3) are satisfied, we call (D, (p, w(D))) a solution in D G [R, R ].

S

  := {(s1, . . . , s k ) ∈ {0, . . . , d} k : rj = min(d, s k + sj) and ∀ ∈ [k] \ {i, j}, s = r }.

  (b) Otherwise, we let tab G [R, R ] := reduce(rmc(A)) with A := proj {k}, S∈S join(tab H [S, S ], {({{j, k}}, 0)}) .Intuitively, we put in tab G [R, R ] all the weighted partitions (p, w) from the tables tab H [S, S ] with S ∈ S, after merging the blocks in p containing k and j, and removing k from the resulting partition.Lemma 5.10. Let G = ren k→j (H) with H a k-labeled graph. For all R = (r 1 , . . . , r k-1 ), R = (r 1 , . . . , r k-1 ) ∈ {0, . . . , d} k-1 , the table tab G [R, R ] is a representative set of D G [R, R ] assuming that tab H [S, S ]is a representative set of D H [S, S ] for all S ∈ {0, . . . , d} k . Proof. Since the used operators preserve representation, it is enough to prove that each weighted partition added to tab G [R, R ] belongs to D G [R, R ], and that • in Case (a), we have D G [R, R ] ⊆ S∈S D H [S, S ], and • in Case (b), we have D G [R, R ] ⊆ A if we let tab H [S, S ] = D H [S, S ] for every S ∈ {0, . . . , d} k . Let (D, (p, w)) be a solution in D G [R, R ]. We start by proving that we have (p, w) ∈ S∈S D H [S, S ] if we are in Case (a), or (p, w) ∈ A if we are in Case (b).By the definition of S, we deduce that rH (D) ∈ S. Indeed, r j,G (D) = min(d, |D ∩ lab -1 G (j)|) equals min(d, r d j,H (D) + r d k,H (D)) because lab -1 G (j) = lab -1 H ({j, k}). Let p ∈ Π(active(r d H (D), S )) such that (D, (p , w)) is a candidate solution in D H [r d H (D), R ]. We claim that (D, (p , w)) is a solution in D H [r d H (D), R ]. Condition (1) is trivially satisfied. We deduce from the definition of S that Condition (2) is satisfied. We claim that Condition (3) is satisfied. If R = {0} k-1 , then we have S = {0} k and Condition (3) is satisfied because H[D] = G[D] must be connected since (D, (p, w)) is a solution in D G [R, R ]. Otherwise, every connected component C of G[D] = H[D] intersects lab -1 G (active(R, R )). Let C be a connected component of H[D]. If C contains a vertex labeled l in G with l ∈ active(R, R ) \ {j},then by definition of S , we have ∈ active(r d H (D), S ). Suppose now, C contains a vertex v in lab -1 G (j) and j ∈ active(R, R ). If v is labeled k in H, then r d k,H (D) = 0 and thus k belongs to active(r d H (D), S ) because s k = r j = 0. Symmetrically, if v is labeled j in H, then j ∈ active(r d H (D), S ). In both cases, C intersects lab -1 H (active(r d H (D), S )). We can conclude that Condition (3) is satisfied. Hence, (D, (p , w)) is a solution in D H [r d H (D), R ]. If r j = 0 or r j = 0 (Case (a)), then it is easy to see that p = p from Equation (3) and thus (p, w) ∈ tab H [S, S ]. Assume now that r j = 0 and r j = 0 (Case (b)). Let D k := D ∩ lab -1 H (k) and D j := D ∩ lab -1 H (j). Observe that the graph CG(G, R )[D ∪ V + (R )] can be obtained from the graph CG(H, S )[D ∪ V + (S )] by removing the vertices in V + k (R ) and by adding the edges between V + j (R ) and D k . Hence, p is obtained from p by merging the blocks containing j and k, and by removing k. Thus, we can conclude that (p, w) ∈ A. It remains to prove that each weighted partition (p, w) added to tab G [R, R ] belongs to D G [R, R ]. Let (p, w) be a weighted partition added to tab G [R, R ] from (p , w) ∈ tab H [S, S ], and let D ⊆ V (H) such that (D, (p , w)) is a solution in D H [S, S ]. We want to prove that (D, (p, w)) is a solution in D G [R, R ]. From the definitions of S and S , we deduce that D satisfies Conditions (1) and (2). We deduce that D satisfies also Condition (3) from Equation (3), the fact that lab -1 G (j) = lab -1 H ({j, k}), and because G[D] = H[D]. If r j = 0 or r j = 0, then it is easy to see from Equation (3) that p = p and that (D, (p, w)) satisfies Condition (4). Otherwise, we deduce from the previous observations concerning the differences between CG(G, R )[D ∪ V + (R )] and CG(H, S )[D ∪ V + (S )], that (D, (p, w)) satisfies Condition (4). In both cases, we can conclude that (D, (p, w)) is a solution in D G [R, R ].

  (a) If active(R, R ) = ∅, then we let tab G [R, R ] := rmc ({(∅, w) : (p, w) ∈ tab H [R, S ]}) . In this case, the partial solution in tab G [R, R ] are associated with connected solutions by Condition (3). The partial solutions in tab H [R, S ] trivially satisfy this condition in G. Notice that tab

Proof.

  Since the used operators preserve representation, it is enough to prove that every weighted partition added to tab G [R, R ] belongs to D G [R, R ], and that • in Case (a), we have D G [R, R ] ⊆ {(∅, w) : (p, w) ∈ D H [R, S ]}, • in Case (b), we have D G [R, R ] ⊆ D H [R, S ], and • in Case (c), we have D G [R, R ] ⊆ A if we let tab H [R, S ] = D H [R, S ]. Let (D, (p, w)) be a solution in D G [R, R ]. Let p ∈ Π(active(R, S )) such that (D, (p , w)) is a candidate solution in D H [R, S ]. We claim that (D, (p , w)) is a solution in D H [R, S ]. Condition (1) is trivially satisfied because lab G

( 3 )

 3 is satisfied because, for every connected component C of H[D], either C is a connected component of G[D], or C contains at least one vertex whose label is i or j. Hence, (D, (p , w)) is a solution in D H [R, S ]. If active(R, R ) = ∅, then p = ∅ and (p, w) is added in tab G [R, R ]. Else if r i = 0 or r j = 0, then p = p and (p, w) is also added to tab G [R, R ]. Otherwise, it is easy to see that p is obtained from p by merging the blocks of p containing i and j, and by removing them if they belong to { ∈ [k] : r = 0}. Thus, we can conclude that (p, w) ∈ {(∅, w) : (p, w) ∈ D H [R, S ]}) in Case (a), (p, w) ∈ D H [R, S ] in Case (b), and (p, w) ∈ A in Case (c).

  tabG[R, R ] := {({{1}}, w(x))} if r1 = 1 and r 1 = 1, ∅ otherwise.

We can assume w.l.o.g. that A = rmc(A), and thus for each p ∈ A, there is a unique w ∈ N such that (p, w) ∈ A.

We consider v 0 as a v 0 -vertex.

The indexes are modulo 2r.

This work is supported by French Agency for Research under the GraphEN project (ANR-15-CE40-0009).

Let A = (a 1 , . . . , a k ), B = (b 1 , . . . , b k ) ∈ {0, . . . , d} k . The following notion characterizes the pairs (A, B) compatible with R with respect to Condition [START_REF] Bergougnoux | Rank based approach on graphs with structured neighborhood[END_REF]. We say that (A, B) is R-compatible if and only if for all i ∈ [k], we have r i = min(d, a i + b i ).

Proof. Since the used operators preserve representation, it is easy to see that if R = {0} k , then we are done as

In the following, we assume that R = {0} k . Since the used operators preserve representation, it is enough to prove that

Since there are no edges between the vertices in V (G a ) and those in V (G b ), we conclude that

Symmetrically, we deduce that there exits

By Condition (4), two labels i, j are in the same block of p if and only if an i-vertex and a j-vertex are connected in CG(G, R )[D ∪ V + (R )]. On the other hand, i and j are in the same block of p a↑V p b↑V if and only if iRj where R is the transitive closure of the relation (i ∼ a j or i ∼ b j). By definition of CG(G, R ), for every label i ∈ active(R, R ), the vertices in lab -1 G (i) ∩ D are all adjacent to the vertices in V + i (R ). One can easily deduce from these observations that p = p a↑V p b↑V . Hence, (p, w) ∈ A.

We now prove that every weighted partition in

With the same arguments given previously, one easily deduces that Conditions ( 2)-( 4) are also satisfied. We conclude that

Theorem 5.13. There is an algorithm that, given an n-vertex graph G and an irredundant k-expression of G, computes a maximum (or a minimum) connected (σ, ρ)-dominating set in time

Proof. We do a bottom-up traversal of the k-expression and at each step we update the tables as indicated above. The correctness of the algorithm follows from Lemmas 5.10-5.12. From the definition of D G [R, R ], we deduce that the weight of an optimum connected (σ, ρ)-dominating set corresponds to the optimum over all R ∈ {0, . . . , d} k of opt{w : (∅, w)

Let us discuss the time complexity now. We claim that the tables of tab G can be computed in time 1) . We distinguish the following cases:

• If G = 1(x), then it is easy to see that tab G is computable in time O(d).

• If G = add i,j (H), then we update tab G [R, R ] from one entry tab H [R, S ] for some fixed S computable in constant time. The used join operation runs in time 2 k-1 • k O(1) (from Fact 3.3). Thus, tab G is computable in time

Since each table of tab H contains at most 2 k-1 entries, computing the call at the function reduce take 1) . Thus, we can compute tab G in time Observe that for all A, B ∈ {0, . . . , d} k : (1) There is only one R ∈ {0, . . . , d} k such that (A, B) is R-compatible.

This follows from the definition of R-compatibility. Hence, there are at most (d + 1) 2k tuples (A, B, R) such that (A, B) is R-compatible. (2) The size of join(tab Ga [A, R ], tab G b [B, R ]) is bounded by 2 2(k-1) and this set can be computed in time 2 2(k-1) • k O (1) .