Édouard Bonnet

Eun Jung Kim

Amadeus Reinald

Stéphan Thomassé

Rémi Watrigant

Twin-width and polynomial kernels

Keywords: 2012 ACM Subject Classification Theory of computation, kernelization, lower bounds, Dominating Set

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The twin-width of a graph can be defined in the following way. A partition sequence of an n-vertex graph G, is a sequence P n , . . . , P 1 of partitions of its vertex set V (G), such that P n is the set of singletons {{v} : v ∈ V (G)}, P 1 is the singleton set {V (G)}, and for every 2 ⩽ i ⩽ n, P i-1 is obtained from P i by merging two of its parts into one. Two parts P, P ′ of a same partition P of V (G) are said homogeneous if either every pair of vertices u ∈ P, v ∈ P ′ are non-adjacent, or every pair of vertices u ∈ P, v ∈ P ′ are adjacent. Finally the twin-width of G is the least integer d such that there is partition sequence P n , . . . , P 1 of G with every part of every P i (1 ⩽ i ⩽ n) being homogeneous to every other parts of P i but at most d. We call such a partition sequence a d-sequence.

On the one hand, a surprisingly wide variety of graphs have low twin-width. Graph classes with bounded twin-width include classes with bounded treewidth, or even rankwidth, proper minor-closed classes, every hereditary proper subclass of permutation graphs, bounded-degree string graphs [START_REF] Bonnet | Twin-width I: tractable FO model checking[END_REF], classes with bounded queue or stack number, some expander families [START_REF] Bonnet | Twin-width II: small classes[END_REF]. Furthermore on those particular classes, we can find (non necessarily optimum) O(1)-sequences in polynomial time. We observe that such an approximation algorithm is still missing in general graphs, but exists for ordered binary structures [START_REF] Bonnet | Twin-width IV: ordered graphs and matrices[END_REF].

On the other hand, bounded twin-width classes have interesting algorithmic and structural properties. Remarkably, given a partition sequence witnessing that an n-vertex graph G has twin-width at most d, and a first-order sentence φ, one can decide if φ holds in G in time f (|φ|, d) n for a computable, but non-elementary, function f [START_REF] Bonnet | Twin-width I: tractable FO model checking[END_REF]. That general framework is called first-order model checking, and generalizes problems like k-Independent Set with φ = ∃x 1 . . . ∃x k 1⩽i<j⩽k ¬(x i = x j ∨ E(x i , x j )) and k-Dominating Set with φ = ∃x 1 . . . ∃x k ∀x 1⩽i⩽k (x = x i ∨ E(x, x i )). For these two particular problems, though, a much better running time of 2 O d (k) n is possible [START_REF] Bonnet | Twin-width III: Max Independent Set and Coloring[END_REF]. In contrast, an algorithm running in time f (k)n o (k) for either of these problems on general graphs, with f being any computable function, would imply the improbable (or at least breakthrough) result that 3-SAT can be solved in subexponential time [START_REF] Chen | Strong computational lower bounds via parameterized complexity[END_REF]. Now we know that k-Independent Set and k-Dominating Set are fixed-parameter tractable (FPT), i.e., solvable in time f (k) n O (1) , on graphs of bounded twin-width given with an O(1)-sequence, one can then ask whether polynomial kernels exist. A kernel is a polytime algorithm that produces, given an instance of a parameterized problem Π, an equivalent instance of Π (i.e., the output is a YES-instance if and only if the input is a YES-instance) of size only function of the parameter. A polynomial kernel is a kernel for which the latter function is polynomial. Any decidable problem with a kernel is FPT, and any FPT problem admits a kernel. However not every FPT problem is believed to have a polynomial kernel. And indeed such an outcome would imply an unlikely collapse of complexity classes.

We already observed that there is a constant d such that k-Independent Set is highly unlikely to have a polynomial kernel on graphs with twin-width at most d [START_REF] Bonnet | Twin-width III: Max Independent Set and Coloring[END_REF]. The ORcomposition 1 is straightforward from the following facts: [START_REF] Alber | Polynomial-time data reduction for dominating set[END_REF] cliques have twin-width 0 and planar graphs have bounded twin-width [START_REF] Bonnet | Twin-width I: tractable FO model checking[END_REF], [START_REF] Alon | Linear time algorithms for finding a dominating set of fixed size in degenerated graphs[END_REF] the twin-width of every graph is the maximum twin-width of its modules and quotient graph (see Lemma 9), and (3) Maximum Independent Set is NP-hard in (subcubic) planar graphs [START_REF] Garey | Some simplified np-complete graph problems[END_REF]. Then one can blow every vertex of a clique K t into a distinct graph among t planar Maximum Independent Setinstances. Facts (1) and [START_REF] Alon | Linear time algorithms for finding a dominating set of fixed size in degenerated graphs[END_REF] imply that the constructed graph has bounded twin-width, while the correctness of the OR-composition is easy to check. Incidentally the exact same reduction rules a polynomial kernel out for k-Independent Dominating Set. Furthermore Minimum Independent Dominating Set is NP-hard in grid graphs [START_REF] Clark | Unit disk graphs[END_REF], and Maximum Independent Set is NP-hard in subdivisions of grid graphs (since these coincide with planar graphs of degree at most 4). Since these graphs have twin-width at most 4 (see Lemma 10), no polynomial kernel is likely to exist for both problems (even when a 4-sequence is given in the input). It should be noted that this simple reduction fails for k-Dominating Set: one can dominate the constructed graph by picking only two vertices (from two distinct instances).

The parameterized complexity (FPT algorithms and kernels) of k-Dominating Set 2 on "sparse" 3 classes has a rich and interesting history. Subexponential FPT algorithms with running time 2 O( √ k) n O (1) are known in planar graphs [START_REF] Fedor | Dominating sets in planar graphs: Branchwidth and exponential speed-up[END_REF][START_REF] Dorn | Dynamic programming and fast matrix multiplication[END_REF], bounded-genus graphs and more generally classes excluding a fixed minor [START_REF] Demaine | Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs[END_REF][START_REF] Fedor | Kernels for (connected) dominating set on graphs with excluded topological minors[END_REF][START_REF] Gutner | Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor[END_REF], and an FPT algorithm with running time 2 O(k) n exists in classes excluding a fixed topological minor [START_REF] Alon | Linear time algorithms for finding a dominating set of fixed size in degenerated graphs[END_REF]. On these classes the mere existence of an FPT algorithm (but not the particular, enhanced running time) is subsumed by an algorithmic meta-theorem of Grohe, Kreutzer, and Siebertz [START_REF] Grohe | Deciding first-order properties of nowhere dense graphs[END_REF] that says that first-order model checking is FPT in any nowhere dense class. 4 More general than nowhere dense classes are bounded-degeneracy graphs, or further, K t,t -free classes, i.e., excluding the biclique K t,t as a subgraph. Alon and Gutner [START_REF] Alon | Linear time algorithms for finding a dominating set of fixed size in degenerated graphs[END_REF] give an FPT algorithm in d-degenerate graphs running in time k O(dk) n. And Philip, Raman, and Sikdar [START_REF] Philip | Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond[END_REF] extend the fixed-parameter tractability of k-Dominating Set to any K t,t -free class (for a fixed t). Telle and Villanger [46] further show that k-Dominating Set on K t,t -free graphs is FPT for the combined parameter k + t.

In parallel to these algorithms, the existence of polynomial, or even linear, kernels have been thoroughly investigated. In 2004, Alber, Fellows, and Niedermeier [START_REF] Alber | Polynomial-time data reduction for dominating set[END_REF] presented a linear kernel for k-Dominating Set on planar graphs that triggered a series of works. Linear kernels are known on planar graphs [START_REF] Alber | Polynomial-time data reduction for dominating set[END_REF][START_REF] Chen | Parametric duality and kernelization: Lower bounds and upper bounds on kernel size[END_REF], bounded-genus graphs [START_REF] Fedor | Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up[END_REF], apex-minorfree graphs [START_REF] Fedor | Bidimensionality and kernels[END_REF], but more generally in any class excluding a fixed topological minor [START_REF] Fedor | Kernels for (connected) dominating set on graphs with excluded topological minors[END_REF]. k-Dominating Set admits a polynomial kernel on graphs of girth 5 (that is, excluding the triangle and the biclique K 2,2 as a subgraph) [START_REF] Raman | Short Cycles Make W -hard Problems Hard: FPT Algorithms for W -hard Problems in Graphs with no Short Cycles[END_REF]. A polynomial kernel of size O(k (t+1) 2 ) is obtained for K t,t -free graphs [START_REF] Philip | Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond[END_REF], the most general "sparse" class. Contrary to the FPT algorithm, a polynomial kernel in the parameter k + t is highly unlikely [START_REF] Dom | Kernelization Lower Bounds Through Colors and IDs[END_REF]. More precisely, for any ε > 0, a kernel of size k (t-1)(t-3)-ε would imply that coNP ⊆ NP/poly [START_REF] Cygan | Tight kernel bounds for problems on graphs with small degeneracy[END_REF]. On classes of bounded expansion5 k-Dominating Set has a linear kernel, while the seemingly closely related Connected k-Dominating Set has no polynomial kernel [START_REF] Grønås Drange | Kernelization and sparseness: the case of dominating set[END_REF]. The latter result refines a reduction showing the same lower bound on 2-degenerate graphs [START_REF] Cygan | Kernelization hardness of connectivity problems in d-degenerate graphs[END_REF].

Beyond sparse classes, for which most answers turn out positive, the parameterized complexity of k-Dominating Set seems to conceal many surprises, some of which recently unraveled. We already mentioned that k-Dominating Set is FPT on bounded twin-width graphs given with an O(1)-sequence. Let us also mention that the same problem is actually W [START_REF] Alber | Polynomial-time data reduction for dominating set[END_REF]-hard (hence unlikely FPT) on circle graphs [START_REF] Bousquet | Parameterized domination in circle graphs[END_REF]. This is somewhat unexpected since Dominating Set is polytime solvable on permutation graphs [START_REF] Farber | Domination in permutation graphs[END_REF], a large subclass of circle graphs. On the positive side, k-Dominating Set admits a polynomial kernel on so-called c-closed graphs [START_REF] Koana | Exploiting c-closure in kernelization algorithms for graph problems[END_REF], a far-reaching dense generalization of bounded d-degenerate graphs.

Our results.

We are back to wondering whether k-Dominating Set admits a polynomial kernel on graphs given with an O(1)-sequence. On the one hand, a polynomial kernel would "fit all the data points" considering that the examples of bounded twin-width classes previously given are either K t,t -free (and one concludes with [START_REF] Philip | Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond[END_REF]) or are dense classes on which Minimum Dominating Set is polytime solvable, like bounded rank-width graphs [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique-width[END_REF], and (subclasses of) permutation graphs [START_REF] Farber | Domination in permutation graphs[END_REF]. On the other hand, the same could be said of k-Independent Set for which we already ruled out such a kernel. Yet we will see in Section 3 that the above OR-composition not working for k-Dominating Set is part of a more general obstacle toward establishing its incompressibility. In the same section we lay down our plan to overcome that obstacle and show the following.

▶ Theorem 1. Unless coNP ⊆ NP/poly, k-Dominating Set on graphs of twin-width at most 4 does not admit a polynomial kernel, even if a 4-sequence of the graph is given.

We mentioned that the same statement holds much more directly for k-Independent Set and k-Independent Dominating Set. With analogous arguments, we can add k-Path, k-Induced Path, k-Induced Matching to the list. Local gadget modifications of the proof of Theorem 1 yield the same kernel lower bound for variants of k-Dominating Set such as Connected k-Dominating Set and Total k-Dominating Set, on graphs of bounded twin-width. More work would be necessary to get the lower bound for twin-width at most 4.

On the positive side, Connected k-Vertex Cover and Capacitated k-Vertex Cover admit polynomial kernels on graphs of bounded twin-width, while such kernels are unlikely on general graphs [START_REF] Dom | Kernelization Lower Bounds Through Colors and IDs[END_REF]. Interestingly, our kernelization algorithm does not require an O(1)-sequence.

▶ Theorem 2. Connected k-Vertex Cover and Capacitated k-Vertex Cover admit a kernel with O(k 2 ) vertices on any class of bounded twin-width.

A linear kernel (in the number of vertices) is known for apex-minor-free classes [START_REF] Fedor | Bidimensionality and kernels[END_REF] via the generic framework of bidimensionality, and even for topological-minor-free classes [START_REF] Jung | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF]. Another powerful meta-theorem by Gajarský et al. [START_REF] Gajarský | Kernelization using structural parameters on sparse graph classes[END_REF] says that every problem with the so-called finite integer index (intuitively, that its boundaried graphs provide finitely many distinct contexts) has a linear kernel on bounded expansion classes when parameterized by the vertex cover number (and more generally by the size of a smallest vertex subset whose deletion leaves the graph with bounded treedepth). In particular this yields a linear kernel for Connected k-Vertex Cover, further extending the two previous results. Besides Connected k-Vertex Cover has a polynomial kernel on K t,t -free graphs [START_REF] Cygan | Kernelization hardness of connectivity problems in d-degenerate graphs[END_REF].

Theorem 2 is based on the following useful lemma stating that, in graphs of bounded twin-width, the number of distinct neighborhood traces inside a subset of vertices is at most linear in the size of the subset.

▶ Lemma 3. There is a function f such that for every graph G of twin-width d and

X ⊆ V (G), the number of distinct neighborhoods in X, |{N (v) ∩ X : v ∈ V (G)}|, is at most f (d)|X|.
A more compact rewording, using the language of Vapnik-Chervonenkis parameters, is that the neighborhood set-system of graphs of bounded twin-width has VC density 1. By extension, we will say that a graph class has VC density at most 1, if its neighborhood hypergraphs do. That bounded twin-width classes have VC density 1 is an interesting property, that is shared with classes of bounded expansion. For example it implies a constant-factor approximation for Min Dominating Set (obtained in a rather different manner in [START_REF] Bonnet | Twin-width III: Max Independent Set and Coloring[END_REF]) via small ε-nets [START_REF] Chan | Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling[END_REF]. Lemma 3 was independently obtained by Wojciech Przybyszewski in his master thesis [44].

For Connected k-Vertex Cover, an improved kernel can be obtained with a more elaborate argument.

▶ Theorem 4. Connected k-Vertex Cover admits a kernel with O(k 1.5 ) vertices on classes with VC density at most 1.

Finally we extend cograph recognizability (cographs are exactly the graphs with twinwidth 0) and prove: 1 Kernelization results for arguably the three main problems without a polynomial kernel in general graphs, but an interesting story in sparse classes. PK stands for polynomial kernel, LK for linear kernel (in the number of vertices). The indicated lack of a kernel is under the assumption that coNP ⊆ NP/poly. Our new results are in bold (the results without a reference nor in bold are consequences of results in bold).

▶ Theorem 5
In case the input graph has indeed twin-width at most 1, a 1-sequence is found in polynomial time. Furthermore we observe that a wide class of graph problems is efficiently solvable on inputs of twin-width at most 1. See Table 1 for a summary of most of our results, together with the relevant pointers on other graph classes.

Preliminaries

We denote by [i, j] the set of integers {i, i + 1, . . . , j -1, j}, and by [i] the set of integers [1, i].

If X is a set of sets, we denote by ∪X their union. The notation O d (•) gives an asymptotic behavior when d is seen as a constant.

Graph theory

Unless stated otherwise, all graphs are assumed undirected and simple, that is, they do not have parallel edges or self-loops. We denote by V (G) and E(G), the set of vertices and edges, respectively, of a graph G. For S ⊆ V (G), we denote the open neighborhood (or simply neighborhood) of S by N G (S), i.e., the set of neighbors of S deprived of S, and the closed neighborhood of S by N G [S], i.e., the set N G (S) ∪ S. We simplify N G ({v}) into N G (v), and

N G [{v}] into N G [v].
We may omit the subscript when G is clear from the context. We denote by G[S] the subgraph of G induced by S, and

G -S := G[V (G) \ S]. An injective mapping η : V (H) → V (G) witnesses that H is a subgraph of G, if uv ∈ E(H) implies η(u)η(v) ∈ E(G). A bijective mapping η : V (H) → V (G) witnesses that H is a spanning subgraph of G, if uv ∈ E(H) implies η(u)η(v) ∈ E(G). A connected subset (or connected set) S ⊆ V (G) is one such that G[S] is connected. A dominating set is a set S ⊆ V (G) such that N [S] = V (G). A vertex cover is a set S ⊆ V (G)
such that every edge of G has at least one of its two endpoints in S. An independent set is a set S ⊆ V (G) such that G[S] is edgeless.

For two disjoint sets A, B ⊆ V (G), E(A, B) denotes the set of edges in E(G) with one endpoint in A and the other one in B. We also denote by G[A, B] the bipartite graph

(A ∪ B, E(A, B)). Two distinct vertices u, v such that N (u) = N (v)
⊆ V (G) is a module relative to Y ⊆ V (G) \ X if every vertex of Y is either fully adjacent to X or fully non-adjacent to X. Hence X is a module if it is a module relative to V (G) \ X.
The

: i < j, i ∈ [t], j ∈ [t], p ∈ [0, ℓ -1]}.
Informally it is the graph obtained from an ℓ-vertex cycle by replacing every edge by a strict half-graph of height t with a consistent, say, clock-wise orientation. See Figure 1 for an example of a 5-cycle of strict half-graphs of height 6. A strict half-graph is, for some natural t, the strict half-graph of height t. A cycle of strict half-graphs is, for some natural ℓ, the ℓ-cycle of strict half-graphs of same height.

The n × m grid is the graph with vertex set [n] × [m] and edges between any pair of vertices (x, y), (x + 1, y) or (x, y), (x, y + 1). A grid is an n × m grid for some integer n and m. A grid graph is an induced subgraph of a grid. To insist that we consider a grid and not a mere grid graph, we may use the term complete grid.

The neighborhood hypergraph of a graph G has vertex set V (G) and edge set

{N (v) : v ∈ V (G)}. A

Contraction sequences and twin-width

A trigraph G has vertex set V (G), black edge set E(G), and red edge set R(G), with E(G) and R(G) disjoint. The total graph of trigraph G is the graph

G ′ with V (G ′ ) = V (G) and E(G ′ ) = E(G) ∪ R(G). The subtrigraph of G induced by S is the trigraph H with V (H) = S, E(H) = E(G) ∩ S 2 , and R(H) = R(G) ∩ S 2 .
H is then called an induced subtrigraph of G. The set of neighbors N G (v) of a vertex v in a trigraph G consists of all the vertices adjacent to v by a black or red edge. A d-trigraph is a trigraph G such that the red graph (V (G), R(G)) has degree at most d. In that case, we also say that the trigraph has red degree at most d. A contraction or identification in a trigraph G consists of merging two (non-necessarily adjacent) vertices u and v into a single vertex z, and updating the edges of G in the following way. Every vertex of the symmetric difference N G (u)△N G (v) is linked to z by a red edge. Every vertex x of the intersection N G (u) ∩ N G (v) is linked to z by a black edge if both ux ∈ E(G) and vx ∈ E(G), and by a red edge otherwise. The rest of the edges (not incident to u or v) remain unchanged. See Figure 2 for an illustration. A d-sequence (or contraction sequence) is a sequence of d-trigraphs G n , G n-1 , . . . , G 1 , where G n = G, G 1 = K 1 is the graph on a single vertex, and G i-1 is obtained from G i by performing a single contraction of two (non-necessarily adjacent) vertices. We observe that G i has precisely i vertices, for every i ∈ [n]. The twin-width of G, denoted by tww(G), is the minimum integer d such that G admits a d-sequence. Note that, in what precedes, the initial structure G n = G may be a trigraph instead of a graph. Thus we defined twin-width more generally for trigraphs. Similarly a partial d-sequence from a n-vertex trigraph G to an

u 1 u 2 x 1 x 2 x 3 x 4 x 5 x 6 x 7 v 1 v 2 u v z u 1 u 2 x 1 x 2 x 3 x 4 x 5 x 6 x 7 v 1 v 2
i-vertex trigraph H is a sequence of d-trigraphs G = G n , G n-1 , . . . , G i = H. Observe that if
G has a partial d-sequence to H, and H has itself a d-sequence, then the concatenation of these sequences is a d-sequence for G.

We may give a (partial) contraction sequence by listing the pairs of vertices to contract: (u 1 , v 1 ), (u 2 , v 2 ), . . . where u i , v i are implicitly contracted to vertex s(u i ) ∪ s(v i ) with s(x) = x if x is a set of vertices and s(x) = {x} if x is a single vertex. Thus for instance u 2 could be equal to {u 1 , v 1 }.

For u ∈ V (G i ), we denote by u(G) the subset of V (G) that was contracted to the single vertex u in G n , G n-1 , . . . , G i . Twin-width and d-sequences can be equivalently seen as a partition refinement process on V (G). We start with the finest partition P n = {{v} : v ∈ V (G)}, and end with the coarsest partition P 1 = {V (G)}. There is a partition sequence P n , P n-1 , . . . , P 2 , P 1 mimicking the contraction sequence, where the contraction of u

, v ∈ V (G i ) corresponds to the merge of parts u(G i ), v(G i ) ∈ P i to form the part u(G i ) ∪ v(G i ) = z(G i-1 ) ∈ P i-1
, while all the other parts are unchanged from P i to P i-1 . The red degree (bounded by d) of a part P ∈ P i now corresponds to the number of other parts P ′ ∈ P i which are not fully adjacent nor fully non-adjacent to P in G. We may denote by G P the trigraph corresponding to partition

P over V (G). Thus G i = G Pi .
Given a partition H = {H 1 , H 2 , . . . , H ℓ } of the vertex set V (G) of a trigraph G, we call quotient trigraph G/H the trigraph obtained by contracting every H i into single vertices. Note that the resulting trigraph does not depend on the order in which the contractions are made. Thus the quotient trigraph is well-defined.

Useful twin-width bounds

It can be seen that the twin-width may only decrease when taking induced subtrigraphs.

▶ Observation 6. Let G be a trigraph and H be an induced subtrigraph of G. Then, tww(H) ⩽ tww(G).

The following observation states that turning some non-edges or black edges into red edges can only increase the twin-width.

▶ Observation 7. Let G, G ′ be two trigraphs such that V (G) = V (G ′ ), R(G) ⊆ R(G ′ ), E(G ′ ) ⊆ E(G), and R(G) ∪ E(G) ⊆ R(G ′ ) ∪ E(G ′ ). Then tww(G) ⩽ tww(G ′ ).
Proof. Indeed, any d-sequence for G ′ is a d-sequence for G. ◀

We will not need the next lemma in its particular form. Yet it yields some good insight on contraction sequences in general, and on the "core structure" of low twin-width used in the proof Theorem 1, in particular. Thus we give a short proof here.

▶ Lemma 8. Cycles of strict half-graphs have twin-width at most 3.

Proof. Consider G t , the ℓ-cycle of strict half-graphs of height t, on vertex set {a p 1 , . . . , a p t : p ∈ [0, ℓ -1]}. By Observation 7 we may prove the stronger statement that tww(G ′ t ) ⩽ 3 where

G ′ t is obtained from G t by adding the red edge a p 1 a p+1 mod ℓ 1 for every p ∈ [0, ℓ -1]. G ′
1 is a red cycle, and admits a 2-sequence by iteratively contracting the endpoints of any red edge. Therefore, we shall just check that the following is a partial 3-sequence from

G ′ t to G ′ t-1 : (a 0 1 , a 0 2 ), (a 1 1 , a 1 2 ), . . . , (a ℓ-1 1 , a ℓ-1 2 ). Indeed {a p 1 , a p 2 }
has, in the suggested partial sequence, at most three red neighbors:

a p-1 mod ℓ 1 , a p+1 mod ℓ 1
, and a p+1 mod ℓ 2 ; the latter two being a single vertex when p = ℓ -1. And all the other vertices have red degree at most 2. ◀

The next lemma was already invoked in the introduction. We will use its essence in a more general form in Section 5.1, namely that contracting vertices from a module X relative to Y do not create red edges incident to Y . ▶ Lemma 9. Let G be a graph and H = {H 1 , H 2 , . . . , H ℓ } be its modular partition. Then,

tww(G) = max{max i∈[ℓ] tww(H i ), tww(G/H)}.
Proof. Consider a sequence which contracts each module H i into a single vertex, followed by a contraction sequence of G/H attaining tww(G/H). Contracting each module H i creates red edges only within the module H i , thus G/H has red degree 0. Hence, tww(G) is upper bounded by the twin-widths of

G[H 1 ], G[H 2 ], . . . , G[H ℓ ],
and G/H. The other inequality follows from Observation 6, since G/H is also an induced subgraph of G. ◀ Finally we will use the following lemma to finish our 4-sequences.

▶ Lemma 10. Any trigraph whose total graph is a subdivision of a subgraph of a grid has twin-width at most 4.

Proof. By Observation 7, we may assume that the given trigraph is a subdivision of a complete grid consisting of red edges only. By contracting every adjacent pair of vertices one of which has degree 2, we obtain a (complete) grid. In a (red) grid on the vertex set

[n] × [m],
consider a matching of n leftmost horizontal edges, that is the edges connecting (i, 1) and (i, 2) for every i ∈ [n]. Contracting these edges from top to bottom produces intermediate red graphs of red degree at most 4, ending in a red grid graph on

[n] × [m -1]
. Finally a path is obtained, which can be contracted into a single vertex while keeping red degree at most 2. ◀

List of handled problems

We refer to Section 2.1 for the definitions of dominating set, vertex cover, connected set, and independent set. We will mostly deal with the following three problems, given by order of importance. Given a graph G and a capacity function c : V (G) → N, a capacitated vertex cover X of G is a vertex cover of G which admits a mapping ρ : E(G) → X assigning to each vertex x ∈ X no more edges than its capacity, i.e., |ρ -1 (x)| ⩽ c(x) for every x ∈ X. The lower bound for k-Dominating Set will also apply to its connected and total variants. For completeness, we give the definition of the remaining problems that are mentioned at least once in the paper.

Kernels or lack thereof

We often identify a problem to the language made by its positive instances. For a parameterized problem Q, a kernel of size bounded by a function f is a polynomial-time reduction ρ :

Σ * × N → Σ * × N such that (x, k) ∈ Q if and only if ρ(x, k) ∈ Q, and |ρ(x, k)| ⩽ f (k).
A kernel is said linear, quadratic, or polynomial, if the function f can be chosen linear, quadratic, or polynomial, respectively. We recall the framework of OR-cross-compositions [START_REF] Cygan | Parameterized algorithms[END_REF], which we will rely on to show the absence of a polynomial kernel in Theorem 1. An OR-cross-composition is a polynomial reduction that takes t instances of an NP-hard problem L and builds an instance of a parameterized problem Q, such that the OR of the input instances is equivalent to the output instance. More precisely at least one of the t input instances is positive if and only if the output instance is positive. It furthermore allows to set some restrictions on the input NP-hard instances in the form of a polynomial equivalence relation. This relation can be useful in shaping the input instances in such a way that the composition behaves well. We can now formally define an OR-cross-composition.

▶ Definition 12. Let L be a language, R a polynomial equivalence relation on Σ * and Q a parameterized problem. An OR-cross-composition from L to Q with respect to R is an algorithm taking as input t R-equivalent instances x 1 , ..., x t ∈ Σ * , running in time polynomial in t j=1 |x j |, and outputting an instance (y, N ) ∈ Σ × N such that: (i) N is polynomially bounded in max j∈ [t] |x j | + log t, (ii) (y, N ) ∈ Q if and only if there exists some j such that x j ∈ L.

We say that L cross-composes into Q, and we sometimes refer to output instance (y, N ) as the composed instance. The following result provides the lower bound under coNP ⊆ NP/poly. ▶ Theorem 13. If an NP-hard language L admits an OR-cross-composition into a parameterized problem Q, then Q does not admit a polynomial kernel unless coNP ⊆ NP/poly.

Organization of the rest of the paper

In Section 3, we sketch the proof of our main result, Theorem 1. In Section 4, we show the NP-hardness of Minimum Dominating Set in a customized setting that will be particularly convenient for the subsequent OR-cross-composition. In Section 5 we present the ORcross-composition, show its correctness, and prove the twin-width upper bound, thereby establishing Theorem 1. In Section 6, we present two simple O(k 2 ) kernels for Connected k-Vertex Cover and Capacitated k-Vertex Cover, and a refined O(k 1.5 ) kernel for the former problem. In Section 7, we show that graphs of twin-width 1 can be efficiently recognized and a 1-sequence with additional property can be produced, and argue that this extra property can be used for polynomial-time algorithm for a wide range of problems.

Outline of the OR-cross-composition for k-Dominating Set

Let us start explaining why we should not expect a simple OR-composition. After all, it is only fair to ask for a justification that the kernel lower bound for k-Dominating Set spans a dozen of pages when the same result for k-Independent Set is a side note; even more so, when the former is often more intractable than the latter from a parameterized complexity standpoint.

The simplest OR-composition is the disjoint union of the input instances. By simple OR-composition we mean one, like for k-Independent Set, straightforwardly based on juxtaposing the instances. A standard way to OR-compose t Dominating Set-instances is to have for each instance a "switch", that is, one vertex dominating all but one instance. Then picking the corresponding vertex in the solution, one is left with dominating one chosen instance with a given remaining budget. This is precisely what we want, but how to ensure that one does not activate two switches?

As we previously observed [START_REF] Bonnet | Twin-width III: Max Independent Set and Coloring[END_REF], one can use larger weights for the switches. However removing the vertex-weights cannot be done without increasing the twin-width. Another possibility is to force all the budget but one unit (for the switch) within the instances. This requires, say, k vertices called "forcers", each adjacent to a k-th fraction of each instance. Now consider the induced subgraph made by these k vertices, the t switches, and tk vertices of the instances realizing the tk possible neighborhoods toward the former t + k vertices. The two neighborhoods of every pair of vertices in this graph has a large symmetric difference. Thus in particular the overall graph has unbounded twin-width. (Finally known tricks to condense the t switches into O(log t) vertices do not help, since we want the twin-width to be bounded by an absolute constant.)

So we need a more elaborate way of selecting one instance among t; one, thought primarily to keep the twin-width low. In the previous attempts, the twin-width was increasing too much because of attachments -switches and forcers-external to the instances. We will therefore have instances themselves play these roles. Say that each instance comes with a partition of its vertex set into N parts, each of which containing a vertex solely adjacent to vertices in its part. We place the t instances in a t × N two-dimensional layout, where each instance occupies a "row," while the j-th part of all the instances form the j-th "column." The switch mechanism is as follows. Every vertex in the j-th part of the i-th instance -say I i -dominates the j -1-st part of the instances with a smaller index, and the j + 1-st part of the instances with a larger index. In other words, we put a strict half-graph over the parts of two consecutive columns. This is done cylindrically, see Figure 3.

With that mechanism, a dominating set of a fixed instance I i (intersecting each of its parts once) is a dominating set of the overall graph. We skip here the details of the reverse direction, but the use of half-graphs and of vertices whose neighborhood in their instance is confined to their own part (the last ingredient is to have a dummy, edgeless top instance I t ) should give a feel for why no other kind of dominating sets of size N can exist.

What about the twin-width bound? Cycles of half-graphs have bounded twin-width. So a natural first step is to contract every part of every instance into a single vertex. Doing so will create some red edges within each row. To ensure that the red degree remains bounded in this first step, a part should be partially adjacent to only a bounded number of other parts. In the second step, we contract the cycle of half-graphs row by row. Thus the red edges of the different instances will progressively stack up. We need to control the accretion with the red edges of each instance mapping onto a common bounded-degree red graph. Finally in the third step, we contract the residual red graph. It should be itself of bounded twin-width,

I 1 I 2 I 3 I 4 I 5 I 6
Figure 3 The overall picture. Instances I1, . . . , It (here with t = 6) are in rows, boxed in blue, with their edge also in blue. For the sake of legibility, we only represented the edges of I1. The red dotted edges are the red edges appearing after contracting every part (boxed in black) into a single vertex. Example of what three vertices picked in the first three parts of I4 dominates in the other instances. Continuing consistently in I4 would result in "switching off" all the other instances, while deviating would leave at least one part "white" and not intersected, thus one vertex not dominated.

for instance by being planar.

In the next section, we show that Minimum Dominating Set remains NP-hard even when inputs are equipped with a vertex-partition satisfying all the properties that we came across in this outline.

4

Tailored NP-hardness for Dominating Set

We will show in this section the following hardness result for Dominating Set. The extra properties that we get compared to existing NP-hardnesses of Dominating Set (even those on planar instances) is crucial for the subsequent OR-cross-composition, as hinted at in the previous section. The statement of the next two theorems involve what we will call snaking grids. See Figure 4 for an illustration of the 5 × 10 snaking grid, which has (3 • (5 -1) + 1)(3 • (10 -1) + 1) vertices. One may observe that the snaking grids are subdivisions of a wall with some extra isolated vertices. We will prefer to think of the snaking grid as a spanning subgraph of a (complete) grid, hence the particular embedding of the figure. The motivation behind the snaking grid will become clear when designing the cross-composition and bounding its twin-width in Section 5.1: it allows to superpose a canonical hamiltonian cycle such that the maximum degree remains 3.

▶ Theorem 14. Dominating Set remains NP-hard when its input (G, N ) comes with a vertex-partition B = {B 1 , . . . , B N }, two positive integers s and t, and a bijective mapping η from {B 1 , . . . , B N } to the vertex set of the s × t snaking grid such that:

(i) G has a partial 4-sequence to the quotient trigraph G/B, (ii) G/B is a spanning subgraph of the s × t snaking grid, with t even, witnessed by η, and (iii) every dominating set of G intersects each B i , for i ∈ [N ].

We will obtain Theorem 14 as a direct consequence of the following reduction, and the fact that Planar 3-SAT is NP-hard [START_REF] Lichtenstein | Planar formulae and their uses[END_REF] One can observe that conditions (i), (ii), and (iii) of Theorems 14 and 15 match. Condition (iv) in Theorem 15 only insists that the polynomial-time transformation is a valid reduction.

Planar satisfiability

Planar 3-SAT was introduced by Lichtenstein, who showed its NP-hardness [START_REF] Lichtenstein | Planar formulae and their uses[END_REF], as a convenient starting point to prove the intractability of planar problems. It is a restriction of 3-SAT where the variable/clause incidence graph is planar even if one adds edges between two consecutive variables for a specified ordering of the variables: x 1 , x 2 , . . . , x n ; i.e., x i x i+1 is an edge (with index i + 1 taken modulo n). In any Planar 3-SAT-instance φ one can partition the clause set C into (C + , C -) such that C + and C -each admits a removal ordering, where a removal ordering consists of iteratively applying the two following kinds of deletions: removing a variable which is not present in any remaining clause, or removing a clause on three consecutive variables together with the middle variable, which ends up with an empty set of clauses. Three consecutive variables means three variables x i , x j , x k , with i < j < k such that x i+1 , x i+2 , . . . , x j-1 and x j+1 , x j+2 , . . . , x k-1 have all been removed already. The middle variable of the clause is x j . For an example, see Figure 5. What matters to us is that φ can be embedded in an (|C| + 1) × n grid (the dashed blue lines in Figure 5) such that every "event" (a variable "wire" turns or finishes) happens at a grid point. The (3m + 1) × (3n -2) grid made by the dashed blue and gray lines will embed the snaking grid. The "wire" of variable x1 is highlighted in green.

x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 C + C -
The reduction to establish Theorem 15 will be a rather transparent substitution of local gadgets on grid points of Figure 5. We need a variable gadget (to initiate a Boolean choice), a propagation gadget ("wires" that may split), and a clause gadget (where the "wires" of three variables meet at a grid point). In addition, we will design a very simple dummy gadget, used to fill all the unoccupied grid points. We start with a description of the variable and propagation gadgets.

Variable and propagation gadgets

We distinguish the initial variable gadget and the (regular) variable gadget. The initial variable gadget is simply a triangle, one vertex of which corresponds to setting the variable to true (marked ⊤ in the figures), a second vertex, to setting it to false (marked ⊥), and a third vertex which will remain of degree 2. These three vertices form one part, say, B ℓ of B. We denote them by ⊤, ⊥, and d, and use the subscript of the part of B they belong to whenever we want to be specific (so ⊤ ℓ , ⊥ ℓ , and d ℓ ).

The regular variable gadget (or variable gadget for short) is the bull graph. More precisely, it is an initial variable gadget where one adds one pendant neighbor t to ⊤ and one pendant neighbor f to ⊥. Again these five vertices form one part of B, say B ℓ , that we may denote ⊤ ℓ , ⊥ ℓ , d ℓ , t ℓ , and f ℓ . For both the initial and regular variable gadgets, the index of the gadget is simply ℓ.

The propagation gadget from a (possibly initial) variable gadget of index ℓ to a regular variable gadget of index ℓ ′ consists of the two edges ⊤ ℓ f ℓ ′ and ⊥ ℓ t ℓ ′ . The "propagation" starts at an initial variable gadget and extends in two directions. It may also "split," that is, a same regular variable gadget can propagate to two variable gadgets, one horizontally and one vertically. See Figure 6 for a depiction of these gadgets.

For every variable x i of φ, we have a unique initial variable gadget, and several regular

⊤ ⊥ ⊤ ⊥ ⊤ ⊥ ⊤ ⊥ ⊤ ⊥ ⊤ ⊥ ⊤ ⊥ ⊤ ⊥ Figure 6
Initial variable gadget (slightly shaded box in the middle), seven (regular) variable gadgets, and the propagation gadgets (edges in between variable gadgets), allowing the "wire" to split. The thick boxes represent the partition B, each box corresponding to an initial or regular variable gadget. The figure should be rotated 90 degrees to match Figure 5 where the propagation from the initial variable gadgets occurs vertically.

variable gadgets connected to it via a chain of propagations. We call wire of x i , the graph induced by all these variable gadgets (the initial variable gadget included). The digraph of a wire (or, by extension, of its corresponding variable) is the directed graph whose vertices are the variable gadgets of the wire, and with an arc from a variable gadget of index ℓ to one of index ℓ ′ if there is a propagation gadget from the former to the latter. Following Figure 5 the digraph of every wire is an out-tree of maximum out-degree 2, rooted at the initial variable gadget. The leaves of this tree are adjacent to a grid point where we will place a clause gadget.

The following lemma ensures the expected behavior of a choice propagation. The rest of the construction (mainly the insertion of the clause gadgets) will not change the properties used in its proof, so we show it here.

▶ Lemma 16. Let H be the wire of variable x, and let ⃗ T be the out-tree, digraph of H. The only two dominating sets of H of size (at most) |V ( ⃗ T )| consists of picking ⊤ in every gadget, or of picking ⊥ in every gadget.

Proof. Every variable gadget has a vertex d only adjacent to vertices within the gadget, so a dominating set of size |V ( ⃗ T )| has to intersect each gadget exactly once. Since the digraph of H is supposed to be an out-tree, and the vertices t ℓ ′ and f ℓ ′ have their neighborhood included in the gadget of index ℓ ′ and its unique in-neighbor (in ⃗ T ), of index, say, ℓ, it suffices to observe that the only pairs of vertices dominating all the vertices in these two gadgets are {⊤ ℓ , ⊤ ℓ ′ } and {⊥ ℓ , ⊥ ℓ ′ }. ◀

In the statement of Lemma 16, the former choice sets x to true, the latter, sets x to false.

Clause and dummy gadgets

The clause gadget of C j consists of two vertices c j , z j , where c j is linked to its three literals in the corresponding wire ends, and z j is isolated. The set {c j , z j } is added to B. See Figure 7 for an illustration.

⊤ ⊥ ⊤ ⊥ ⊤ ⊥ c j z j x a1
x a3

x a2

Figure 7 Three variable wires converging to a clause gadget Cj = xa 1 ∨ ¬xa 2 ∨ ¬xa 3 . Again, the thick boxes represent the partition B. In fact, due to the horizontal snaking, either one of xa 1 , xa 3 would appear above the clause gadget (see Figure 8).

A dummy gadget is simply an isolated vertex z, which makes its own singleton part {z} in B. Thus a dummy gadget is a clause gadget minus the vertex c j . The isolated vertices z j 's in the clause gadgets, and the dummy gadgets may seem artificial. Their purpose is to fulfill conditions (ii) and (iii). Besides isolated vertices will not remain isolated in the subsequent OR-cross-composition.

Construction

At this point, the construction is probably clear. Let n and m be the number of variables and clauses, respectively, of the Planar 3-SAT-instance φ. We assume that n is even (if not, we add a dummy variable not appearing in any clause). We put one initial variable gadget at each grid point (of the finer (3m + 1) × (3n -2) grid) in Figure 5 with a circled vertex (n grid points in total). We place a regular variable gadget at every grid point covered by the solid black (or green) lines, and at every grid point just below any horizontal segment of a wire (to account for the snaking), except for those on the bottommost row. We orient the propagation such that the digraph of each of the n wires is an out-tree rooted at its initial variable gadget. For every clause of C -, we place a clause gadget at the corresponding grid point occupied by a square vertex in Figure 5, and link it accordingly to its literals. For every clause of C + , the clause gadget is instead placed at the grid point just below the corresponding square vertex. This is again because of the horizontal snaking (see Figure 8). Finally we put a dummy gadget at every unoccupied grid point. This finishes the construction of the graph G, and its vertex-partition B. We set N to |B|, that is, (3m + 1) × (3n -2). The embedding witness η is implicit from the construction.

Proof of Theorem 15. We now check the conditions (i) to (iv). Let us start with the correctness of the reduction, namely (iv).

Assume φ admits a satisfying assignment A, and sets each variable to the value given by A in each wire of G. Complete this solution by including all the isolated vertices of G. By design this yields a set S of size N . By Lemma 16, every vertex in a wire is dominated. The isolated vertices are dominated by themselves, and every vertex c j in a clause gadget is dominated since A is a satisfying assignment. Thus S is a dominating set of G of size N (intersecting every part of B exactly once).

Conversely, assume that G has a dominating set S of size N . As every gadget contains a vertex whose neighborhood is included in its own part of B (namely d, and the isolated x a 1

x a 1

x a 1

x a 1

x a 1

x a 1

x a 1

x a 2

x a 2

x a 3

x a 3

x a 3

x a 3

x a 3

x a 3

C j D D D D D D D D D D D D Figure 8
The vicinity of a clause gadget, for a clause Cj ∈ C + . Red edges materialize the edges in between two parts: propagation and edges incident to the clause gadget. Due to the horizontal snaking, the clause gadget is placed just below its position in Figure 5. Dummy gadgets are marked with a D. vertices), S should intersect every part of B exactly once. In the dummy and clause gadgets, the picked vertex should thus be the isolated vertex. By Lemma 16, in each wire a consistent choice (of taking only ⊤ or only ⊥) has to be made. Let A be the corresponding truth assignment. As S dominates each vertex c j in the clause gadgets, it implies that A is a satisfying assignment, and ϕ is satisfiable.

Condition (i). By construction B partitions V (G)

. We want to propose a partial 4-sequence from G to G/B. In other words, we wish to contract every part of B into a single vertex, such that the red degree remains at most 4.

In any order, we contract the bull graph of each regular variable gadget adjacent to only two other variable gadgets in the following way: (⊤, d), ({⊤, d}, t), ({⊤, d, t}, ⊥), ({⊤, d, t, ⊥}, f ). Internally this creates (at any moment) a single red edge. There can be up to four red edges between this part and another part of B (since there are at most four leaving black edges). Observe however that these four edges can be incident to a single vertex only after the last internal contraction ({⊤, d, t, ⊥}, f ). Thus the red degree of these vertices remains at most 4.

Meanwhile the red degree of vertices not falling in that category is bounded by 3, in clause gadgets, and by 2, in other variable gadgets. We can then contract the initial variable gadget and the clause gadgets (there is nothing to contract in dummy gadgets). Regular variable gadgets adjacent to three parts of B are now adjacent to three vertices. Indeed there is no pair of adjacent such gadgets. Thus the above suggested contraction of the bull keeps red degree at most 4.

Condition (ii)

. By design, G/B is a subgraph of the (m + 1) × n snaking grid, witnessed by η. It is spanning by introduction of the dummy gadgets.

Condition (iii). This was observed when checking the correctness of the reduction. ◀

As previously mentioned, this directly implies Theorem 14.

For Connected k-Dominating Set and Total k-Dominating Set on bounded twin-width graphs (with an upper bound possibly larger than 4), one does not need the snaking grid nor the dummy gadgets. In the propagation between two variable gadgets, one can add an edge between the two ⊤ vertices, and an edge between the two ⊥ vertices. In the clause gadgets, one can add a neighbor y j to z j , adjacent to the six vertices ⊤ and ⊥ in the three incident variable gadgets.

OR-cross-composition

We now describe the cross-composition from the NP-hard Dominating Set restricted as in Theorem 14 to k-Dominating Set. We use the polynomial equivalence R to partition all well-formed instances for the restricted k-Dominating Set (those satisfying Theorem 14) with respect to the given parameter N and dimensions (p, q) of the corresponding snaking grid. All ill-formed instances will then make a single class. Relation R satisfies the conditions of Definition 11. For any two well-formed instances (I i , N i , B i , p i , q i , η i ), (I ℓ , N ℓ , B ℓ , p ℓ , q ℓ , η ℓ ), we can check in polynomial time that N i = N ℓ and (p i , q i ) = (p ℓ , q ℓ ), yielding (i). Now, choosing some encoding such that all well-formed instances of Σ ⩽n have at most n vertices, their parameter and snaking grid dimensions must also be bounded by n. Then, the number of equivalence classes on Σ ⩽n accounting for the malformed instances is at most n 3 + 1, yielding (ii).

The conditions for our composition being set, consider t instances of the restricted Dominating Set, equivalent with respect to R. If the instances are ill-formed we output an ill-formed instance of k-Dominating Set. If not, their equivalence yields common parameter N and snaking grid dimensions (p, q), letting us consider them as (I i , N, B i , p, q, η i ) i∈ [t] . We will construct a k-Dominating Set instance (H, N ), with the same parameter, admitting a solution if and only if at least one input instance (I i , N, B i , p, q, η i ) admits a solution for the restricted k-Dominating Set. Before composing the input graphs, we introduce a dummy instance in the form of graph I t+1 serving to ensure that any valid (H, N ) further admits a solution picking vertices in each column. I t+1 is an independent set of size 2N on which we partition V (I t+1 ) through B i+1 into N classes of exactly two vertices. Note that since I t+1 /B t+1 is an independent set, it is a spanning subgraph of the p × q snaking grid as witnessed by any bijective η t+1 onto the latter.

We first show how to order the partition classes of each instance in the same way with respect to their mapping onto the snaking grid. This ordering will follow a fictitious hamiltonian cycle (y 1 , ..., y N ) on the p × q snaking grid, which we now describe. From the snaking grid, we take all edges of the first row, and all edges of the first and last columns. Then, from the complete underlying grid, we take all but the first edge of each column and we complete the cycle by taking all edges between two degree one vertices in the so-built union of paths (see the darker red cycles in Figures 9 and10). Referring to the partition of instance i ∈ [t + 1] as B i = {B i,1 , ..., B i,N }, we can assume up to the reordering above that η i (B i,j ) = y j . Now, considering all instances over H, a representation of the construction that follows is given in Figure 3. It will be useful to consider the instances in a grid such that B i,j is the cell in the i-th row and j-th column, and we will use the term partition class or cell interchangeably. We can then see instance I i as row i, and define regular instance columns, omitting the dummy instance, as

C j = i∈[t] B i,j for j ∈ [N ].
Construction. We start building our composed graph H as the union of all instances

(I i ) i∈[t+1] , that is, V (H) = i∈[t+1] V (I i ) and E(I i ) ⊆ E(H) for i ∈ [t + 1]
. Then, our cross-composition proceeds by adding a cycle of strict half-graphs over columns (C j ) j∈[N +1] : for i ∈ [t + 1], j ∈ [N ], B i,j forms a biclique with i<ℓ⩽t+1 B ℓ,j+1 (accounting for indices j modulo N ). Notice then that the only edges added above lie between columns C j , C j ′ with |j ′ -j| = 1, so any edge between two columns differing by at least two indices is an edge of I i . Each instance class B t+1,j is then adjacent exactly to C j-1 . Having ordered the classes of each instance in the same way with respect to their mapping onto the snaking grid, column C j consists of homologous vertices, all in the same position on their respective grids, see Figure 10. Then, the cycle of half-graphs follows the darker red fictitious hamiltonian cycles mapping to (y 1 , ..., y N ).

The composed k-Dominating Set is then (H, N ), which we can construct polynomially in t i=1 |I i |. Indeed, N is bounded by any |I i | so the dummy instance is built linearly, then graph union and addition of the bicliques takes time polynomial in t i=1 |I i |. Moreover, the reduction directly satisfies condition (i) of Definition 12 since the output parameter N is bounded by any |I i |.

The overall construction has twin-width at most 4

Consider the OR-cross-composition of t instances (I i , N, B i , p, q, η i ) i∈ [t] of the restricted k-Dominating Set described Section 5, letting (H, N ) be the composed instance. Towards showing that the twin-width of H is bounded by 4, we first show that there is a partial 4-sequence contracting each B i,j for i ∈ [t + 1], j ∈ [N ] into a single vertex in H. After these contractions, each instance I i /B i can be considered as a red snaking grid augmented by a hamiltonian path (Figure 9). We call augmented snaking grid the graph obtained by adding the (darker red) hamiltonian cycle to the snaking grid. The cycle of strict half-graphs added between the instances will then follow the hamiltonian cycles of each augmented snaking grid. Finally, we show that there is a partial 4-sequence contracting these t + 1 grids into a single one, which is of twin-width four. . . .

Figure 9

The maximal set of red edges, with the hamiltonian cycle in darker red, and the edges of the snaking grid that are not already in the hamiltonian cycle in lighter red. A partial 4-sequence goes as follows. First contract every blue vertex with their homologous in the next layer, in any order. Then similarly contract every purple vertex, followed by every orange vertex. Finally follow the order indicated by positive integers (in increasing value). This way a vertex contracted with the next layer has at most two neighbors, or at most one non-contracted neighbor.

▶ Lemma 17. The composed graph admits a partial 4-sequence to H/

i∈[t+1] B i .
Proof. Theorem 14 yields that each input graph I i , i ∈ [t] admits a partial 4-sequence to I i /B i yielding a subgraph of the snaking grid, this is also the case for dummy instance I t+1 as an independent set. Our contraction sequence will consist exactly of those contractions, so let us see how they behave over H. Notice that for any I i , the only contractions made above involve vertices of a single class B i,j , which is a module with respect to H -I i . Therefore, in H, the partial contraction sequence of each I i does not create red edges towards H -I i . In turn, we can contract each I i to I i /B i through a partial 4-sequence over H, and the only resulting red edges will belong to a single instance. ◀ Now, for the purpose of bounding the twin-width of the composed graph, it is useful to note that Observation 7 allows us to add red edges. At this point, the only vertices of large degree stem from the strict half-graphs. We keep those edges black, and we now turn each instance into a red augmented snaking grid as depicted in Figure 9 as follows. Since each instance is a spanning subgraph of the p × q snaking grid, we can first assume that it is a (fully) red snaking grid. Then, the red augmented snaking grid is built by further adding red cycle (B i,1 , ..., B i,N ). By our choice of ordering in the composition, this cycle is the same on every instance with respect to their mapping on the p × q snaking grid.

▶ Lemma 18. The composed graph H has twin-width at most 4.

Proof. By Lemma 17 and the above remarks, we can now describe the contraction of t + 1 red augmented snaking grids (I i ) i∈[t+1] , abusing notation for the now quotiented instances, with the black edges of our composition. We will exhibit a partial 4-sequence eventually contracting every column, now consisting of t + 1 homologous vertices, that is, all vertices at the same position on their respective snaking grid into a single one. The proof will proceed by induction on the number of augmented snaking grids, our hypothesis at step t being that there exists a partial 4-sequence from t augmented snaking grids to a single one, accounting for the black edges added in the composition. This being true for t = 1, assume the result holds for some t and let us consider case t + 1.

We will deal with the two bottommost augmented snaking grids I 1 , I 2 in the half-graphs, contracting pairs of homologous vertices, corresponding to the quotiented (B 1,j , B 2,j ) thanks to the ordering chosen in the composition. Before proceeding, it is useful to make the following observations:

For any grid I i with i > 2, the vertices of any homologous pair (B 1,j , B 2,j ) are each adjacent exactly to B i,j+1 in I i . Their contraction yields no red edges, allowing us to omit other instances and only consider the two to be contracted. The edges involving both snaking grids consist in the matching (B 1,j , B 2,j+1 ) j , see Figure 10, which can be assumed red while keeping red degree at most four. In our contraction sequence, this enables us to only bound the total degree at any point. Now, when contracting a pair of vertices, any vertex in the above matching adjacent to one of the vertices of our pair is also adjacent to the other because of the additional hamiltonian cycle. Therefore, the neighbors of the contracted pair will be exactly the neighbors of each vertex in its respective instance. Contracting a pair coarsens the partition of our vertices, so the degree of a vertex not in the pair cannot increase, thus it is enough to bound the degree of the contracted pair. Now, consider any pair (a, b) to be contracted, such that both vertices have C already contracted, common neighbors and each P non-contracted neighbors in their respective instance. According to the second observation above, the resulting degree will be C + 2P . Since any vertex is of degree at most three in its respective grid C + P ⩽ 3, which would already allow us to contract the pairs in any order with degree at most six. Therefore, to bound the degree by four, the order in which we contract the pairs must be carefully chosen with respect to their position on the respective augmented snaking grids. We want to iteratively contract pairs of vertices satisfying C + 2P ⩽ 4, at each step propagating this bound to more non-contracted vertices to eventually contract all pairs. We proceed by groups of colors as depicted in Figure 9. We first contract pairs of blue vertices, those of degree two in their respective augmented snaking grid. Second, we contract pairs of purple vertices, those of degree three adjacent to two contracted vertices (necessarily blue). Third, we proceed with pairs of orange vertices, those still non contracted on the second row of the snaking grids, which are of degree three and adjacent to a blue and a purple vertex. Finally, numbered in white, we will contract the remaining degree three vertices along the corresponding snaking path.

We are now ready to describe the contraction sequence. For the blue, orange and purple pairs, the contractions can be done in any order, while we will describe the order for the last ones. For any blue pair, depending on the order of contraction we either have (C, P ) = (0, 2), (C, P ) = (1, 1) or (C, P ) = (2, 0). Thus, regardless of the order the contraction yields degree C + 2P at most four. For any purple pair, we either have (C, P ) = (2, 1) or (C, P ) = (3, 0), again regardless of order contracting the pair yields degree at most four. The case is the same for orange pairs, and we can again contract them in any order. The graph induced by the non-contracted vertices on each instance now consists in an union of paths, with endpoints satisfying (C, P ) = (2, 1) and interior points such that (C, P ) = (1, 2). We can iteratively contract the pairs corresponding to the endpoints, satisfying (C, P ) = (2, 1), decreasing the length of the path by one at each step. This can be done until we are left with single vertices for each path, the corresponding pairs are then adjacent exactly to three already contracted vertices, and their contraction yields degree three.

This finishes to prove that the contraction of the first two red snaking grids can be done while bounding the red degree by four. Since the only contracted pairs were homologous, this results in a red augmented snaking grid with no red edges towards grids i > 2. The remaining edges of the strict half-graph cycle still form one of height t, which is exactly the induction case for t and achieves to prove the induction. Therefore, there is a partial 4-sequence from our composed graph into a red augmented snaking grid. Then, as the latter is a subgraph of the red complete grid, Lemma 10 yields twin-width at most 4. ◀

Correctness

Having verified that the reduction runs in polynomial time and satisfies condition (i) of Definition 12, for the OR-cross-composition to be sound it remains to show equivalence of the instances.

▶ Lemma 19. The composed instance is positive for k-Dominating Set if and only if at least one input instance is positive for the restricted k-Dominating Set.

Proof. Consider the OR-cross-composition of R-equivalent instances (I i , N ) i , i ∈ [t] of the restricted k-Dominating Set into k-Dominating Set instance (H, N ) as described in Section 5. We start by showing the easier direction, the existence of a positive input instance implies that the composed instance is also positive, then we prove the converse. The reduction is such that for any set D ∈ H, D dominates H if and only if it dominates some input instance I i .

One input instance is positive implies that the composed instance is positive

Assume there exists some ℓ ̸ = t + 1 such that (I ℓ , N ) is a positive instance for the restricted k-Dominating Set, let us consider dominating set D for I ℓ , with |D| = N and satisfying the conditions of Theorem 14. We show that D is also a dominating set for H. Since our reduction preserves the edges of each instance, D dominates V (I ℓ ) over H by assumption. To show that V (H) -V (I ℓ ) = i̸ =ℓ,j∈[N ] B i,j is dominated, let us consider any cell B i,j with i ̸ = ℓ. If i < ℓ, by construction B ℓ,j-1 , B i,j form a biclique in H, then D intersects B ℓ,j-1 via item (iii) of Theorem 14 so B i,j is dominated. Otherwise, i > ℓ and B ℓ,j+1 , B i,j form a biclique in H, now D must intersect B ℓ,j+1 and again B i,j is also dominated. Therefore D is indeed a dominating set of H, yielding the backwards implication.

The composed instance is positive implies that one input instance is positive

Conversely, assume (H, N ) is a positive instance for k-Dominating Set, considering any solution D ⊆ V (H), we show that D is necessarily also a dominating set of some I ℓ , yielding a positive instance among the input ones.

We leverage the fact that D dominates each dummy partition class B t+1,j+1 to yield that |D ∩ C j | ⩾ 1 for any j. By construction, each B t+1,j+1 is only adjacent to vertices in column C j , so we already know D intersects each C j ∪ B t+1,j+1 for j ∈ [N ], and since |D| = N each such intersection consists of a single vertex d j . Now, the two vertices of B t+1,j+1 are adjacent exactly to C j , so the choice of d j as one of them would prevent our solution from dominating the other. Then d j ∈ C j = t i=1 B i,j , letting us define the row choice r j for column j as the unique r j ∈ [t] such that d j ∈ B rj ,j .

We now show the existence of some i ∈ [t] such that D ⊆ V (I i ). From the necessity to choose one vertex per column shown above, this is equivalent to showing that for some i ∈ [N ] the row choices are constant: r j = i for j ∈ [N ]. We first argue that both the even choice sequence (r 2j ) j and the odd choice sequence (r 2j+1 ) j must be constant (notice that if N is odd, both contain all row choices). Considering the indices as corresponding to rows modulo N , both sequences are periodic. If one is not constant we can consider a pair of indices (j, j + 2) such that corresponding row choices k = r j , k ′′ = r j+2 are such that k > k ′′ .

With Proof. Lemma 19 proves that the OR-cross-compositions described in the beginning of Section 5 is correct. The twin-width bound of the composed instance is given in Lemma 18.

d j ∈ B k,j , d j+2 ∈ B k ′′ ,
We can thus invoke Theorem 13 in order to obtain the desired result. ◀

I k ′′ -3 I k ′′ -2 I k ′′ -1 I k ′′ . . . . . . . . . . . . . . . . . . I k I k+1 I k+2 I k+3
Figure 11 In the middle column Cj+1, pink classes are those dominated by the choice of dj and dj+2 in the neighboring columns. At least two classes, highlighted in green and corresponding to the interval [k ′′ , k], would need to be dominated by a single vertex within the column, which cannot be done.

Polynomial kernels

We present two simple kernelization algorithms for Connected k-Vertex Cover and Capacitated k-Vertex Cover with kernels on O(k 2 ) vertices. We also provide an improved kernel on O(k 1.5 ) vertices for Connected k-Vertex Cover.

A folklore in the context of k-Vertex Cover kernelization is that keeping at most k + 1 twin vertices is a safe reduction rule. Hence any module outside of a vertex cover X can be trimmed down to k + 1 vertices. Similar reduction rules are also known for Connected k-Vertex Cover and Capacitated k-Vertex Cover [START_REF] Cygan | Tight kernel bounds for problems on graphs with small degeneracy[END_REF]. Therefore to get a polynomial kernel, one simply needs to polynomially bound the number of modules outside X, or equivalently, the number of distinct neighborhoods in X.

This will be done by proving Lemma 3 which, we repeat, is equivalent to saying that the neighborhood hypergraphs of graphs of bounded twin-width have VC density 1. This feature is shared with classes of bounded expansion. Lemma 3 is of independent interest as it opens the door to a common algorithmic treatment for classes of bounded twin-width and of bounded expansion.

To state the next two theorems, we need to introduce some vocabulary on 0, 1-matrices. A row (resp. column) partition of a matrix M is a partition of its row set (resp. column set). A row (resp. column) division is a row (resp. column) partition where every part is a consecutive set of rows (resp. columns), or interval. A division of a matrix M is a pair (R, C) where R is a row division and C is a column division. A cell or zone of a matrix M with division

(R, C) is a submatrix M [R i , C j ] with R i ∈ R and C j ∈ C. A t-division is a division (R, C) with |R| = |C| = t. A t-grid minor of a 0, 1-matrix M is a t-division of M
where every cell contains at least one 1-entry. A matrix is mixed if it has at least two distinct rows and at least two distinct columns. A corner is a 2 × 2 contiguous submatrix which is mixed. A t-mixed minor of a matrix M is a t-division of M where every cell is mixed. It can be observed that this is equivalent to the existence of a t-division where every cell contains a corner [START_REF] Bonnet | Twin-width I: tractable FO model checking[END_REF].

We first recall the Marcus-Tardos theorem, a celebrated result in combinatorics.

▶ Theorem 20 ([41]). For every integer t, there is some c t such that every n × m 0, 1matrix M with at least c t max(n, m) entries 1 has a t-grid minor.

In what follows c t will always denote the bound in Theorem 20. The best upper bound for c t is currently 8/3(t + 1) 2 2 4t [START_REF] Cibulka | Füredi-Hajnal limits are typically subexponential[END_REF], that we take as the definition of c t .

The following result is shown in the first paper of the series dedicated to twin-width.

▶ Theorem 21 ([6]). If, for every vertex ordering, the adjacency matrix of a graph G has a 2t + 2-mixed minor, then G has twin-width larger than t.

We prove that in a 0, 1-matrix of small twin-width, the number of distinct columns is linearly bounded in the total number of rows.

▶ Theorem 22. Let t be a positive integer. Let M be a 0, 1-matrix with s rows, and at least 2 4c2t+2 • s distinct columns. Then M has a 2t + 2-mixed minor.

Proof. We denote by R and C the sets of rows and columns, respectively, of M . Without loss of generality, we may assume that all the columns of M are distinct. We consider a division of C into s parts {C 1 , . . . , C s }, each C i consisting of 2 4c2t+2 consecutive (distinct) columns. Note that the submatrix of M consisting of the columns C i has rank at least 4c 2t+2 in the binary field F 2 , for all i ∈ [s].

Therefore there is a row division of M [R, C i ] into at least 2c 2t+2 (row) parts, each zone of which has rank at least 2, thus is mixed, and, by an observation in [START_REF] Bonnet | Twin-width I: tractable FO model checking[END_REF], contains a corner. These 2c 2t+2 corners in M [R, C i ] are on pairwise disjoint pairs of consecutive rows. Let us consider R 1 the row division grouping each pair of rows with indices 2i -1, 2i, and R 2 , grouping each pair of rows 2i, 2i + 1, for i ∈ [⌈s/2⌉]. Observe that one of the two divisions

(R 1 , {C i }), (R 2 , {C i }) of M [R, C i ] contains
⊆ V (G), the number of distinct neighborhoods in X, |{N (v) ∩ X : v ∈ V (G)}|, is at most 2 4c2t+2 |X|.
Proof. We assume for the sake of contradiction that |{N

(v) ∩ X : v ∈ V (G)}| > 2 4c2t+2 |X|.
For every vertex ordering of G, its adjacency matrix M along this order contains an |X| × 2 4c2t+2 submatrix without two equal columns; namely the submatrix of the adjacencies between X and 2 4c2t+2 vertices with a pairwise distinct neighborhood in X. By Theorem 22, it implies that M has a 2t + 2-mixed minor. By Theorem 21, this in turn implies that G has twin-width more than t. ◀

Quadratic vertex kernels

For completeness, we state and prove the folklore reduction rule for k-Vertex Cover variants.

▶

′ := G -s. Suppose that T is a connected vertex cover of G of size at most k. If s / ∈ T , then T is a connected vertex cover of G ′ . If s ∈ T , there is at least one vertex s ′ in S \ T . Now T ′ := (T \ {s}) ∪ {s ′ } is a connected vertex cover of G ′ of size |T |.
Conversely let T be a connected vertex cover of G ′ of size at most k. We claim that T is also a connected vertex cover in G. As G[T ] is connected and |T | ⩽ k, we shall just check that all the edges of G are covered by T . This is because S \ s cannot be totally included in T ; if so, T is not connected because S \ s consists of (at least) k pairwise independent vertices. Therefore, the common neighborhood N (S) should be included in Proof. Let Y i ⊆ V (G) \ X be a module within which Reduction Rule 3 is applied, and y ∈ Y i be the deleted vertex, that is, such that G ′ := G -y. Set Y ′ i := Y i \ {y}. We first observe that the vertices of X b are mandatory for any feasible solution to (G ′ , k). Let T be an arbitrary connected vertex cover of G ′ of size at most k. ▷ Claim 28. X b ⊆ T .

Proof of the Claim: Suppose some vertex w ∈ X b is not contained in T and thus all its neighbors belong to T . Note that w has at least k neighbors outside X in G ′ , even when the deleted vertex y was a neighbor of w in G. We conclude that T = N G ′ (w) \ X, which contradicts that G ′ [T ] is connected. ♢

Because there are all possible edges between Y ′ i and X i , T must contain at least one of Y ′ i and X i entirely. The next claim says that T can be assumed to fully contain X i .

▷ Claim 29. Let y ′ be a vertex of Due to Claim 29, we may assume that T contains X i . Now for any edge xy incident with the deleted vertex y, x is either in X b or X i , and thus the edge xy is covered by T by Claim 28 and the assumption X i ⊆ T . It follows that T is a feasible solution to (G, k).

Y ′ i . If Y ′ i ⊆ T , then T ′ := (T \ Y ′ i ) ∪ (X i ∪ {y ′ })
Conversely, let T be a connected vertex cover of (G, k) of size at most k. Following the same arguments as the above claims, one can easily check that T must contain both X b and X i , and contains at most one vertex of Y i . As we can modify T so that it does not contain y, T is a feasible solution to (G ′ , k). ◀ ▶ Proposition 30. Connected k-Vertex Cover admits a kernel on O t (k 1.5 ) vertices when the input graphs have twin-width at most t.

Proof. Let (G, k) be the input instance of Connected k-Vertex Cover. We can safely remove any isolated vertex, and assume that every connected component of G contains at least one edge. If G contains more than one connected component, then clearly (G, k) is a no-instance and we output the 4-vertex graph with two isolated edges. Therefore, we can assume that G is connected. With a 2-approximation algorithm for Vertex Cover, one can find a vertex cover X of G and assume that |X| ⩽ 2k. Indeed if this is not the case, we can correctly output a trivial no-instance because G does not admit a connected vertex cover of size at most k. Note that Reduction Rule 3 does not disconnect the given graph as we remove a vertex only when it has a twin. Let (G ′ , k) be an instance obtained by exhaustively applying Reduction Rule 3 with the vertex cover X at hand. We classify X into X b and X s as before, and Y 1 , . . . , Y q denote the partition of Y := V (G ′ ) \ X into maximal modules. For each i ∈ [q], X i is the neighbors of Y i in X s . By Lemma 3, we have q ⩽ 2 • 2 4c2t+2 k. Because the edge set since otherwise a vertex shall be incident with two red edges. Recall that at least one vertex of G i+1 , thus one of {u 1 , u 2 , v} is not an original vertex of G. Such a vertex must be incident with a red edge because it is not a module. Therefore, G i+1 [{u 1 , u 2 , v}] has a unique red edge. Without loss of generality, assume that the red edge is u 2 v. Again, u 1 should be an original vertex of G, i.e., |u 1 (G)| = 1, because it has no incident red edge and therefore u 1 (G) forms a module. So Property P holds for G i+1 . ◀

We can efficiently detect graphs of twin-width 1 using the previous lemma and an inductive scheme.

▶ Theorem 32. Twin-width 1 graphs can be recognized in polynomial time. Moreover, a 1-contraction sequence where each trigraph has at most one red edge can be constructed in polynomial time.

Proof. Let G be a given graph. We show by induction on n, the number of vertices of G, how to decide whether or not it has twin-width 1. If G has one vertex, it has twin-width 1 (even 0). If G is not a prime graph, then each maximal module of G and the quotient graph of G by its (pairwise disjoint) maximal modules all have at most n -1 vertices. So Lemma 9 and the inductive step allow us to conclude. We can therefore assume that G is a prime graph.

As a technicality, it is more convenient to assume that G is a trigraph with exactly one red edge. We can in quadratic time guess the first 1-contraction (which creates exactly one red edge since the contractions of twins are safe by Observation 6). Recall that G has exactly one red edge, say uv. Let us establish the next 1-contraction. By Lemma 31, we can limit ourselves to contractions which keep the number of red edges to at most one. Therefore, the next contraction cannot be between two vertices in V (G) \ {u, v}. Indeed, that would either add at least one new red edge to the trigraph or the two contracted vertices would be twins, and as such, in a module of size at least two.

Any contraction between w ∈ V (G) \ {u, v} and u (or v) that creates a new red edge can be disregarded again by Lemma 31. The only way that such a contraction does not increase the number of red edges is if the contraction actually results in the induced subgraph G -{w}. By Observation 6, this contraction can be safely performed. When no such safe contraction is available, we know that only the current red edge can possibly be contracted. Hence, we can safely make this contraction, and we obtain a new graph with n -1 vertices. Observe that in this process, we never branch on two possible contractions.

The second statement immediately follows by concatenating the 1-contraction sequence of modules and the quotient graph, each of twin-width at most 1, as in Lemma 9. ◀

We remark that polynomial time algorithms are not hard to obtain for, say, Connected k-Vertex Cover, k-Dominating Set or Connected k-DS, when a 1-contraction sequence as in Theorem 32 is given. Consider Connected k-Vertex Cover for instance. For each red component, we "trace" a partial solution X, i.e., a vertex set covering all original edges whose endpoints belong to the said red component, by recording for each vertex u of the component whether u(G) is fully contained in X, intersecting (but not fully contained in) X, or not intersecting at all. Among all partial solutions leaving the same trace over the red component, we remember the minimum size of a solution. One can readily check that the optimal value of a partial solution per trace can be updated in constant time for each newly created red component.

Readers may further notice that this dynamic programming works not only when there is at most one red edge, but more generally when a red component size is bounded by a constant. In a manuscript under preparation, the authors show that MSOL 1 -expressible problems can be solved in f (d) • n O (1) -time if the input graph admits a contraction sequence in which each red component has size at most d.

Figure 1 A 5 -

 15 Figure 1 A 5-cycle of strict half-graphs of height 6.

Figure 2

 2 Figure 2 Contraction of vertices u and v, and how the edges of the trigraph are updated.

  Input: A graph G and an integer k Question: Does G have a dominating set of size at most k? Connected k-Vertex Cover (Connected k-VC) Parameter: k Input: A graph G and an integer k Question: Does G have a vertex cover of size at most k which induces a connected subgraph of G?

  Capacitated k-Vertex Cover (Capacitated k-VC) Parameter: k Input: A graph G with a capacity function c : V (G) → N and an integer k Question: Does G admit a capacitated vertex cover X of size at most k?

  Connected k-Dominating Set (Connected k-DS) Parameter: k Input: A graph G and an integer k Question: Does G have a dominating set of size at most k which induces a connected subgraph of G? Total k-Dominating Set Parameter: k Input: A graph G and an integer k Question: Does G admit a set X ⊆ V (G) of size at most k such that every vertex of G has a neighbor in X?

  k-Independent Set Parameter: k Input: A graph G and an integer k Question: Does G have an independent set of size at least k? Independent k-Dominating Set Parameter: k Input: A graph G and an integer k Question: Does G have an independent dominating set of size at most k? k-Path Parameter: k Input: A graph G and an integer k Question: Does G have a path of length at least k? k-Induced Path Parameter: k Input: A graph G and an integer k Question: Does G have an induced path of length at least k? k-Induced Matching Parameter: k Input: A graph G and an integer k Question: Does G have a matching M of size at least k such that there are no edges between endpoints of M other than the edges of M ?

▶

  Definition 11. A polynomial equivalence relation on Σ * is an equivalence relation R when (i) for x, y ∈ Σ * , the equivalence xRy can be decided in time polynomial in |x| + |y|, and (ii) R restricted to instances of size at most n admits polynomially many equivalence classes.

Figure 4

 4 Figure 4 The 5 × 10 snaking grid.

▶ Theorem 15 .

 15 (see Section 4.1). There is a polynomial-time reduction from Planar 3-SAT to Dominating Set that, on n-variable m-clause Planar 3-SAT-instances φ producesDominating Setinstances (G, N, B = {B 1 , . . . , B N }, η) such that: (i) B partitions V (G),and G has a partial 4-sequence to the quotient trigraph G/B, (ii) G/B is a spanning subgraph of the (m + 1) × n ′ snaking grid, with n ′ even in {n, n + 1}, witnessed by η, (iii) every dominating set of G intersects each B i , for i ∈ [N ], and (iv) φ is satisfiable if and only if G has a dominating set of size N .

Figure 5

 5 Figure[START_REF] Bonnet | Twin-width IV: ordered graphs and matrices[END_REF] The bipartition (C + , C -) of an n-variable m-clause Planar 3-SAT-instance, with n = 8 and m = 10. The square vertices represent the clauses. All the degree-3 vertices of the solid black (and green) graph lie at intersections of the (m + 1) × n grid represented with the dashed blue lines. The (3m + 1) × (3n -2) grid made by the dashed blue and gray lines will embed the snaking grid. The "wire" of variable x1 is highlighted in green.

Figure 10

 10 Figure 10The different layers (instances) linked by the cycle of half-graphs. Only four half-graphs are drawn for the sake of legibility.

▶ 1 .

 1 j , let us consider the adjacencies between D and column C j+1 towards showing an absurdity. On the one hand, the edges added in our composition between {d j , d j+2 } and C j+1 are exactly{(d j , v) : v ∈ i>k B i,j+1 } and {(d j+2 , v) : v ∈ i<k ′′ B i,j+1}. On the other hand, for any d ∈ D\{d j , d j+2 }, any edge between d and C j+1 necessarily belongs to some instance I i , i ∈ [t]. Combining the two observations above: for i ∈ [k ′′ , k], any edge (a, d) with a ∈ B i,j+1 , d ∈ D must be an edge of Ii . Since k > k ′′ , interval [k ′′ , k] is of size at least two. We get that B k,j+1 is dominated by D ∩ V (I k ) in I k , while B k ′′ ,j+1 is dominated by D ∩ I k-1 in I k-1 , see Figure11. Now, by Theorem 14 (iii), for any i∈ [t], B i,j+1 ⊈ N (V (I i )\B i,j+1 ), yielding that both D ∩ B k,j+1 and D ∩ B k ′′ ,j+1are non-empty. This is absurd since D must intersect C j+1 in exactly one vertex, so both (r 2j ) j and (r 2j+1 ) j are constant. Now, let us call k the row choice for even columns and k ′ the row choice for odd ones, if N is odd, k = k ′ and the choice is constant. If k ̸ = k ′ , we can choose without loss of generality three consecutive columns C j , C j+1 , C j+2 such that r j = r j+2 = k and r j+1 = k ′ with k ′ > k. Then, we proceed similarly to the last paragraph. Since k ′ > k, the class B k,j+1 is not dominated by d j , d j+2 , by construction of the half-graph. Therefore, it is necessarily dominated by D ∩ V (I k ) both in H and in I k . Again, Theorem 14 (iii) yields thatB k,j+1 ⊈ N (V (I k )\B k,j+1 ) so d j+1 ∈ B k,j+1 , contradicting with d j+1 ∈ B k ′ ,j+1. Therefore k = k ′ and the sequence of row choices (r j ) j is constant.The latter yields k ∈ [t] such that D ⊆ V (I k ), by assumption D dominates V (I k ) on H, while no edges are added between two vertices in V (I k ) by our construction, thus D is a dominating set of I k .◀ Theorem Unless coNP ⊆ NP/poly, k-Dominating Set on graphs of twin-width at most 4 does not admit a polynomial kernel, even if a 4-sequence of the graph is given.

  is a connected vertex cover of G ′ of size at most k.Proof of theClaim: Notice that X b ∪ X i is the neighborhood of Y ′ i in G ′ . By Claim 28, T ′ is clearly a vertex cover of G ′ and y ′ provides any connection between a pair of vertices in T ′ that Y ′ i used to provide. Finally, that Y ′ i is obtained from Y i after Reduction Rule 3 means that |Y ′ i | ⩾ |X i | + 1 = |X i ∪{y ′ }|, and thus |T ′ | ⩽ |T |. ♢

  are called false twins, and true twins if N [u] = N [v]. Two vertices are twins if they are false twins or true twins.A set S ⊆ V (G) is a module if every vertex outside S is fully adjacent to S or fully non-adjacent to S. A module is said to be trivial if it is a singleton or the entire vertex set, and a graph without non-trivial modules is called prime. The vertex set of every graph G can be partitioned into modules H 1 , H 2 , . . . , H ℓ , some of which can be singletons. H = {H 1 , H 2 , . . . , H ℓ } is then called a modular decomposition of G. The quotient graph G/H of G has vertex set H and an edge between H i and H j whenever every vertex of H i is adjacent to every vertex of H j . By definition of a module, H i H j is not an edge of G/H if and only if there is no edge in G between H i and H j . We say that X

  strict half-graph of height t is (up to isomorphism) the graph with vertex set {a 1 , . . . , a t , b 1 , . . . , b t } and edge set {a i b j : i < j, i ∈ [t], j ∈ [t]}. One can see {a 1 , . . . , a t } oriented toward {b 1 , . . . , b t } in their realization of the relation < over the indices. The ℓ-cycle of strict half-graphs of height t is (up to isomorphism) the graph with vertex set

	{a p 1 , . . . , a p t : p ∈ [0, ℓ -1]} and edge set {a p i a p+1 mod ℓ j

  family of hypergraphs H has Vapnik-Chervonenkis (VC) density at most 1 if there is a constant c such that for every hypergraph H ∈ H and every X ⊆ V (H), |{X ∩ e : e ∈ E(H)}| ⩽ c • |X|. By extension, we may say that a graph class C has VC density at most 1 if the neighborhood hypergraph of every graph in C has VC density at most 1.

  at least c 2t+2 zones with a corner, hence mixed. Without loss of generality, we may assume that at least ⌈s/2⌉ column parts among C 1 , . . . , C s have at least c 2t+2 mixed zones when divided by, say, R 1 . Consider the column division {C ′ 1 , . . . , C ′ s ′ } with s ′ ⩾ ⌈s/2⌉, coarsening of {C 1 , . . . , C s } such that each part C ′ j contains exactly one column part C i with the property of the previous sentence. Let M ′ be a |R 1 |×s ′ 0, 1-matrix with a 1-entry at positions where the cell of (R 1 , {C ′ 1 , . . . , C ′ s ′ }) is mixed, and a 0-entry otherwise. Note that M ′ has at most ⌊s/2⌋ rows and s ′ ⩾ ⌈s/2⌉ columns. Moreover each column of M ′ contains by design at least c 2t+2 1-entries. By Theorem 20, M ′ admits a (2t + 2)-grid minor. Thus M has a (2t + 2)-mixed minor, which implies that M has twin-width larger than t by Theorem 21. ◀

	We conclude the following.

▶ Lemma 3. For every graph G of twin-width t and X

  If there is i ∈ [q] with X i ̸ = ∅ and |Y i | ⩾ |X i | + 2,then delete a vertex of Y i . ▶ Lemma 27. Let G be a graph and G ′ be a graph obtained by applying Reduction Rule 3. Then (G, k) is a yes-instance to Connected k-Vertex Cover if and only if (G ′ , k) is.

T . ◀ ▶ Proposition 24. Connected k-Vertex Cover admits a kernel on O t (k 2 ) vertices when the input graphs have twin-width at most t. ▶ Reduction Rule 3.

The definition of nowhere denseness being technical and unnecessary to the current paper, we refer the interested reader to[START_REF] Nesetril | Sparsity -Graphs, Structures, and Algorithms[END_REF]. Let us just mention that bounded-degree graphs, planar graphs, and proper (topological) minor-closed classes are all nowhere dense.

We will not need a definition of expansion here. Bounded expansion classes are more general than topological-minor-free classes and less general than nowhere dense classes.

Jan Arne Telle and Yngve Villanger. FPT algorithms for domination in sparse graphs and beyond. Theor. Comput. Sci., 770:62-68, 2019. doi:10.1016/j.tcs.2018.10.030.

Acknowledgments

We thank Noga Alon and Bart M. P. Jansen for independently asking whether k-Dominating Set admits a polynomial kernel on classes of bounded twin-width, an interesting question that led to our main result.

Proof. Let (G, k) be an instance of Connected k-Vertex Cover and let X be a vertex cover obtained using a 2-approximation algorithm for Min Vertex Cover (given by any maximal matching). If |X| ⩾ 2k + 1, an optimal vertex cover and thus an optimal connected vertex cover has size at least k + 1. Then one can correctly output a trivial no-instance. Henceforth we assume that |X| ⩽ 2k. Apply Reduction Rule 1 exhaustively, and let (G ′ , k) be the resulting instance. By Lemma 3 and by the construction of G ′ , V (G ′ ) \ X can be partitioned into at most 2 4c2t+2 • |X| modules and each module consists of at most k + 1 vertices. Therefore, V (G ′ ) has at most c t • (k + 1) + 2k vertices. That (G ′ , k) is an equivalent to (G, k) is implied by Lemma 23 Proof. Again let s be such that G ′ := G -s. We first check the forward direction. A c-capacitated vertex cover of G is not necessarily a c ′ -capacitated vertex cover of G ′ as we decreased the capacities of neighbors of s. However we claim that if G admits a c-capacitated vertex cover T of size at most k, then it also admits a c-capacitated vertex cover of G of size at most k not containing s. Indeed, if s ∈ T , then there exists a vertex s ′ ∈ S \ T and not that all neighbors of s ′ (thus s) are in T . Therefore, (T \ {s}) ∪ {s ′ } is a vertex cover of G of size at most k. It is further c-capacitated because c(s ′ ) ⩾ c(s). Now we may assume that T does not contains s. Set T is a c ′ -capacitated vertex cover of G ′ because the decrease of capacity of each vertex v ∈ N (s) by one unit is canceled out by the absence of edge sv in G ′ . Conversely, if there is a c ′ -capacitated vertex cover T of G ′ of size at most k, note that all neighbors of S \ {s} must be in T . Therefore, T is a c-capacitated vertex cover of G where each edge incident with s is covered by the residual capacity of the other endpoint. ◀ Therefore, Capacitated k-Vertex Cover admits a quadratic vertex kernel, which follows the proof of Proposition 24 verbatim. ▶ Proposition 26. Capacitated k-Vertex Cover admits a kernel on O t (k 2 ) vertices when the input graphs have twin-width at most t.

Theorem 2 is a direct consequence of Propositions 24 and 26.

Improved kernel for Connected k-Vertex Cover

We present here a kernelization algorithm for Connected k-Vertex Cover on bounded twin-width graphs which leads to an instance on O(k 1.5 ) vertices, and a simple linear kernel when the input class is further restricted to be sparse, that is, K s,s -free.

Let X be a vertex cover of G, and let X b (resp. X s ) be the subsets of X containing all vertices of X with at least k + 1, respectively at most k, neighbors in V (G) \ X. Let Y 1 , . . . , Y q be the partition of V (G) \ X into maximal modules. For each i ∈ [q], let X i be the neighbors of Y i in X s .

Twin-width and polynomial kernels

between X s and Y is decomposed into the edge sets of complete bipartite graphs on (Y i , X i ) over i ∈ [q], the number of edges between X s and Y is at least

and hence there are more than 2k 2 edges between X s and Y . With |X s | ⩽ 2k, this implies that there exists a vertex in X s which has more than k neighbors in Y , contradicting the definition of X s . To conclude, G ′ has at most

vertices as claimed. ◀

Note that the proof of Proposition 30 only uses the fact that the input graphs have VC density at most 1, so we in fact established Theorem 4.

Graphs of twin-width 1

Cycles on at least five vertices and their complements have twin-width 2. Thus graphs of twin-width 1 do not have induced cycles of length at least 5, nor their complements. In particular, they are perfect. Hence computing the independence, clique, and coloring numbers can be done in polynomial-time [START_REF] Grötschel | Corrigendum to our paper "the ellipsoid method and its consequences in combinatorial optimization[END_REF]. Graphs of twin-width 0 are cographs, and can be recognized in linear time [START_REF] Habib | A simple linear time algorithm for cograph recognition[END_REF]. It turns out that twin-width 1 graphs are also efficiently recognizable. For that, we need the following technical lemma.

▶ Lemma 31. Let G be a prime graph of twin-width 1, and let G = G n , . . . , G 2 , G 1 be a 1-contraction sequence. Then the trigraphs G i have exactly one red edge, except for G n and G 1 which have no red edge.

Proof. The idea of the proof is to start with the 3-vertex trigraph G 3 and to rewind the contraction sequence back to G n = G. Let a, b, c be the three vertices of G 3 . Since G 3 is a 1-trigraph, there is at most one red edge in G 3 . Since G is a prime graph, there has to be at least one red edge in G 3 , say between b and c. Furthermore, a has to be a vertex in G, otherwise a(G) is a module of size at least two in G. Moreover, a is adjacent to, say, b, but non-adjacent to the other vertex, c since otherwise b(G) ∪ c(G) is a module.

We show by induction the following property (P) for i ∈ [2, n -1]:

Property P: in G i , there is exactly one red edge, say, uv (u and v can depend on i) and all the vertices that are not u nor v are original vertices of G.

We already observed that Property P holds for G 3 . It also holds for G 2 because G contains no non-trivial module. Assuming that G i satisfies Property P for some i ∈ [3, n -2], let us prove that G i+1 also satisfies Property P. Let uv be the red edge in G i . By assumption, all the other vertices are vertices in G. Hence, the graph G i+1 is obtained from G i by splitting u or v, say u, into two vertices u 1 and u 2 . Now, there is at most one red edge in G i+1 [{u 1 , u 2 , v}]