Archontia C Giannopoulou
email: archontia.giannopoulou@tu-berlin.de

O-Joung Kwon
email: ojoungkwon@inu.ac.kr

Jean-Florent Raymond
email: raymond@tu-berlin.de

Dimitrios M Thilikos

Lean Tree-Cut Decompositions: Obstructions and Algorithms

Keywords: 2012 ACM Subject Classification Mathematics of computing → Graph algorithms; Theory of computation → Fixed parameter tractability tree-cut width, lean decompositions, immersions, obstructions, parameterized algorithms Digital Object Identifier 10.4230/LIPIcs.STACS.2019.32

The notion of tree-cut width has been introduced by Wollan in [The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, 110:47-66, 2015]. It is defined via tree-cut decompositions, which are tree-like decompositions that highlight small (edge) cuts in a graph. In that sense, tree-cut decompositions can be seen as an edge-version of tree-decompositions and have algorithmic applications on problems that remain intractable on graphs of bounded treewidth. In this paper, we prove that every graph admits an optimal tree-cut decomposition that satisfies a certain Menger-like condition similar to that of the lean tree decompositions of Thomas [A Menger-like property of tree-width: The finite case, Journal of Combinatorial Theory, Series B, 48(1): [67][68][69][70][71][72][73][74][75][76] 1990]. This allows us to give, for every k ∈ N, an upper-bound on the number immersion-minimal graphs of tree-cut width k. Our results imply the constructive existence of a linear FPT-algorithm for tree-cut width.

Introduction

Menger's theorem is a classic result in graph theory and arguably one of the most used. It can be informally stated as follows: two vertex sets of a graph can be linked by k vertexdisjoint paths if and only if they cannot be separated by the removal of k vertices [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF]. A significant feature of this result is that it provides a concise certificate for the optimality (in terms of cardinality) of a collection of k disjoint paths between two sets, in the form of a separator of size k. Many variants of Menger's theorem are known, including edge and directed versions [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF][START_REF] Grünwald | Ein Neuer Beweis Eines Mengerschen Satzes[END_REF].

In 1990, Thomas [START_REF] Thomas | A menger-like property of tree-width: The finite case[END_REF] obtained a similar duality between paths and separators in tree decompositions. Tree decompositions are central objects in the theory of graph minors of Robertson and Seymour. Introduced in the early times of their Graph Minors series [START_REF] Robertson | Graph Minors. II. Algorithmic Aspects of Tree-Width[END_REF], they soon became the standard way to approach problems related to minors (such as Disjoint Paths, Feedback Vertex Set, etc.) and to minor-closed graph classes. The result of Thomas is that every graph admits an optimal tree decomposition, said to be lean, where the following holds: two bags of the decomposition1 can be connected by k vertex-disjoint paths if and only if they cannot be separated by the removal of a bag on at most k vertices. That is, while Menger's theorem provides a set of k vertices separating the two bags, Thomas proved that such vertices (again forming a concise certificate of optimality) can moreover be found in a unique bag. Lean tree decompositions had important applications as they have been used to optimize parameter dependencies and to simplify arguments in proofs of the Graph Minors series [START_REF] Bellenbaum | Two short proofs concerning tree-decompositions[END_REF][START_REF] Erde | A unified treatment of linked and lean tree-decompositions[END_REF].

The objects of our attention in this paper are tree-like decompositions of graphs called tree-cut decompositions. These decompositions, introduced by Wollan in [START_REF] Wollan | The structure of graphs not admitting a fixed immersion[END_REF], highlight small (edge) cuts in graphs and are particularly suited to deal with problems related to the immersion ordering 2 and immersion-closed graph classes. (Comparatively, tree decompositions display small vertex separators and are tailored for minor-related problems.) A strength of tree-cut decompositions compared to other decompositions defined by edge cuts (such as cutwidth orderings or carving decompositions) is that they enjoy two highly desirable properties that mirror those of tree decompositions: (a) they admit an excluded wall immersion theorem [START_REF] Wollan | The structure of graphs not admitting a fixed immersion[END_REF] (comparable to the excluded grid minor theorem of Robertson and Seymour [START_REF] Robertson | Graph Minors. V. Excluding a planar graph[END_REF]) and (b) they can be used for dynamic programming, additionally for problems that cannot be tackled under the bounded-treewidth framework [START_REF] Ganian | Algorithmic applications of tree-cut width[END_REF][START_REF] Kim | An FPT 2-Approximation for Tree-Cut Decomposition[END_REF][START_REF] Archontia | Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes[END_REF]. Thus they are believed to be a credible translation of tree decompositions to the settings of immersions. The importance of tree decomposition-based techniques in graph algorithms is an additional motivation to study their possible counterpart in the immersion world. Our first contribution is to show that paths and cuts in tree-cut decompositions obey a duality as in the aforementioned result of Thomas.

Theorem 1. Every graph has an optimal tree-cut decomposition that is lean.

For the above statement to be meaningful, we adapted the notion of leanness to the setting of tree-cut decomposition; in particular it relates edge-disjoint paths with edge cuts. 3A similar notion of leanness has been previously studied in [START_REF] Archontia | Cutwidth: Obstructions and Algorithmic Aspects[END_REF] for the simpler setting of cutwidth orderings. We also note that analogs of lean tree decompositions appeared for several different width parameters such as θ-tree-width [START_REF] Carmesin | k-Blocks: A Connectivity Invariant for Graphs[END_REF][START_REF] Geelen | A generalization of the Grid Theorem[END_REF], pathwidth [START_REF] Lagergren | Upper Bounds on the Size of Obstructions and Intertwines[END_REF], directed pathwidth [START_REF] Kim | Tournament minors[END_REF], DAG-width [START_REF] Kintali | Directed Minors III. Directed Linked Decompositions[END_REF], rank-width [START_REF] Oum | Rank-width and vertex-minors[END_REF], linear-rankwidth [START_REF] Moustapha | An Upper Bound on the Size of Obstructions for Bounded Linear Rank-Width[END_REF], profile-and block-width [START_REF] Erde | A unified treatment of linked and lean tree-decompositions[END_REF], matroid treewidth [START_REF] Geelen | Branch-width and well-quasi-ordering in matroids and graphs[END_REF][START_REF] Azzato | Linked tree-decompositions of represented infinite matroids[END_REF][START_REF] Erde | A unified treatment of linked and lean tree-decompositions[END_REF] and matroid branchwidth [START_REF] Geelen | Branch-width and well-quasi-ordering in matroids and graphs[END_REF].

To prove Theorem 1, we design an improvement procedure that, in a finite number of steps, transforms a tree-cut decomposition that is not lean into a lean one.

Tree-cut decompositions can be used to define the graph parameter of tree-cut width, in the same way that treewidth can be defined via tree decompositions. Our second result pertains to obstructions for bounded tree-cut width. We say that a graph is an (immersion)-obstruction for tree-cut width at most k if it has tree-cut width more than k and all its proper immersions have tree-cut width at most k. Intuitively, such graphs delimit the border between the graphs of small tree-cut width (i.e. at most k) and the rest. As a consequence of the results of Robertson and Seymour in [START_REF] Robertson | Graph Minors. XXIII. Nash-Williams' Immersion Conjecture[END_REF], the set obs(k) of obstructions for tree-cut width at most k is finite, for every k ∈ N. Unfortunately the techniques used to prove this result (namely, properties of well-quasi-orders) do not provide explicit upper-bounds on its size. We consider here the related question of estimating the size of the elements of obs(k). This question has received significant attention in related settings. In [START_REF] Lagergren | Upper Bounds on the Size of Obstructions and Intertwines[END_REF], Lagergren gave exponential upper-bounds on the order of minor-obstructions to graphs of pathwidth or treewidth at most k (2 O(k 4 ) and 2 2 O ( k 5 ) ), respectively. Moreover, the size of immersion-obstructions to graphs of cutwidth at most k is known to lie between (3 k-5 -1)/2 [17] and 2 O(k 3 log k) [START_REF] Archontia | Cutwidth: Obstructions and Algorithmic Aspects[END_REF]. As noted in [START_REF] Booth | Cutwidth approximation in linear time[END_REF], these size estimations can be important in practice. Our result on this topic is a constructive upper-bound on the size of obstructions for bounded tree-cut width.

Theorem 2. Let k ∈ N. If G has tree-cut width more than k and every proper immersion of G has tree-cut width at most k, then G has at most 2 2 O(k 4 ) vertices.

Our proof has two main ingredients. The first one is an encoding into a finite number of types of the features of a graph that are relevant when computing tree-cut width, in the fashion of the folios of [START_REF] Robertson | Graph Minors. XIII. The disjoint paths problem[END_REF] and the protrusion machinery of [START_REF] Hans L Bodlaender | Meta) kernelization[END_REF], but adapted to the different setting studied here (and similar in this sense to the techniques developed in [START_REF] Archontia | Cutwidth: Obstructions and Algorithmic Aspects[END_REF][START_REF] Chatzidimitriou | An O(log OP T )-approximation for covering and packing minor models of θr[END_REF]). The second ingredient is our aforementioned result on leanness. Informally, Theorem 1 allows us, when "redundancy" has been identified in a graph (using the first ingredient), to obtain an immersion that has the same tree-cut width and less vertices. To the best of our knowledge, no explicit upper-bound concerning obs(k) was known before.

The third problem that we consider is of algorithmic nature: how fast can the treecut width of a graph be computed? This problem is NP-hard [START_REF] Kim | An FPT 2-Approximation for Tree-Cut Decomposition[END_REF] and therefore has been approached through parameterized complexity and approximation algorithms. A consequence of the aforementioned result of Robertson and Seymour [START_REF] Robertson | Graph Minors. XXIII. Nash-Williams' Immersion Conjecture[END_REF] and a result in [START_REF] Grohe | Finding Topological Subgraphs is Fixed-parameter Tractable[END_REF] is the existence -and the existence only -of an FPT algorithm that decides, given a graph G and k ∈ N, whether G has tree-cut width at most k. The first step towards a constructive FPT algorithm for tree-cut width was achieved by Kim et al. [START_REF] Kim | An FPT 2-Approximation for Tree-Cut Decomposition[END_REF] who designed a 2 O(k 2 log k) • n 2 -time factor 2 approximation algorithm. Our third result is the first constructive parameterized algorithm for tree-cut width. Theorem 3. It is possible to construct an algorithm that given an n-vertex graph G and an integer r decides whether G has tree-cut width more than r in f (r) • n steps, where f is some recursive function.

Our algorithm relies on the fact that graphs of small tree-cut width have small treewidth and on our result on the size of the obstructions. Graphs of large treewidth can be immediately rejected, while graphs of small treewidth can be searched for the existence of an obstruction to tree-cut width at most k using standard techniques on tree decompositions. We leave as an open problem to determine the optimal order of magnitude for f . S TA C S 2 0 1 9

32:4

Lean Tree-Cut Decompositions Organization of this extended abstract. In Section 2, we give preliminary definitions. The proofs of Theorem 1 is given in Section 3. In Sections 4 and 5 we introduce the machinery used to prove Theorems 2 and 3 whose proofs are given in Section 6. Finally, in Section 7, we provide some discussion on how to bound the parametric dependence of the algorithm of Theorem 3. Due to the space constraints, the proofs of the lemmas marked by have been omitted. They can be found in the full version [START_REF] Archontia | Lean tree-cut decompositions: obstructions and algorithms[END_REF].

Preliminaries

In this paper, graphs are undirected, finite, loopless, and may have multiple edges. We respectively denote by V (G) and E(G) the vertex and edge sets of a graph G and by |G| and G the cardinalities of these sets (counting edges with multiplicities).

A cut in a graph G is a set

F ⊆ E(G) such that G -F has more connected components than G. If A, B ⊆ V (G), the cut F is an (A, B)-cut if there is no path connecting a vertex of A to a vertex of B in G -F . If A, B ⊆ E(G), we say that F is an (A, B)-cut if there is no path from an endpoint of an edge of A to an endpoint of an edge of B in G -F . If (X, Y ) is a partition of V (G), we sometimes refer to the cut {xy ∈ E(G), x ∈ X and y ∈ Y } by (X, Y ). For k ∈ N, a graph is said to be k-edge-connected if it has no cut on (strictly) less than k edges.
If T is a tree and a, b ∈ E(T ), we denote by aT b the (unique) path of T from a to b and containing these edges.

Immersions. For graphs H and G, a pair (φ, ψ) is an H-immersion model in G if

φ is an injection from V (H) to V (G), ψ maps every edge uv of H to a path of G between φ(u) and φ(v) such that different edges are mapped to edge-disjoint paths. We say that H is an immersion of G if there is an H-immersion model in G and we denote this by H ≤ G. This defines a partial order on graphs. We also say that H is a proper immersion of G if H ≤ G and H is not isomorphic to G.

Tree-cut decompositions.

A near-partition of a set S is a family of pairwise disjoint subsets S 1 ,. . . , S k ⊆ S such that k i=1 S i = S. Observe that this definition allows some sets S i of the family to be empty. A tree-cut decomposition of a graph G is a pair (T, X ) where T is a tree and X = {X t } t∈V (T ) is a near-partition of V (G). We call elements of V (T ) nodes and elements of V (G) vertices for clarity. The set X t is called the bag of the decomposition corresponding to the node t, or just the bag at t.

An example of a tree-cut decomposition (X , T ) of a graph G is depicted in Figure 1. In this picture, the tree T is depicted in blue and G is drawn on top of it to highlight which vertices (resp. edges) belong to which bags (resp. adhesions). This decomposition has an empty bag, at node t.

For an edge {u, v} ∈ E(T ), we denote by T uv and T vu the connected components of T -{uv} containing u and v, respectively. The adhesion adh (T,X ) (uv) of some edge uv ∈ E(T ) is defined as the set of edges of G that have an endpoint in a bag of T uv and the other one in a bag of T vu . We drop the subscript when it is clear from the context. In Figure 1, the adhesion of the edge tu of T consists in the two thick red edges of G.

If G is 3-edge-connected, we define the width of (T, X ) as follows:

width(T, X ) = max max tt ∈E(T ) | adh(tt )|, max t∈V (T ) (|X t | + deg T (t)) .
The tree-cut width of G is the maximum width over all tree-cut decompositions of G. For the simplicity of the presentation we only work on 3-edge-connected graphs in the extended abstract 4 . However, our results hold for all graphs and full proofs can be found in the full version [START_REF] Archontia | Lean tree-cut decompositions: obstructions and algorithms[END_REF]

A Menger-like property of tree-cut width

In this section, we give a formal definition of the notion of leanness for tree-cut decompositions and we sketch the proof of Theorem 1.

A tree-cut decomposition (T, X ) is said to be lean if, for every distinct edges Observe that when the second point holds, adh(e) is an (A, B)-cut. Therefore, as with Thomas' notion of leanness mentioned in the introduction, the absence of a large collection of (here edge-disjoint) paths can be certified by a small (edge) separator that has restricted position. Out first result (Theorem 1) shows that every graph admits a tree-cut decomposition that is lean and has optimum width. Its proof can in fact be reduced to the case of 3-edge-connected graphs.

Lemma 4 ( (included in the proof of Theorem 1)). Theorem 1 holds iff it holds for 3-edge-connected graphs.

Therefore we can now focus on 3-edge-connected graphs. A crucial element of the proof of Theorem 1 is the definition of a potential on tree-cut decompositions, called fatness, as in Bellenbaum and Diestel's proof of Thomas leanness result for tree-decompositions [START_REF] Bellenbaum | Two short proofs concerning tree-decompositions[END_REF]. Let G be a graph on m edges and let (T, X ) be a tree-cut decomposition of G. For every i ∈ [m], we denote by T ≥i the subgraph of T induced by the edges that have adhesion at least i. The fatness, denoted by fatness(T, X ), of (T, X ) is the (2m)-tuple

(α m , -β m , α m-1 , -β m-1 , . . . , α 1 , -β 1 ), where for every i ∈ [m],
α i is the number of edges of T ≥i ; and β i is the number of connected components of T ≥i . We order fatnesses by lexicographic order. Informally, fatness is used to quantify the progress made when improving a non-lean tree-cut decomposition. This is captured by the following lemma which constitutes an important technical ingredient of the paper. Lemma 5 ( ). Let G be a 3-edge-connected graph. If (T, X ) is a tree-cut decomposition of G that is not lean, then G has a tree-cut decomposition of smaller fatness and no bigger width than the one of (T, X ).

As the fatness of tree-decompositions of a given graph can take a finite number of values, Lemma 5 implies that we can, after a finite number of "improvement steps", obtain a lean tree-cut decomposition. Let us now describe what we mean by improvement step. Let G be

a b a 1 ∅ s 1 b 1 b 1 ∅ s 2 a 2 a 2 b 2
Figure 2 A tree-cut decomposition of a graph G (left) and its (a, b, F )-segregation (right), where F is a cut that separates G into GA and GB. The vertices of GA and GB respectively lie in blue and green bags. Newly introduced bags, corresponding to nodes s1, s2, are empty. The adhesion of s1s2 is exactly F . such a graph and let (T, X ) be a tree-cut decomposition of G. Let a, b ∈ E(T ), and let F be an inclusion-wise minimal cut separating a graph G into two graphs that we call G A and G B . We define the (a, b, F )-segregation of (T, X ) as the pair (U, Y) obtained as follows:

1. consider a first copy T 1 of T , subdivide once the edge corresponding to b, call s 1 the subdivision vertex, and call the two created edges b 1 and b 1 , with the convention that (the copy of) a is closer to b 1 in T 1 ;

2. symmetrically, consider a second copy T 2 of T , subdivide once the edge corresponding to a, call s 2 the subdivision vertex, and call the two created edges a 2 and a 2 , with the convention that (the copy of) b is closer to a 2 in T 2 ;

3. in the disjoint union of these two trees, add an edge joining s 1 and s 2 : this gives U ;

4. for every t ∈ V (U ), let Y t =        X t ∩ V (G A ) if t ∈ V (T 1 ) \ {s 1 } X t ∩ V (G B ) if t ∈ V (T 2 ) \ {s 2 }, and
∅ if t ∈ {s 1 , s 2 }.
The construction of an (a, b, F )-segregation is depicted in Fig. 2. It is not hard to see that a segregation of a tree-cut decomposition is still a tree-cut decomposition.

For every non-lean tree-cut decomposition (T, X ) there are edges a, b, e ∈ E(T ) and subsets A ⊆ adh(a), B ⊆ adh(b) violating the definition of leanness. The proof of Lemma 5 consists in showing that the (a, b, F )-segregation of (T, X ), for some cut F carefully chosen using a, b, e, A, B, has the same width as (T, X ) and smaller fatness.

Tidy decompositions and branch interfaces

For the rest of the proofs we need the notion of tidiness of a tree-cut decomposition of a graph G, with respect to some edge-cut F of G. Informally, the tidiness property, is satisfied in a tree-cut decomposition of G, when, given a cut in a graph, the tree-cut decomposition can be almost partitioned (excluding a set of nodes whose size is upper-bounded linearly by the size of F ) to subtrees in such a way that the vertices of the graph residing in each subtree reside also to the same side of the cut. (See also Figure 3.) To clearly define tidy tree-cut decompositions and state the main lemma of this section we need the following.

⊆ A ⊆ B ⊆ A ⊆ A ⊆ B ⊆ A ⊆ B ∈ M ∈ M (i) ∈ M (ii)
For a tree T and a set M ⊆ V (T ), the least common ancestor closure (lca-closure) of M is the set lca(M ) ⊆ V (T ) obtained from M by repeatedly adding to it, for every triple x, y, z in the set, the common vertex of the paths xT y, yT z, and zT x. Let T be a tree, M ⊆ V (T ), and v ∈ V (T ). A node u ∈ V (T ) is a M -descendant of v if every path from u to a vertex of M contains v. We denote by desc M T (v) the set of such vertices (we drop the subscript when it is clear from the context). In particular v ∈ desc M (v) holds for every v ∈ V (T ) and desc M (v) = {v} holds for every v ∈ M . We also use the notation desc T (v) instead of desc

V (G) T (v).

Definition 7 (tidy tree-cut decomposition). Let D = (T, {X u } u∈V (T ) ) be a tree-cut decomposition of a graph G and let (A, B) be a cut of this graph. Let M ⊆ V (T ) be the lca-closure of the nodes of T whose bags contain endpoints of the cut (A, B). We denote by C M i , i ∈ [2] the set of connected components of T -M that have exactly i neighbors in M (and drop the superscript M if it is clear from the context).

We say that D is (A, B)-tidy if the following conditions hold for every connected component

F of T -M : (i) if F ∈ C M 2 :
for every w ∈ V (F ), all the bags at T desc M (w) are subsets of one of A and B; (ii) if F ∈ C M 1 : let u be the node of F adjacent to M . Then, first, u has at most two neighbors in F ; let us call them v, w (if they exist). Second, X u intersects at most one of A and B and all the bags at T desc M (v) (resp. T desc M (w)) are subsets of A (resp. B), or the other way around. These two situations are again depicted on Fig. 3.

S TA C S 2 0 1 9

32:8

Lean Tree-Cut Decompositions Furthermore, we show that there exists a tidy tree-cut decomposition of optimum width where the number of these subtrees is upper-bounded by a function of the size of the cut and the tree-cut width of the graph.

J A J B J A J B v J a l + b l a r + b r v A v B a l + b l a r + b r a r + b l ∈ M v a l + b l J ∈ M v a l + b l a l b l (a) (b)
Figure 4 Improvement step towards obtaining a tidy tree-cut decomposition from a general tree-cut decomposition without increasing the width.

Before we present the lemma, we need the following definition. Let G be a graph and let D = (T, {X} u∈V (T ) ) be a tree-cut decomposition of G. For X ⊆ V (G), a X-block is a maximal subtree F of T such that: bags at nodes of F are subsets of X; at most two nodes of T -V (F ) have a neighbor in F . If (A, B) is a cut, we refer to A-and B-blocks as (A, B)-blocks.

Lemma 8 ( ). Let ∈ N ≥3 and G be a 3-edge-connected graph. If (A, B) is a cut of G of size , then there is an optimum tidy tree-cut decomposition D = (T, X ) of G with less than 8 • tcw(G) (A, B)-blocks in T -M , where M is the lca-closure of the nodes of T whose bags contain endpoints of the cut (A, B).

Note that from the definition of a block, two A-blocks (resp. B-blocks) cannot be connected by a link of T . This simple property is crucial in the proof of Lemma 8. It allows us, given a tree-cut decomposition of a graph G that has many (A, B)-blocks, to swap two of them (hence decreasing the total number of blocks) without increasing the width of the decomposition. Fig. 4 illustrates how we may obtain a tidy tree-cut decomposition of optimum width from a general tree-cut decomposition of optimum width while Fig. 5 illustrates the intuition behind swapping A-and B-blocks in order to decrease their total number.

T i-1 T i T i+1 T i+2 v p i-1 v s i-1 v p i e i-1 v s i v p i+1 e i v s i+1 v p i+2 e i+1 v s i+2 L i-1 R i R i+1 P i S i T i-1 T i+1 T i T i+2 v p i-1 v s i-1 v p i+1 v s i+1 v p i v s i v p i+2 v s i+2 L i-1 R i+1 P i S i P i+1 S i+1

32:9 5 Branch Interfaces

Tidy tree-cut decompositions will be used in this section to classify certain subgraphs of a graph into a bounded number of equivalence classes. This will be directly used to obtain our result on obstructions.

A k-boundaried graph is a pair G = (G, x) where G is a graph and x = (x 1 , . . . , x k ) is a k-tuple of the graph's vertices, called boundary vertices (ordered, not necessarily distinct). The extension of G is the graph G * obtained from G by adding k new vertices x 1 , . . . , x k and edges x 1 x 1 , . . . , x k x k . The join A ⊕ B of two k-boundaried graphs A = (A, x), B = (B, ȳ) is the graph obtained from the disjoint union of A and B by adding an edge

x i y i for i ∈ [k].
Intuitively, a boundaried graph can be seen as the subgraph corresponding to one side of an (edge) cut in a larger graph. Its boundary vertices then record the endpoints the edges of the cut and can be glued to an other boundaried graph to recover the original graph.

We note that our definition of boundaried graph (already used in previous work [START_REF] Archontia | Cutwidth: Obstructions and Algorithmic Aspects[END_REF][START_REF] Archontia | Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes[END_REF][START_REF] Chatzidimitriou | Minors in graphs of large θr-girth[END_REF][START_REF] Chatzidimitriou | An O(log OP T )-approximation for covering and packing minor models of θr[END_REF]) slightly differs from that usually followed in the literature (e.g. in [START_REF] Hans L Bodlaender | Meta) kernelization[END_REF]), in particular the join operation. This is because the problems that we consider are related to (edge) cutsa setting where our definition is more natural -while other papers often deal with settings pertaining to (vertex) separators, typically graphs of bounded treewidth.

Let A and B be two k-boundaried graphs and let G = A ⊕ B. (This is roughly the same as saying that G has a cut (A, B) of size k.) Let D = (T, X ) be an (A, B)-tidy tree-cut decomposition of G. Let M denote the lca-closure of the vertices of T whose bags contain endpoints of the cut.

Let us construct a new pair B = (U, Y) from D as follows: for every (A, B)-block F of T , we contract F to a single vertex x and define Y x as the set of vertices of G that are contained in bags at F . For every x ∈ M we set Y x = X x . We call B a bucketing of G. In order to avoid confusion with the bags of a tree-cut decomposition, we refer to the elements of Y as buckets. Recall that by Lemma 8, the vertices of M are separated in T by a bounded number of alternations of (A, B)-blocks. Therefore the size of U is bounded by a function of k and tcw(G).

A bucketing of A is obtained from a bucketing of G by forgetting the content of the buckets corresponding to B; formally it is the pair (U, Y ) where

Y = {Y u ∩ V (A), u ∈ V (U -M )} ∪ {Y u , u ∈ M }.
Given the bucketing (U, Y ) of A together with D, we can compute:

for each edge e of U , the size z(e) of its adhesion (defined as for tree-cut decompositions); for each node x ∈ V (T -M ), the width z(x) of the corresponding (A, B)-block in D;5 for each node x ∈ V (T -M ), the maximum α(x) of adhesions sizes over the subpath linking the attachement points (i.e. vertices with a neighbor outside of the block) of the corresponding (A, B)-block in D; for each node x ∈ M , the sum z(x) of its degree in T and bag size in D; a function f : [2k] → V (U ) specifying which buckets of U contain the endpoints of the cut.

Informally, these values encode all the relevant information about the contribution of A to the width of D. If = tcw(G), then we say that (U, z, α, f ) (seen as a tuple independent of A) is a (k, )-branch interface 6 and we say that A conforms with this branch interface.

Observe that the number of (k, )-branch interfaces can be upper-bounded by a function of k and . In particular we have the following. Observation 9. For all k, ∈ N there are 2 O( k log k) (k, )-branch interfaces.

We denote by I k, (A) the set of (k, )-branch interfaces A conforms with. Intuitively, this set records all the possible ways for A to appear in a tidy tree-cut decomposition of a graph A ⊕ B of tree-cut width at most . That is, whatever k-boundaried graph B we consider (among those such that tcw(A ⊕ B) ≤ ), all the possible ways (A, B)-blocks can interleave and contribute to the width in a tidy tree-cut decomposition of A ⊕ B is of bounded size and recorded in I k, (A). This is formalized by the following lemma.

Theorem 10 (edge-protrusion replacement lemma ). Let k, be two positive integers. Let also A 1 and A 2 be two k-boundaried graphs with I k, (A 1 ) = I k, (A 2 ). Then for any k-boundaried graph B where tcw(A 1 ⊕ B) ≤ and such that both

A 1 ⊕ B and A 2 ⊕ B are 3-edge connected, it holds that tcw(A 2 ⊕ B) = tcw(A 1 ⊕ B).

Obstructions and algorithms for tree-cut width

We explain in this section how the machinery introduced in the two previous sections can be used to obtain theorems 2 and 3.

Let H = (H, x) and G = (G, y) be two k-boundaried graphs. If there is an H * -immersion model (φ, ψ) of G * where φ(x i ) = y i and φ(x i ) = y i for each i ∈ [k], then we say that H is a rooted immersion of G and we denote this by H ≤ G.

Immersion obstructions.

For every k ∈ N, we denote by obs(k) the set of all immersionminimal graphs whose tree-cut width is strictly greater than k. For instance, it is easy to see that obs(1) contains only the graph with two vertices and a double edge between them.

Our purpose is to provide a bound to the order of the graphs in obs(k), as a function of k. It follows from [START_REF] Kim | An FPT 2-Approximation for Tree-Cut Decomposition[END_REF]Lemmata 3 and 4] that all graphs in obs(k) are 3-edge-connected for k ≥ 2.

We use the following lemmata.

Proposition 11 ([16]). Let w, m be positive integers and let y be a word in [w] * of length m w . Then there is a number k ∈ [w] and a subword u of y such that all numbers in u are at least k and u contains the number k at least m times. Proof. By Lemma 5, there exists a lean tree-cut decomposition D = (T, X ) of G with width at most w. We also assume that for every node t of T of degree at most 2, the bag X t is non-empty, otherwise we revise D by contracting a link incident to t. The 3-edge connectivity of G implies that ∆(T ) ≤ w. We root T on some, arbitrarily chosen, node s. This permits us to see T as a directed tree where all links are oriented towards the root s. In particular, if (v, u) is a link of T , we always assume that u is closer than v to the root.

From Observation 9 there is a function α : N 2 → N, with α(w, ) = 2 O( •w•log w) , such that the number of the different (w, ) interfaces of w-boundaried graphs is upper-bounded by α(w, ). We define d = m w where m = α(w, ) + 1 and = 8wr. Let z be a node of T of maximum distance from the root s. Notice that z is a leaf of T . Let also f : N 2 → N be a function such that if |T | > f (d, w), then T contains a path P of length d from z to some node, say u that is different than the root s. Notice that, as ∆(T ) ≤ w, we can choose f such that f (d, w) = 2 O(d•log w) . We also set up the function g : N 2 → N where g(r, w) = f (d, w) • w.

Clearly, g(r, w) = f (m w , w) • w = 2 O((2 O( •w 2 •log w) ) w •log w) • w = 2 2 O(r•w 3 ) .
Notice that if |G| > g(r, w), then |T | > f (d, w) and the aforementioned path P exists in T . Let e 1 , . . . , e d be the links of P ordered so that e 1 is the one that is closer to the root and let w ei = | adh D (e i )|. We now see the string y = w e1 . . . w e d as a word in [w] * . As d = m w , from Proposition 11 there is some k ∈ [w] and a subword y = w ei . . . w ej of y such that w e h ≥ k for h ∈ [i, j] and there is some I ⊆ [i, j] such that m = |I| and ∀h ∈ I w ej = k. Let f 1 , . . . , f m be the links in {e h | h ∈ I} ordered as a subsequence of e 1 , . . . , e d . As D is lean, we know that there exist k edge-disjoint paths from adh (T,X ) (f 1 ) to adh (T,X ) (f m ). We denote these paths by P 1 , . . . , P k . Notice also that for every q ∈ [m], adh (T,X ) (f m ) contains exactly one edge from each of the paths in P 1 , . . . , P k . We denote by e q,p the unique edge in E(P k ) ∩ adh (T,X ) (f q ), for (p, q) ∈ [k] × [m]. for every q ∈ [m], we define λ q : adh (T,X ) (f q ) → [w fq ] so that λ q (e q,p ) = p for p ∈ [k].

For q ∈ [m], we denote by t q the tail of the edge f q and we define A q = (A q , xq ) where A q = G[ t∈desc T (tq) X t ] and xq are the endpoints of the edges in adh (T,X ) (f q ) that belong to A 1 , ordered according to λ q (recall that desc T (t q ) consists of the descendants of t q , including t q , in the rooted tree T ). We also set B q = (B q , x q ) where B q = G -V (A q ) and x q are the endpoints of the edges in adh (T,X ) (f q ) that belong to B q , again ordered according to λ q . Notice that for every q ∈ [m], B q ⊕ A q = G. Moreover for every (q, q ) ∈ [m] 2 , where q ≤ q , there are k edge-disjoint paths in A q that are joining, for each p ∈ [k] the edge e q,p with the edge e q ,p . This implies that A q ≤ A q . This, combined with Lemma 12, yields that

I k, (A 1 ) ⊆ • • • ⊆ I k, (A m )
and, as m = α(r, w) + 1, there is a pair (q, q ) ∈ [m] 2 , where q < q and I k, (A q ) = I k, (A q ). We set H = A q ⊕ B q . Since q = q , H is a proper immersion of G. From Lemma 10, the fact that tcw(A q ⊕B q ) = tcw(G) ≤ r implies that tcw(H) = tcw(A q ⊕B q ) = tcw(A q ⊕B q ) = tcw(G) ≤ r. Theorem 14 (Restatement of Theorem 2). For every k ∈ N, every graph in obs(k) has

2 2 O(k 4 ) vertices. Proof. Let G ∈ obs(k). This means that tcw(G) ≥ k +1 and that if H is a proper immersion of G, then tcw(H) < tcw(G) and hence, tcw(H) ≤ k. It is easy to verify that if H is a proper immersion of G with H = G -1 then tcw(H) ≥ tcw(G) -1. This last observation implies that tcw(G) ≤ k + 1. If |V (G)| > g(k, k + 1
) (where g is the function of Lemma 13) then Lemma 13 implies that G contains as a proper immersion a graph H for which tcw(H) ≤ k implies that tcw(G) ≤ k. As tcw(H) ≤ k for every proper immersion H of G, we deduce that tcw(G) ≤ k, a contradiction to the fact that tcw(G) ≥ k + 1. The result follows as g(k, k + 1) = 2 2 O(k 4 ) . S TA C S 2 0 1 9 32:12 Lean Tree-Cut Decompositions Tree decompositions. A tree decomposition of a graph G is a pair D = (T, X ), where T is a tree and X = {X t | t ∈ V (T )} is a collection of subsets of V (G) such that: t∈V (T ) X t = V (G), for every uv ∈ E, there is a t ∈ V (T ) such that {u, v} ⊆ X t , and for each {x, y, z} ⊆ V (T ) such that z lies on the unique path between x and y in T , X x ∩ X y ⊆ X z . The width of a tree decomposition D = (T, X ) is max t∈V (T ) |X t | -1. The treewidth of a graph G, denoted by tw(G), is the smallest integer w such that there exists a tree decomposition of G of width at most w.

The proof of Theorem 3 comes as a direct consequence of Theorem 14.

Proof of Theorem 3. We set n = |V (G)|. Observe that ∆(G) = O r [START_REF] Azzato | Linked tree-decompositions of represented infinite matroids[END_REF]. Moreover, if an edge has multiplicity strictly greater than r, then both its endpoints should be in the same bag of a tree-cut decomposition with width at most r. Therefore, we may replace each edge in G of multiplicity bigger than r + 1 by one of multiplicity r + 1 and this modification can be implemented in O r (n) steps. By applying this preprocessing we may assume that G has O r (n) edges.

In [START_REF] Ganian | Algorithmic applications of tree-cut width[END_REF] it was proved that there exists a constant c 1 such that, for every graph H, tw(H) ≤ c 1 • (tcw(H)) 2 . We run the algorithm in [START_REF] Hans | Daniel Lokshtanov, and Michal Pilipczuk. A (c k n) 5-Approximation Algorithm for Treewidth[END_REF] that, given a graph H and an integer q, either outputs a tree decomposition of H of width at most 5q or reports that tw(G) > q, setting H = G and q = c 1 • r 2 . If tw(G) > q we know that tcw(G) > r and we readily have an answer. Therefore, we can assume that we have a tree decomposition of G of width at most 5c 1 • r 2 . As the property of the immersion-containment of a graph H can be expressed in Monadic Second Order Logic, by using Courcelle's theorem, it is possible to construct an algorithm that, given two graphs H 1 and H 2 , outputs whether H 1 ≤ H 2 in O |V (H1)|+tw(G) (|V (H 2 )|) steps. By Theorem 14, the set obs(r) can be constructed in O r (1) steps. Then, by testing immersion-containment for every graph H ∈ obs(r), we can decide whether tcw(G) ≤ r in O r (n) steps.

Discussion

An interesting direction is to specify the parameterized dependence of the algorithm in Theorem 3. We argue below on why the proof of Lemma 13 can already give a first bound. Notice that Lemma 10 defines an equivalence relation of w-boundaried graphs. We say that two k-boundaried graphs G 1 and G 2 are (w, r)-equivalent, namely G 1 ≡ w,r G 2 if I w,8wr (G 1 ) = I w,8wr (G 2 ). Notice that the proof of Lemma 13 already implies that a minimum-size of a representative of any of the equivalence classes of ≡ w,r has g(r, w) = 2 2 O(r•w 3 ) vertices. By brute-force checking on all graphs on g(r, w) = 2 2 O(r•w 3 ) vertices, we may construct a set R w,r of representatives for ≡. Moreover |R w,r | = 2 2 2 O(r•w 3 ) . The knowledge of R w,r permits us to avoid the use of Courcelle's theorem in Theorem 3. For this, we first transform the tree decomposition of the proof of Theorem 3 to a tree-cut decomposition with width w = O(r 4 ) using [START_REF] Wollan | The structure of graphs not admitting a fixed immersion[END_REF]Lemma 12]. Then we implement an algorithmic version of the proof of Lemma 13: as long as the sub-tree of T rooted on u of height 2 2 2 r•w 3 exists, we reduce G = A q ⊕ B q to the smaller equivalent instance G = A q ⊕ B q . Given that |R w,r | = 2 2 2 O(r•w 3 ) and using suitable data-structures, this compression can be implemented in 2 2 2 O(r 13 ) steps and as it is repeated at most n times, it will report a correct answer in 2 2 2 O(r 13 )

• n steps.

Clearly, the parameterized dependence of the above argumentation is still too heavy. We believe that a detailed dynamic programming based on how collections of branch interfaces are updated along a rooted tree-cut decomposition may yield a bound f (r) = 2 poly(r) to the function of Theorem 3.

A second direction for further research is to obtain an algorithm that, besides computing the tree-cut width of a graph, also provides a tree-cut decomposition of optimal width.

Figure 1

 1 Figure 1 Example of a tree-cut decomposition (right) of a graph (left).

  a, b ∈ E(T ) and every A ⊆ adh(a), B ⊆ adh(b) with |A| = |B| =: k, either there are k edge-disjoint paths linking A to B; or there is an edge e in aT b such that | adh(e)| < k.

Figure 3

 3 Figure 3 Parts of an (A, B)-tidy tree-cut decomposition, with subtrees colored differently depending whether the bags of their vertices are included in A or in B.

Lemma 6 (

 6 [START_REF] Fedor | Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms[END_REF]). Let T be a rooted forest and M ⊆ V (T ). Then | lca(M )| ≤ 2|M | and every connected component C of T -lca(M ) has at most two neighbors in T .

Figure 5

 5 Figure 5 From D (top) to D (bottom): swapping the blocks Ti and Ti+1.

Lemma 12 (Lemma 13 .

 1213 ). Let k ∈ N and let H = (H, x) and G = (G, y) be two k-boundaried graphs. For every ∈ N, if H ≤ G, then I k, (G) ⊆ I k, (H). There exists a function g : N 2 → N such that for every w, r ∈ N and every 3-edge-connected graph G where tcw(G) ≤ w and |V (G)| > g(r, w), G contains as a proper immersion a graph H for which tcw(H) ≤ r implies tcw(G) ≤ r. Moreover such a function can be chosen so that g(r, w) = 2 2 O(r•w 3 ) .

We follow here the standard terminology about tree-decompositions, see Section 6 for details.

The immersion ordering is a partial order on graphs that has properties similar to the minor ordering, see Section 2 for details.

The formal definition is given in Section 2.

There is a definition the width for tree-cut decompositions of graphs that are not 3-edge-connected. It can be found in the full version[START_REF] Archontia | Lean tree-cut decompositions: obstructions and algorithms[END_REF]. The definition that we give here is equivalent to that of Wollan in[START_REF] Wollan | The structure of graphs not admitting a fixed immersion[END_REF].S TA C S 2 0 1 9

That is, the width of D restricted to this block.

Note that we define here a slightly simplified notion of branch interface than in the full version[START_REF] Archontia | Lean tree-cut decompositions: obstructions and algorithms[END_REF], which is sufficient for the presentation given in this extended abstract.

Acknowledgements

We are grateful to Michał Pilipczuk and Marcin Wrochna for extensive discussions about the proof of Theorem 1.

Funding Archontia C. Giannopoulou: Supported by the ERC consolidator grant Distruct-648527. O-joung Kwon: Supported by the ERC consolidator grant Distruct-648527 and by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. NRF-2018R1D1A1B07050294). Jean-Florent Raymond: Supported by ERC consolidator grant Distruct-648527. Dimitrios M. Thilikos: Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). Supported by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019. . Thilikos; licensed


Eun Jung Kim

Maria Serna
email: mjserna@cs.upc.edu

Dimitrios M Thilikos

Data-Compression for Parametrized Counting Problems on Sparse Graphs

Keywords: 2012 ACM Subject Classification Theory of computation → Graph algorithms analysis Parameterized counting, compactor, protrusion decomposition Digital Object Identifier 10.4230/LIPIcs.ISAAC.2018.20

We study the concept of compactor, which may be seen as a counting-analogue of kernelization in counting parameterized complexity. For a function F : Σ * → N and a parameterization κ : Σ * → N, a compactor (P, M) consists of a polynomial-time computable function P, called condenser, and a computable function M, called extractor, such that F = M•P, and the condensing P(x) of x has length at most s(κ(x)), for any input x ∈ Σ * . If s is a polynomial function, then the compactor is said to be of polynomial-size. Although the study on counting-analogue of kernelization is not unprecedented, it has received little attention so far. We study a family of vertex-certified counting problems on graphs that are MSOL-expressible; that is, for an MSOL-formula φ with one free set variable to be interpreted as a vertex subset, we want to count all A ⊆ V (G) where |A| = k and (G, A) |= φ. In this paper, we prove that every vertex-certified counting problems on graphs that is MSOL-expressible and treewidth modulable, when parameterized by k, admits a polynomial-size compactor on H-topological-minor-free graphs with condensing time O(k 2 n 2 ) and decoding time 2 O(k) . This implies the existence of an FPT-algorithm of running time O(n 2 k 2 ) + 2 O(k) . All aforementioned complexities are under the Uniform Cost Measure (UCM) model where numbers can be stored in constant space and arithmetic operations can be done in constant time.

Introduction

A large part of research on parameterized algorithms has been focused on algorithmic techniques for parametrizations of decision problems. However, relatively less effort has been invested for solving parameterized counting problems. In this paper, we provide a general data-reduction concept for counting problems, leading to a formal definition of the notion of a compactor. Our main result is an algorithmic meta-theorem for the existence of a polynomial size compactor, that is applicable to a wide family of problems of graphs.

General context

Algorithmic meta-theorems. Parameterized complexity has been proposed as a multivariable framework for coping with the inherent complexity of computational problems . Nowadays, it is a mature discipline of modern Theoretical Computer Science and has offered a wealth of algorithmic techniques and solutions (see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to fixed-parameter algorithms[END_REF] for related textbooks). In some cases, in-depth investigations on the common characteristics of parameterized problems gave rise to algorithmic meta-theorems. Such theorems typically provide conditions, logical and/or combinatorial, for a problem to admit a parameterized algorithm [START_REF] Grohe | Methods for algorithmic meta theorems, chapter Model Theoretic Methods in Finite Combinatorics[END_REF][START_REF] Grohe | Logic, graphs, and algorithms[END_REF][START_REF] Kreutzer | Algorithmic Meta-theorems[END_REF][START_REF] Seese | The structure of the models of decidable monadic theories of graphs[END_REF]. Important algorithmic meta-theorems concern model-checking for Monadic Second Order Logic (MSOL) [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF][START_REF] Borie | Automatic Generation of Linear-Time Algorithms from Predicate Calculus Descriptions of Problems on Recursively Constructed Graph Families[END_REF][START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF][START_REF] Seese | Linear Time Computable Problems and First-Order Descriptions[END_REF] on bounded treewidth graphs and model checking for First Order Logic (FOL) on certain classes of sparse graphs [START_REF] Flum | Fixed-parameter tractability, definability, and modelchecking[END_REF][START_REF] Frick | Deciding First-Order Properties of Locally Tree-Decomposable Graphs[END_REF][START_REF] Dawar | Locally Excluding a Minor[END_REF][START_REF]1 8 20:12 Data-Compression for Parametrized Counting Problems on Sparse Graphs 20[END_REF][START_REF] Dvorak | Deciding First-Order Properties for Sparse Graphs[END_REF][START_REF] Grohe | Deciding First-order Properties of Nowhere Dense Graphs[END_REF].

In some cases, such theorems have a counterpart on counting parameterized problems. Here the target is to prove that counting how many solutions exist for a problem is fixed parameter tractable, under some parameterization of it. Related meta-algorithmic results concern counting analogues of Courcelle's theorem, proved in [START_REF] Courcelle | On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic[END_REF], stating that counting problems definable in MSOL are fixed-parameter tractable when parameterized by the treewidth of the input graph. Also similar results for certain fragments of MSOL hold when parameterized by the rank-width of the input graph [START_REF] Courcelle | On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic[END_REF]. Moreover, it was shown in [START_REF] Frick | Generalized Model-Checking over Locally Tree-Decomposable Classes[END_REF] that counting problems definable in first-order logic are fixed-parameter tractable on locally tree-decomposable graphs (e.g. for planar graphs and bounded genus graphs).

Kernelization and data-reduction.

A well-studied concept in parameterized complexity is kernelization. We say that a parameterized problem admits a polynomial kernel if there is an algorithm -called kernelization algorithm -that can transform, in polynomial time, every input instance of the problem to an equivalent one, whose size is bounded by a function of the parameter. When this function is polynomial then we have a polynomial kernel. A polynomial kernel permits the drastic data-reduction of the problem instances to equivalent "miniatures" whose size is independent from the bulk of the input size and is polynomial on the parameter. That way, a polynomial kernel, provides a preprocessing of computationally hard problems that enables the application of exact algorithmic approaches (however still super-polynomial) on significantly reduced instances [START_REF] Lokshtanov | Kernelization -Preprocessing with a Guarantee[END_REF].

Meta-algorithmic results for kernelization.

Apart from the numerous advances on the design of polynomial kernels for particular problems, algorithmic meta-theorems appeared also for kernelization. The first result of this type appeared in [START_REF] Hans | Meta) Kernelization[END_REF], where it was proved that certain families of problems on graphs admit polynomial kernels on bounded genus graphs. The logic-condition of [START_REF] Hans | Meta) Kernelization[END_REF] is CMSOL-expressibility or, additionally, the Finite Integer Index (FII) property (see [START_REF] Abrahamson | Finite Automata, Bounded Treewidth and Well-Quasiordering[END_REF][START_REF] Hans | Reduction algorithms for graphs of small treewidth[END_REF][START_REF] De | Algorithms for Graphs of Small Treewidth[END_REF]). Moreover, the meta-algorithmic results of [START_REF] Hans | Meta) Kernelization[END_REF] require additional combinatorial properties for the problems in question. The results in [START_REF] Hans | Meta) Kernelization[END_REF] where 20:3 extended in [START_REF] Fomin | Bidimensionality and Kernels[END_REF] (see also [START_REF] Fedor | Bidimensionality and Kernels[END_REF]) where the combinatorial condition for the problem was related to bidimensionality, while the applicability of the results was extended in minor-closed graph classes. Finally, further extensions appeared in [START_REF] Jung | Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions[END_REF] where, under the bounded treewidthmodulability property (see Subsection 1.2), some of the results in [START_REF] Fomin | Bidimensionality and Kernels[END_REF][START_REF] Hans | Meta) Kernelization[END_REF] could be applied to more graph classes, in particular those excluding some fixed graph as a topological minor.

Data reduction for counting problems. Unfortunately, not much has been done so far in the direction of data-reduction for parameterized counting problems. The most comprehensive work in this direction was done by Marc Thurley [START_REF] Thurley | Kernelizations for parameterized counting problems. In 4th international conference on Theory and applications of models of computation[END_REF] (see also [START_REF] Thurley | Tractability and Intractability of Parameterized Counting Problems[END_REF]) who proposed the first formal definition of a kernelization analogue for parameterized problems called counting kernelization. In [START_REF] Thurley | Kernelizations for parameterized counting problems. In 4th international conference on Theory and applications of models of computation[END_REF] Thurley investigated up to which extent classic kernelization techniques such as Buss' Kernelization and crown decomposition may lead to counting counterparts of kernelization. In this direction, he provided counting kernelizations for a series of parameterized counting problems such as and p-#VertexCover, p-card-#Hitting Set and p-#Unique Hitting Set.

Compactor enumeration.

Another framework for data-reduction on parameterized counting problems is provided by the notion of a compactor. In a precursory level, it appeared for the first time in [START_REF] Díaz | Efficient algorithms for counting parameterized list H-colorings[END_REF]. The rough idea in [START_REF] Díaz | Efficient algorithms for counting parameterized list H-colorings[END_REF] was to transform the input of a parameterized counting problem to a structure, called the compactor, whose size is (polynomially) bounded by the parameter and such that the enumeration of certain family of objects (referred as compactor enumeration in [START_REF] Díaz | Efficient algorithms for counting parameterized list H-colorings[END_REF]) in the compactor is able to derive the number of solutions for the initial instance. This technique was introduced in [START_REF] Díaz | Efficient algorithms for counting parameterized list H-colorings[END_REF] for counting restrictive list H-colorings and, later in [START_REF] Nishimura | Parameterized Counting Algorithms for General Graph Covering Problems[END_REF], for counting generalized coverings and matchings. However none of [START_REF] Díaz | Efficient algorithms for counting parameterized list H-colorings[END_REF][START_REF] Nishimura | Parameterized Counting Algorithms for General Graph Covering Problems[END_REF] provided a general formal definition of a compactor, while, in our opinion, the work of Thurley provides a legitimate formalization of compactor enumeration.

In this paper, we define formally the concept of a compactor for parameterizations of function problems (that naturally include counting problems) that is not based on enumeration. As a first step, we observe that for parameterized function problems, the existence of a compactor is equivalent to the existence of an FPT-algorithm, a fact that is also the case for classic kernels on decision problems and for counting kernels in [START_REF] Thurley | Kernelizations for parameterized counting problems. In 4th international conference on Theory and applications of models of computation[END_REF].

Under the above formal framework, we prove an algorithmic meta-theorem on the existence of polynomial compactors for a general family of graph problems. In the next subsection, we define the compactor concept and we present the related meta-algorithmic results.

Our results

Counting problems and parameterizations. First of all notice that, for a counting problem, it is not possible to have a kernelization in the classic sense, that is to produce an reduced instance, bounded by a function of k, that is counting-equivalent in the sense that the number of solutions in the reduced instance will provide the number of solutions in the original one. For this reason we need a more refined notion of data compression where we transform the input instance to "structure", whose size is bounded by a function of k. This structure contains enough information (combinatorial and arithmetical) so as to permit the recovering of the number of the solutions in the initial instance. We next formalize this idea to the concept of a compactor.

Let N be all non-negative integers and by poly the set of all polynomials. Let Σ be a fixed alphabet. A parameterized function problem is a pair (F, κ) where F, κ : Σ * → N. An FPT-algorithm for (F, κ) is one that, given x ∈ Σ * , outputs F (x) in f (κ(x)) • poly(|x|) I S A A C 2 0 1 8

20:4

Data-Compression for Parametrized Counting Problems on Sparse Graphs steps. When evaluating the running time, we use the standard Uniform Cost Measure (UCM) model where all basic arithmetic computations are carried out in constant time. We also disregard the size of the numbers that are produced during the execution of the algorithm.

Compactors. Let (F, κ) be a parameterized function problem. A compactor for (F, κ) is a pair (P, M ) where P : Σ * → Σ * is a polynomially computable function, called an condenser,

M : Σ * → N is a computable function, called a extractor, F = M • P , i.e., ∀x ∈ Σ * , F (x) = (M • P )(x)
, and there is a recursive function s :

N → N where ∀x ∈ Σ * |P (x)| ≤ s(κ(x)
). We call the function s size of the compactor (P, M ) and, if s ∈ poly, we say that (P, M ) is a polynomial-size compactor for (F, κ). We call the running time of the algorithm computing P , measured as a function of |x|, condensing time of (P, M ). We also call the running time of the algorithm computing M , measured as a function of κ(x), decoding time of (P, M ). We can readily observe that parameterized function problem has an FPT-algorithm if and only if there is a compactor for it.

Up to our best knowledge, the notion of compactor as formalized in this paper is new. As discussed in Subsection 1.1, similar notions have been proposed such as counting kernelization [START_REF] Thurley | Kernelizations for parameterized counting problems. In 4th international conference on Theory and applications of models of computation[END_REF] and compactor enumeration [START_REF] Díaz | Efficient algorithms for counting parameterized list H-colorings[END_REF]. In both counting kernelization and compact enumeration, a mapping from the set of all certificates to certain objects in the new instance is required. While this approach comply more with the idea of classic kernelization, it seems to be more restrictive. The main difference of our compactor from the previous notions is that (the condenser of) a compactor is free of this requirement, which makes the definition more flexible and easier to work with. Due to this flexibility and succinctness, we believe that our notion might be amenable for lower bound machineries akin to those for decision problem kernelizations.

Parameterized counting problems on graphs.

A structure is a pair (G, A) where G is a graph and A ⊆ V (G). Given a MSOL-formula φ on structures and some graph class G, we consider the following parameterized counting problem Π φ,G .

Π φ,G Input: a graph G ∈ G, an non-negative integer k. Parameter: k. Count: the number of vertex sets A ⊆ V (G) such that (G, A) |= φ and |A| = k. We say that an instance (G, k) ∈ G × N of Π φ,G is a null instance if it has no solutions. Given a graph G, we say that a vertex set A ⊆ V (G) is a t-treewidth modulator of G if the removal of A from G
leaves a graph of treewidth at most t. Given an MSOL-formula φ and a graph class G, we say that Π φ,G is treewidth modulable if there is a constant t (depending on φ and G only) such that, for every non-null instance (G, k) of Π φ,G , G has a t-treewidth modulator of size at most t • k.

Let F H be the class of all graphs that do not contain a subdivision of H as a subgraph. The next theorem states our main result.

Theorem 1. For every graph H and every MSOL

-formula φ, if Π φ,F H is treewidth modulable, then there is a compactor for Π φ,F H of size O(k 2 ) with condensing time O(k 2 n 2 ) and decoding time 2 O(k) .
As a corollary of the main theorem we have the following.

20:5 Corollary 2. For every graph H and every MSOL

-formula φ, if Π φ,F H is treewidth mod- ulable, then Π φ,F H can be solved in O(k 2 n 2 ) + 2 O(k) steps.
In the above results, the constants hidden in the O-notation depend on the choice of φ, on the treewidth-modulability constant t, and on the choice of H.

Recall that the above results are stated using the UCM model. As for Π φ,F H , the number of solutions is O(n k ) and this number can be encoded in O(k log n) bits. Assuming that summations of two r-bit numbers can be done in O(r) steps and multiplications of two r-bit numbers can be done in O(r 2 ) steps, then the size of the compactor in Theorem 1 is O(k 2 log n) the condensing and extracting times are O(k 4 n 2 log 2 n) and 2 O(k) log 2 n respectively. Consequently, the running time of the algorithm in Corollary 2 is

O(k 4 n 2 log 2 n) + 2 O(k) log 2 n.
Coming back to the algorithmic meta-theorems on parameterized counting problems we should remark that the problem condition of Corollary 2 is weaker than MSOL, as it additionally demands treewidth-modulability. However, the graph classes where this result applies have unbounded treewidth or rankwidth. That way our results can be seen as orthogonal to those of [START_REF] Courcelle | On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic[END_REF].

On the side of FOL, the problem condition of Corollary 2 is stronger than FOL, while its combinatorial applicability includes planar graphs or graphs of bounded genus where, the existing algorithmic meta-theorems require FOL-expressibility (see [START_REF] Frick | Generalized Model-Checking over Locally Tree-Decomposable Classes[END_REF]).

Outline of the compactor algorithms

Our approach follows the idea of applying data-reduction based on protrusion decomposability. This idea was initiated in [START_REF] Hans | Meta) Kernelization[END_REF] for the automated derivation of polynomial kernels on decision problems. The key-concept in [START_REF] Hans | Meta) Kernelization[END_REF] is the notion of a protrusion, a set of vertices with small neighborhood to the rest of the graph and inducing a graph of small treewidth. Also, [START_REF] Hans | Meta) Kernelization[END_REF] introduced the notion of a protrusion decomposition, which is a partition of G to O(k) graphs such the first one is a "center", of size O(k), and the rest are protrusions whose neighborhoods are in the center.

The meta-algorithmic machinery of [START_REF] Hans | Meta) Kernelization[END_REF] is based on the following combinatorial fact: for the problems in question, YES-instances -in our case non-null instances-admit a protrusion decomposition that, when the input has size Ω(k), one of its protrusions is "big enough". This permits the application of some "graph surgery" that consists in replacing a big protrusion with a smaller one and, that way, creates an equivalent instance of the problem (the replacements are based on the MSOL-expressibiliy of the problem). In the case of counting problems, this protrusion replacement machinery does not work (at least straightforwardly) as we have to keep track, not only of the way some part of a solution "invades" a protrusion, but also of the number of all those partial solutions. Instead, we take another way that avoids stepwise protrusion replacement. In our approach, the condenser of the compactor first constructs an approximate protrusion decomposition, then, it computes how many possible partial solutions of all possible sizes may exist in each one of the protrusions. This computation is done by dynamic programming (see Section 4) and produces a total set of O(k 2 ) arithmetic values. These values, along with the combinatorial information of the center of the protrusion decomposition and the neighborhoods of the protrusions in the center, constitutes the output of the condenser. This structure can be stored in O(k 2 ) space (given that arithmetic values can be stored in constant space) and contains enough information to obtain the number of all the solutions of the initial instance in 2 O(k) steps (Section 4).

We stress that the above machinery demands the polynomial-time construction of a constant-factor approximation of a protrusion-decomposition. To our knowledge, this remains an open problem in general. So far, no such algorithm has been proposed, even for particular I S A A C 2 0 1 8

20:6

Data-Compression for Parametrized Counting Problems on Sparse Graphs graph classes, mostly because meta-kernelization machinery in [START_REF] Hans | Meta) Kernelization[END_REF] (and later in [START_REF] Fedor | Bidimensionality and Kernels[END_REF][START_REF] Fomin | Bidimensionality and Kernels[END_REF][START_REF] Jung | Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions[END_REF][START_REF] Fedor | Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms[END_REF]) is based on stepwise protrusion replacement and does not actually need to construct such a decomposition. Based on the result in [START_REF] Jung | Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions[END_REF], we show that that the construction of such an approximate protrusion decomposition is possible on H-topological-minor-free graphs, given that it is possible to construct an approximate t-treewidth modulator of G. In fact, this can been done in general graphs using the randomized constant-factor approximation algorithm in [START_REF] Fedor | Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms[END_REF]. Responding to the need for a deterministic approximation we provide a constantfactor approximation algorithm that finds a t-treewidth modulator on H-topological-minor free graphs (Section 3). This algorithm runs in O(k 2 n 2 ) steps and, besides from being a necessary step of the condenser of our compactor, is of independent algorithmic interest.

Preliminaries

We use N to denote the set of all non-negative integers. Let χ : N 2 → N and ψ : Given a graph G, a subdivision of G is any graph that is obtained from G after replacing its edges by paths with the same endpoints. We say that a graph H is a topological minor of G if G contains as a subgraph some subdivision of H. We also say that G is H-topological-minor-free if it excludes H as a topological minor.

N → N. We say that χ(n, k) = O k (ψ(n)) if there exists a function φ : N → N such that χ(n, k) = O(φ(k) • ψ(n)).

Boundaried structures. A labeling of a graph G is any injective function

λ : V (G) → N.

Given a structure (G, A), we call A the annotated set of (G, A) and the vertices in A annotated vertices of (G, A).

A boundaried structure, in short a b-structure, is a triple G = (G, B, A) where G is a graph and B, A ⊆ V (G). We say that B is the boundary of G and A is the annotated set of G. Also we call the vertices of B boundary vertices and the vertices in A annotated vertices. We use notation B (t) to denote all b-structures whose boundary has at most t vertices. We set

G(G) = G, V (G) = V (G), B(G) = B, A(G) = A.
We refer to G as the underlying graph of G and we always assume that the underlying graph of a b-structure is accompanied with some labelling λ. Under the presence of such a labelling, we define the index of a boundary vertex v as the quantity |{u ∈ B | λ(u) ≤ λ(v)}| i.e., the index of v when we arrange the vertices of B according to λ in increasing order. We extend the notion of index to subsets of B in the natural way, i.e., the index of S ⊆ B consists of the indices of all the vertices in S.

A boundaried graph, in short b-graph, is any b-structure G = (G, B, A) such that A = V (G). For simplicity we use the notation G = (G, B, -) to denote b-graphs instead of using the heavier notation G = (G, B, V (G)). For every t ∈ N, we use B (t) to denote the b-graphs in B (t) . We avoid denoting a boundary graph as an annotated graph as we want to stress the role of B as a boundary.

We say that two b-structures

G 1 = (G 1 , B 1 , A 1 ) and G 2 = (G 2 , B 2 , A 2 ) are compatible, denoted by G 1 ∼ G 2 , if A 1 ∩ B 1 and A 2 ∩ B 2 have the same index and the labeled graphs G[B 1 ] and G[B 2 ]
, where each vertex of B i is labeled by its index, are identical.

Given two compatible b-structures

G 1 = (G 1 , B 1 , A 1 ) and G 2 = (G 2 , B 2 , A 2 ), we define G 1 ⊕ G 2 as the structure (G, A)
where the graph G is obtained by taking the disjoint union of G 1 and G 2 and then identifying boundary vertices of G 1 and G 2 of the same index, and the vertex set A is obtained from A 1 and A 2 after identifying equally-indexed vertices in

A 1 ∩ B 1 and A 2 ∩ B 2 . Keep in mind that (G, A) = G 1 ⊕ G 2 is
an annotated graph and not a b-structure. We always assume that the labels of the boundary of G 1 prevail during the gluing operation, i.e., they are inherited to the identified vertices in (G, A) while the labels of the boundary of G 2 dissapear in (G, A). Especially, when G 1 and G 2 are compatible b-graphs, we treat G 1 ⊕ G 2 as a graph for notational simplicity.

Treewith of b-structures. Given a b-structure G = (G, B, A), we say that the triple D = (T, χ, r) is a tree decomposition of G if (T, χ) is a tree decomposition of G, r ∈ V (T ), and χ(r) = B. We see T as a tree rooted on r. The width of a tree decomposition D = (T, χ, r) is the width of the tree decomposition (T, χ). The treewidth of a b-structure G is the minimum width over all its tree decompositions and is denoted by tw(G). We use T (t) (resp. T

X i = V (G i ) \ B i , i ∈ [s], it holds that 1. s ≤ α 2. ∀i ∈ [s], G i ∈ T (β) 3. ∀i ∈ [s], G i is a subgraph of G 4. ∀i, j ∈ [s], i = j ⇒ X i ∩ X j = ∅ 5. |V (G) \ i∈[s] X i | ≤ α 6. ∀i ∈ [s], tw(G[X i ]) ≤ γ.
We cal the set V (G) \ i∈[s] X i center of the above (α, β, γ)-protrusion decomposition. Protrusion decompositions have been introduced in [START_REF] Hans | Meta) Kernelization[END_REF] in the context of kernelization algorithms (see also [START_REF] Fedor | Bidimensionality and Kernels[END_REF][START_REF] Fomin | Bidimensionality and Kernels[END_REF]). The above definition is a modification of the original one in [START_REF] Hans | Meta) Kernelization[END_REF], adapted for the needs of our proofs. The only essential modification is the parameter γ, used in the last requirement. Intuitively, γ bounds the "internal" treewidth of each protrusion B i .

Equivalence on boundaried structures.

(Counting) Monadic Second Order Logic. We say that a MSOL-formula φ is a formula on structures if it has a free variable corresponding to a set of vertices. A structure G = (G, A) is a model for such a formula φ, we write this G |= φ, if it becomes true on G when instantiating the free variable of φ by the set A. Given a MSOL-formula φ we denote by |φ| the length of the formula.

20:8

Data-Compression for Parametrized Counting Problems on Sparse Graphs

Equivalences between b-structures and b-graphs. Let φ be a MSOL-formula and t ∈ N.

Given two b-structures G 1 , G 2 ∈ B (t) , we say that G 1 ≡ φ,t G 2 if G 1 ∼ G 2 and ∀F ∈ B (t) F ∼ G 1 ⇒ (F ⊕ G 1 |= φ ⇐⇒ F ⊕ G 2 |= φ) Notice that ≡ φ,t
is an equivalence relation on B (t) . The following result is widely known as Courcelle's theorem and was proven [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF]. The same result was essentially proven in [START_REF] Borie | Automatic Generation of Linear-Time Algorithms from Predicate Calculus Descriptions of Problems on Recursively Constructed Graph Families[END_REF] and [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF]. The version on structures that we present below appeared in [4, Lemma 3.2.]. Proposition 3. There exists a computable function ξ : N 2 → N such that for every CMSOformula φ and every t ∈ N, the equivalence relation ≡ φ,t has at most ξ(|φ|, t) equivalence classes.

Given a MSOL-formula φ and under the light of Proposition 3, we consider a (finite) set R φ,t containing one minimum-size member from each of the equivalence classes of ≡ φ,t . Keep in mind that R φ,t ⊆ B (t) . Notice that for every G ∈ B (t) , there is a b-structure in R φ,t , we denote it by rep φ,t (G), such that rep φ,t (G) ≡ φ,t G.

Approximating protrusion decompositions

The main result of this section is a constant-factor approximation algorithm computing a ttreewidth modulator (Lemma 5). Based on this we also derive a constant-factor approximation algorithm for a protrusion decomposition (Theorem 6). For our proofs we need the following lemma that is a consequence of the results in [START_REF] Jung | Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions[END_REF].

Lemma 4.

For every h-vertex graph H and every t ∈ N, there exists a constant c and an algorithm that takes as input an H-topological-minor-free graph G and a t-treewidth modulator X ⊆ V (G) and outputs a (c|X|, c, t)-protrusion decomposition along with tree decompositions of its b-graphs of width at most c, in O h+t (n) steps.

As a consequence of Lemma 4, as long as the input graph G has many vertices (linear in k), there is a vertex set Y whose (internal) treewidth is at most t and contains sufficiently many vertices. The key step of the approximation algorithm, to be shown in the next lemma, is to replace N [Y ] with a smaller graph of the same 'type'. Two conditions are to be met during the replacement: first, the minimum-size of a t-treewidth modulator remains the same. Secondly, a t-treewidth modulator of the new graph can be 'lifted' to a t-treewidth modulator of the graph before the replacement without increasing the size.

Lemma 5.

For every h-vertex graph H and every t, there is a constant c, depending on h and t, and an algorithm that, given a graph G ∈ F H and k ∈ N, either outputs an t-treewidth-modulator of G of size at most c • k or reports that no t-treewidth modulator of G exists with size at most k. This algorithm runs in O h+t (n 2 ) steps.

Notice that the above lemma, with worst running time, is also a consequence of the recent results in [START_REF] Gupta | Losing treewidth by separating subsets[END_REF]. We insist to the above statement of Lemma 5, as we are interested for a quadratic time approximation algorithm for protrusion decompositions. Indeed, based on Lemma 5 we can prove the following that is the main result of this section. Theorem 6. Let H be an h-vertex graph and φ be a MSOL-formula that is treewidth modulable. Then there is a constant c, depending on h and |φ|, and an algorithm that, given an input (G, k) of Π φ,F H , either reports no A ⊆ V (G) with (G, A) |= φ has size at most k or outputs a (ck, c, c)-protrusion decomposition of G along with tree decompositions of its b-graphs, each of width at most c. This algorithm runs in O |φ|+h (n 2 ) steps.

4

The compactor

By Theorem 6, we may assume that a (tk, t, t)-protrusion decomposition G 1 , . . . , G s of G, with G i = (G i , B i , -), is given for some t. For counting the sets A ⊆ V (G) of size at most k with (G, A) |= φ, we view such a set A as a union of A 0 ∪ A 1 ∪ • • • A s , where A 0 is the subset of A residing in the the center of the decomposition, and

A i = A ∩ V (G i ) for each i ∈ [s]. Suppose that A i ⊆ V (G i ) for some i ∈ [s] satisfies (G i , B i , A i ) ≡ φ,t (G i , B i , A i ) and |A i | = |A i |.
Then, (A \ A i ) ∪ A i has the same size as |A| and we have (G,

A \ A i ∪ A i ) |= φ.
In other words, A i and A i are indistinguishable when seen from outside of G i .

The basic idea of the condenser is to replace all the occurrences of such sets A i (include A i itself) with O(1)-bit information; that is, the number of such sets, the size of |A i |, and the equivalence class containing (G i , B i , A i ). Formally, for the given CMSO-formula φ and t ∈ N, we define the function #sol φ,t so that for each R ∈ R φ,t , G := (G, B, -) ∈ T (t) , we set

#sol φ,t (R, G, k) = |{A ∈ V (G) k | R ≡ φ,t (G, B, A)}|.
This function can be fully computed in linear time on a b-graph of bounded treewidth.

Lemma 7.

For every CMSO-formula φ and every t ∈ N, there exists an algorithm that, given a G ∈ T (t) and a tree decomposition of G of width at most t, outputs #sol φ,t (R, G, k )

for every (R, k ) ∈ R φ,t × [0, k]. This computation takes O |φ|,t (nk 2 ) steps.
The proof of Lemma 7 is based on a dynamic programming procedure. This may follow implicitly from the proofs of Courcelle's theorem (see [START_REF] Courcelle | Monadic second-order evaluations on tree-decomposable graphs[END_REF][START_REF] Courcelle | On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic[END_REF]).

We are now in position to prove Theorem 1.

Proof of Theorem 1. We describe a polynomial size compactor (P, M) for Π φ,F H . Given an input (G, k) ∈ F H × N, the condenser P of the compactor runs as a first step the algorithm of Theorem 6. If this algorithm reports that there is no set A of size k with (G, k) |= φ, the the condenser outputs $, i.e., A(G, k) = $. Suppose now that the output is a (tk, t, t)-protrusion decomposition G 1 , . . . , G s of G, along with the corresponding tree decompositions, for some constant t that depends only on h and |φ|. Let K be the center of this protrusion decomposition and recall that |K|, s ≤ tk. We set G 0 = G[K] and let

G i = (G i , B i , -) for each i ∈ [s]. We also define B = {B i , | i ∈ [s]} where B i is the boundary of G i , i ∈ [s]
. The next step of the condenser is to apply the algorithm of Lemma 7 and compute

#sol φ,t (R, G i , k ) for every (R, k , i) ∈ R φ,t × [0, k] × [s], in O |φ|+h (nk 2 ) steps. The output of the condenser P is P(G, k) = (G 0 , B, {#sol φ,t (R, G i , k ) | (R, k , i) ∈ R φ,t × [0, k] × [s]}).
Clearly, P(G, k) can be encoded in O |φ|+h (k 2 ) memory positions. We next describe the extractor M of the compactor. For simplicity, we write z := P(G, k) and we define M($) = 0. We assume that there is a fixed labeling λ of G 0 . The extractor M first computes the set A containing all subsets of K of at most k vertices. Notice that |A| = 2 O |φ|+h (k) . Next, for each A 0 ∈ A, the algorithm builds the set M A0 containing all mappings m : [s] → R φ,t with the property that, for every i ∈

[s], (G 0 , B i , A 0 ) ∼ m(i).
As the boundary of m(i) induces an identical labeled graph as B i does, we denote m

(i) as (G m i , B i , A m i ). Notice that |M A0 | = 2 O |φ|+h (k) , for every A 0 ∈ A. Let A 0 ∈ A
sets D m i+1 = ((D i , B i+1 , -) ⊕ (G m i+1 , B i+1 , -), j∈[i+1] A m j ) iteratively from i = 0 up to s -1. We set (D m , A m ) = D m s . Notice that the routine runs in O |φ|+h (k) steps and that |D m | = O |φ|+h (k).
The extractor M is defined as

M(z) = A0∈A m∈M A 0 [(D m , A m ) |= φ] • ζ∈K k-|A 0 | i∈[s] #sol φ,t (m(i), G i , ζ(i) + |B i ∩ A 0 |)
where

m i ≡ φ,t (G i , B i , A ) ensure that (G, A 0 ∪ i∈[s] A i ) |= φ. Observe that |A 0 ∪ i∈[s] A i | = |A 0 | + i∈[s] |A i \ B i | = |A 0 | + i∈[s] |A i | = |A 0 | + i∈[s] ζ(i) = k.
That is, each combination of A 0 , m, ζ, and a sequence A 1 , . . . , A s contributing 1 to the sum M(z), a vertex set A of size precisely k can be uniquely defined and we have (G, A) |= φ. Clearly, distinct combinations lead to distinct such sets. Therefore, |{A ∈ V (G) k | (G, A) |= φ}| is at least the value of M(z). This completes the proof.

Conclusions

Concerning Theorem 1, we stress that the treewidth-modulability condition can be derived by other meta-algorithmic conditions. Such conditions are minor/contraction bidimensionality and linear separability for graphs excluding a graph/apex graph as a minor [START_REF] Fomin | Bidimensionality and Kernels[END_REF][START_REF] Fedor | Bidimensionality and Kernels[END_REF]. This extends the applicability of our meta-algorithmic result to more problems but in more restricted graph classes. Natural follow-up questions are whether the size of the compactor can be made linear and whether its combinatorial applicability can be extended to more general graph classes.

We envision that the formal definition of a compactor that we give in this paper may encourage the research on data-reduction for counting problems. The apparent open issue is whether other problems (or families of problems) may be amenable to this data-reduction paradigm (in particular, the results in [START_REF] Díaz | Efficient algorithms for counting parameterized list H-colorings[END_REF][START_REF] Nishimura | Parameterized Counting Algorithms for General Graph Covering Problems[END_REF][START_REF] Thurley | Kernelizations for parameterized counting problems. In 4th international conference on Theory and applications of models of computation[END_REF][START_REF] Thurley | Tractability and Intractability of Parameterized Counting Problems[END_REF] can be interpreted as results on polynomial compactors).

Another interesting question is whether (and to which extent) the fundamental complexity results in [START_REF] Chen | Lower Bounds for Kernelizations and Other Preprocessing Procedures[END_REF][START_REF] Hans | On problems without polynomial kernels[END_REF][START_REF] Fortnow | Infeasibility of instance compression and succinct PCPs for NP[END_REF][START_REF] Dell | AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations[END_REF][START_REF] Hans | Kernelization Lower Bounds by Cross-Composition[END_REF][START_REF] Drucker | New Limits to Classical and Quantum Instance Compression[END_REF][START_REF] Harnik | On the Compressibility of NP Instances and Cryptographic Applications[END_REF] on the non-existence of polynomial kernels may have their counterpart for counting problems.

2 . 1

 21 Given a, b ∈ N, we define by [a, b] = {a, . . . , b}. Also, given some a ∈ N we define [a] = {1, . . . , a}. Given a set Z and a k ∈ N, we denote Z k = {S ⊆ Z | |S| = k}. Graphs and boundary graphs Graphs. All graphs in this paper are simple and undirected. Given a graph G, we use V (G) to denote the set of its vertices. Given a S ⊆ V (G) we denote by N G (S) the set of all neighbours of S in G that are not in S. We also set N G [S] = S ∪ N G (S) and we use N (S) and N [S] as shortcuts of N G (S) and N G [S] (when the index is a graph denoted by G). We define G -S as the graph obtained from G if we remove the vertices in S, along with the edges incident to them. The subgraph of G induced by S is the graph G[S] := G -(V (G) \ S). Finally, we set ∂ G (S) = N G (V (G -S)). We call |V (G)| the size of a graph G and n is reserved to denote the size of the input graph for time complexity analysis.

  (t) ) to denote all b-structures (resp. b-graphs) in B (t) (resp. B(t) ) with treewidth at most t.Protrusion decompositions.Let G be a graph. Given α, β, γ ∈ N, an (α, β, γ)-protrusion decomposition of G is a sequence of G 1 = (G 1 , B 1 , -), . . . , G s = (G s , B s , -) of b-graphs where, given that

  and m ∈ M A0 . For each such pair, the extractor runs a routine that constructs an annotated graph (D m , A m ) as follows: first it initializesD m 0 = (D 0 , A m 0 ) with D 0 = G 0 and A m 0 = A 0 . After constructing D m i = (D i , j∈[i] A m j ), the routine

  [•] is a function indicating whether a sentence is true (=1) or false (=0), andK -|A0| is the set of all vectors ζ ∈ [0, k] s such that i∈[s] ζ(i) = -|A 0 |. Having access to {#sol φ,t (R, G i , k ) | (R, k , i) ∈ R φ,t × [0, k] × [s]}, we can compute M(z) in 2 O |φ|+h (k) steps. Therefore, the extractor runs in the claimed running time. It remains to prove that M(z) equals |{A ∈ V (G) k | (G, A) |= φ}|.Before proceeding, we present a key claim (for the proof, see the full version of the paper).Claim 8. Let H i = (H i , B, A i ) for i = 1, 2 be two compatible b-structures from B (t) . Let H 2 = (H 2 , B, A 2 ) be a b-structure equivalent with H 2 .Then for every B ⊆ V (H 1 ) of size at most t, the two b-structures D and D are equivalent under ≡ φ,t , whereD = ((H 1 , B, -)⊕(H 2 , B, -), B , A 1 ∪A 2 ) and D = ((H 1 , B, -)⊕(H 2 , B, -), B , A 1 ∪A 2 )Now, consider an arbitrary sequence A 1 , . . . , A s of vertex sets withA i ⊆ V (G i ), each of which is counted in #sol φ,t (m(i), G i , ζ(i) + |B i ∩ A 0 |).Claim 8, [(G m , A m ) |= φ] = 1, and

Supported by project ESIGMA (ANR-17-CE23-0010). 2 Partially funded by MINECO and FEDER funds under grants TIN2017-86727-C2-1-R (GRAMM) and MDM-2014-044 (BGSMath), and by AGAUR grant 2017SGR-786 (ALBCOM). 3 Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).