Julien Baste
email: julien.baste@uni-ulm.de.

Ignasi Sau
email: ignasi.sau@lirmm.fr

Dimitrios M Thilikos

A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary

For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f (tw) • n O(1) , where tw is the treewidth of G. We determine the asymptotically optimal function f (tw), for each possible choice of H. Namely, we prove that, under the ETH, f (tw) = 2 Θ(tw) if H is a contraction of the chair or the banner, and f (tw) = 2 Θ(tw•log tw) otherwise. Prior to this work, such a complete characterization was only known when H is a planar graph with at most five vertices. For the upper bounds, we present an algorithm in time 2 Θ(tw•log tw) •n O(1) for the more general problem where all minor models of connected graphs in a finite family F need to be hit. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. In particular, this algorithm vastly generalizes a result of Jansen et al. [SODA 2014] for the particular case F = {K 5 , K 3,3 }. For the lower bounds, our reductions are based on a generic construction building on the one given by the authors in [IPEC 2018], which uses the framework introduced by Lokshtanov et al. [SODA 2011] to obtain superexponential lower bounds.

Introduction

Let F be a finite non-empty collection of non-empty graphs. In the F-M-Deletion problem, we are given a graph G and an integer k, and the objective is to decide whether there exists a set S ⊆ V (G) with |S| ≤ k such that G \ S does not contain any of the graphs in F as a minor. This problem belongs to the family of graph modification problems and has a big expressive power, as instantiations of it correspond, for instance, to Vertex Cover (F = {K 2 }), Feedback Vertex Set (F = {K 3 }), and Vertex Planarization (F = {K 5 , K 3,3 }). Note that if F contains a graph with at least one edge, then F-M-Deletion is NP-hard [START_REF] Lewis | The nodedeletion problem for hereditary properties is NPcomplete[END_REF].

We study the parameterized complexity of F-M-Deletion in terms of the treewidth of the input graph (while the size of k is not bounded). Since the property of containing a graph as a minor can be expressed in Monadic Second Order logic [START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF], by Courcelle's theorem [START_REF] Courcelle | The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs[END_REF], F-M-Deletion can be solved in time O * (f (tw)) on graphs with treewidth at most tw, where f is some computable function 1 . As the function f (tw) given by Courcelle's theorem is typically enormous, our goal is to determine, for a fixed collection F, which is the best possible such function f that one can (asymptotically) hope for, subject to reasonable complexity assumptions. Besides being an interesting objective in its own, optimizing the running time of algorithms parameterized by treewidth has usually side effects. Indeed, black-box subroutines parameterized by treewidth are nowadays ubiquitous in parameterized [START_REF] Cygan | Parameterized Algorithms[END_REF], exact [START_REF] Fomin | Exact Exponential Algorithms[END_REF], and approximation [START_REF] Williamson | The Design of Approximation Algorithms[END_REF] algorithms.

Previous work. This line of research has attracted considerable attention in the parameterized complexity community during the last years. For instance, Vertex Cover is easily solvable in time O * (2 O(tw) ), called single-exponential, by standard dynamic programming techniques, and no algorithm with running time O * (2 o(tw) ) exists, unless the Exponential Time Hypothesis (ETH)2 fails [START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF]. For Feedback Vertex Set, standard dynamic programming techniques give a running time of O * (2 O(tw•log tw) ), while the lower bound under the ETH [START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF] is again O * (2 o(tw) ).

This gap remained open for a while, until Cygan et al. [START_REF] Cygan | Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time[END_REF] presented an optimal (randomized) algorithm running in time O * (2 O(tw) ), introducing the celebrated Cut & Count technique. This article triggered several other (deterministic) techniques to obtain singleexponential algorithms for so-called connectivity problems on graphs of bounded treewidth, mostly based on algebraic tools [START_REF] Bodlaender | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF][START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF].

Concerning Vertex Planarization, Jansen et al. [START_REF] Jansen | A near-optimal planarization algorithm[END_REF] presented an algorithm running in time O * (2 O(tw•log tw) ) as a crucial subroutine in an algorithm running in time O * (2 O(k•log k) ). Marcin Pilipczuk [START_REF] Pilipczuk | A tight lower bound for Vertex Planarization on graphs of bounded treewidth[END_REF] proved afterwards that this running time is optimal under the ETH, by using the framework introduced by Lokshtanov et al. [START_REF] Lokshtanov | Slightly superexponential parameterized problems[END_REF] for proving superexponential lower bounds.

Generalizing the above algorithm, the main technical contribution of the recent paper of Kociumaka and Pilipczuk [START_REF] Kociumaka | Deleting vertices to graphs of bounded genus[END_REF] is an algorithm running in time O * (2 O((tw+g)•log(tw+g)) ) to solve the Genus Vertex Deletion problem, which consists in deleting the minimum number of vertices from an input graph in order to obtain a graph embeddable on a surface of Euler genus at most g.

In a recent pair of papers [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF][START_REF]A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth[END_REF], we initiated a systematic study of the complexity of F-M-Deletion, parameterized by treewidth 3 . Before stating these results, we say that a collection F is connected if it contains only connected graphs. In [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] we showed that, for every F, F-M-Deletion can be solved in time O * 2 2 O(tw•log tw) , and that if F is connected and contains a planar graph, the running time can be improved to O * (2 O(tw•log tw) ). If the input graph G is planar or, more generally, embedded in a surface of bounded genus, and F is connected, then the running time can be further improved to O * (2 O(tw) ). We also provided single-exponential algorithms for the cases where F ∈ {{P 3 }, {P 4 }, {C 4 }}. Concerning lower bounds under the ETH, we proved that for any connected F, F-M-Deletion cannot be solved in time O * (2 o(tw) ), even if the input graph G is planar. Inspired by the reduction of Pilipczuk [START_REF] Pilipczuk | A tight lower bound for Vertex Planarization on graphs of bounded treewidth[END_REF], we proved that the problem cannot be solved in time O * (2 o(tw•log tw) ) for some families of collections F, for example, when all graphs in F are planar and 3connected. In the subsequent paper [START_REF]A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth[END_REF], we focused on small planar graphs. Namely, we classified the optimal asymptotic complexity of {H}-M-Deletion when H is a connected planar graph on at most five vertices. To achieve that, we provided single-exponential algorithms for a number of small patterns not considered in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] and superexponential lower bounds for the remaining cases, this time inspired by a reduction of Bonnet et al. [START_REF] Bonnet | Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms[END_REF] for generalized feedback vertex set problems. Full proofs of the results in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF][START_REF]A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth[END_REF] are available at [START_REF] Baste | Hitting minors on bounded treewidth graphs[END_REF].

Our results. In this article we make significant steps towards a complete classification of the complexity of the F-M-Deletion problem parameterized by treewidth, by improving both the known upper and lower bounds. Namely, we prove the following results:

Our main contribution is an algorithm to solve F-M-Deletion in time O * (2 O(tw•log tw) ) for every connected collection F, hence dropping the condition that it contains a planar graph, which was critically needed in the algorithm presented in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] in order to bound the treewidth of an F-minor-free graph. Besides largely improving our previous results [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF][START_REF]A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth[END_REF], this algorithm also generalizes the one for F = {K 5 , K 3,3 } given by Jansen et al. [START_REF] Jansen | A near-optimal planarization algorithm[END_REF], which is based on embeddings. It can be interpreted as an exponential "collapse" of the natural dynamic programming algorithm running in time O * 2 2 O(tw•log tw) given in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF]. The algorithm is quite involved, and we provide an overview of it in §2.

Concerning lower bounds, we vastly improve all previous super-exponential lower bounds [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF][START_REF]A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth[END_REF][START_REF] Pilipczuk | A tight lower bound for Vertex Planarization on graphs of bounded treewidth[END_REF] for F-M-Deletion by proving that for every connected graph H that is not a contraction of the chair or the banner, depicted in Figure 1, {H}-M-Deletion cannot be solved in time O * (2 o(tw•log tw) ) under the ETH. We also prove a lower bound of O * (2 o(tw•log tw) ) for F-M-Deletion when F is any finite non-empty subset of all connected graphs that contain a block with at least five edges. In particular, the former result applies to K 5 and all the connected graphs with at least six vertices.

Our reductions are based on a generic framework that generalizes the one given in [START_REF]A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth[END_REF], which was inspired by a reduction of Bonnet et al. [START_REF] Bonnet | Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms[END_REF]. These lower bounds also subsume the ones in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF], which were proved using a different reduction inspired by the one of Pilipczuk [START_REF] Pilipczuk | A tight lower bound for Vertex Planarization on graphs of bounded treewidth[END_REF]. More precisely, in [START_REF]A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth[END_REF] we proved subexponential lower bounds for P 5 , K 1,i with i ≥ 4, K 2,i and θ i for i ≥ 3 (θ i is the graph consisting of two vertices and i parallel edges), and the following graphs (see the full version for a figure containing these graphs): the px, the kite, the dart, the bull, the butterfly, the cricket, and the co-banner. All these reductions were based on a general construction, which is a less general version of the construction that we present here, and then we needed particular small gadgets to deal with each of the graphs.

Here we present a more general version of this approach that has the following advantage: in order to prove lower bounds, we need to distinguish cases not depending on particular instantiations of the collection F, but on general structural properties of the graphs in F, like containing a block with at least five edges or the number and relative position of cut vertices and cycles.

The above results, together with the lower and upper bounds for planar graphs on at most five vertices given in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF][START_REF]A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth[END_REF] and the known cases [START_REF] Tu | On the vertex cover P 3 problem parameterized by treewidth[END_REF], and F = {C 3 } [START_REF] Bodlaender | Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth[END_REF][START_REF] Cygan | Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time[END_REF] imply the following complexity dichotomy when F consists of a single connected graph H, which we suppose to have at least one edge.

F = {P 2 } [14, 27], F = {P 3 } [2,
Theorem 1.1. Let H be a connected graph. Under the ETH, {H}-M-Deletion is solvable in time 4• 2 Θ(tw) • n O (1) , if H is a contraction of the chair or the banner, and

• 2 Θ(tw•log tw) • n O(1) , otherwise.
Note that if |V (H)| ≥ 6, then H is not a contraction of the chair or the banner, and therefore the second item above applies. Note also that K 4 and the diamond are the only graphs on at most four vertices for which the problem is solvable in time O * (2 Θ(tw•log tw) ) and that the chair and the bannerare the only graphs on at least five vertices for which the problem is solvable in time O * (2 Θ(tw) ).

The crucial role payed by the chair and the bannerin the complexity dichotomy may seem surprising at first sight. In fact, we realized a posteriori that the "easy" cases can be succinctly described in terms of the chair and the banner. Note that the "easy" graphs can be equivalently characterized as those that are minors of the banner, with the exception of P 5 . Nevertheless, there is some intuitive reason for which excluding the chair or the bannerconstitutes the horizon on the existence of single-exponential algorithms. Namely, focusing on the banner, every connected component (with at least five vertices) of a graph that excludes the banneras a minor is either a cycle (of any length) or a tree in which some vertices have been replaced by triangles; both such types of components can be maintained by a dynamic programming algorithm in single-exponential time [START_REF] Baste | Hitting minors on bounded treewidth graphs[END_REF].

A similar situation occurs when excluding the chair. It appears that if the characterization of the allowed connected components is enriched in some way, such as restricting the length of the allowed cycles or forbidding certain degrees, the problem becomes inherently more difficult, inducing a transition from time O * (2 Θ(tw) ) to O * (2 Θ(tw•log tw) ).

Organization of the paper. In §2 we provide a high-level overview of the algorithm running in time O * (2 O(tw•log tw) ). In §3 we give some preliminaries. In §4 we deal with flat walls, in §5 we apply the irrelevant vertex technique in the context of boundaried graphs, and in §6 we use this in order to bound the size of the dynamic programming tables. The lower bounds can be found in the full version. We conclude the article in §7. Due to space limitations, the proofs of all the results marked with '( )' can be found in the full version.

Overview of the algorithm

In order to obtain our algorithm of time O * (2 O(tw•log tw) ) for every connected collection F, our approach can be streamlined as follows. We use the machinery of boundaried graphs, equivalence relations, and representatives originating in the seminal work of Bodlaender et al. [START_REF] Bodlaender | Meta) Kernelization[END_REF] and subsequently used, for instance, in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF][START_REF] Fomin | Bidimensionality and ker-969 Copyright[END_REF][START_REF] Garnero | Explicit Linear Kernels via Dynamic Programming[END_REF][START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF]. Let h be a constant depending only on the collection F (to be defined in the formal description of the algorithm) and let t be a positive integer that is at most the treewidth of the input graph plus one. Skipping several technical details, a t-boundaried graph is a graph with a distinguished set of vertices -its boundary-labeled bijectively with integers from the set [t]. We say that two t-boundaried graphs are h-equivalent if for any other t-boundaried graph that we can "glue" to each of them, resulting in graphs G 1 and G 2 , and every graph H on at most h vertices, H is a minor of G 1 if and only if it is a minor of G 2 (see §3 for the precise definitions). Let R (t) h be a set of minimum-sized representatives of this equivalence relation. Since h-equivalent (boundaried) graphs have the same behavior in terms of eventual occurrences of minors of size up to h, there is a generic dynamic programming algorithm (already used in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF]) to solve F-M-Deletion on a rooted tree decomposition of the input graph, via a typical bottom-up approach: at every bag B of the tree decomposition, naturally associated with a t-boundaried graph G B , and for every representative R ∈ R (t) h , store the minimum size of a set S ⊆ V (G B ) such that the graph G B \ S is h-equivalent to R (cf. Subsection 6.2 for some more details). This yields an algorithm running in time O * (|R (t) h | 2 ), and therefore it suffices to prove that

|R (t) h | = 2 O h (t•log t)
, where the notation 'O h ' means that the hidden constants depend only on h. Since we may assume that the graphs in R (t) h exclude some graph on at most h vertices as a minor (as all those that do not are h-equivalent), hence they have a linear number of edges, it is enough to prove that, for every R ∈ R

(t) h , it holds that |V (R)| = O h (t). (2.1)
Note that this is indeed sufficient as there are at most

|V (R)| 2 |E(R)| = 2 O h (|V (R)| log |V (R)||) representatives.
In order to prove (2.1), we combine a number of different techniques, which we proceed to discuss informally, and that are schematically summarized in Figure 2:

t ≤ tw(G) + 1 h = f (F) R ∈ R (
|V (R)| = O h (t) [Lemma 6.4] |R (t) h | = 2 Oh(t•log t) [Corollary 6.1] Algorithm in time O * (2 Oh(tw•log tw) ) for connected F [Theorem 1.1] [34]
Reduce protrusions [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] Sparsity of the representatives DP algorithm from [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] Figure 2: Diagram of the algorithm in time O * (2 O(tw•log tw) ) for connected F.

We use the Flat Wall Theorem of Robertson and Seymour [START_REF] Robertson | Graph Minors. XIII. The Disjoint Paths Problem[END_REF], in particular the recent optimized versions by Kawarabayashi et al. [START_REF] Kawarabayashi | A new proof of the flat wall theorem[END_REF] and by Chuzhoy [START_REF] Chuzhoy | Improved bounds for the flat wall theorem[END_REF]. In a nutshell, this theorem says that every K h -minor-free graph G has a set of vertices A ⊆ V (G) -called apiceswith |A| = O h (1) such that G \ A contains a flat wall of height Ω h (tw(G)). Here, the definition of "flat wall" is quite involved and is detailed in §4; it essentially means a subgraph that has a bidimensional grid-like structure, separated from the rest of the graph by its perimeter, and that is "close" to being planar, in the sense that it can be embedded in the plane in a way that its potentially non-planar pieces, called flaps, have a well-defined structure along larger pieces called bricks.

We say that a vertex set S affects a flat wall if some vertex within the wall has a neighbor in S that is not an apex. With these definitions at hand, we define a parameter, denoted by p h,r in this informal description, mapping every graph G to the smallest size of a vertex set that affects all flat walls with at most h apices and height at least r in G. It is not hard to prove that the parameter p h,r has a "bidimensional" behavior [START_REF] Demaine | Subexponential parameterized algorithms on graphs of bounded genus and Hminor-free graphs[END_REF][START_REF] Fomin | Bidimensionality[END_REF], in the sense that its value on a flat wall depends quadratically on the height of the wall (Lemma 4.1) and separable [START_REF] Bodlaender | Meta) Kernelization[END_REF][START_REF] Fomin | Bidimensionality[END_REF][START_REF] Fomin | Bidimensionality and ker-969 Copyright[END_REF]

(Lemma 4.2).
A subwall of a flat wall is h-homogeneous if for every brick of the subwall, the flaps within that brick have the same variety of h-folios, that is, the same sets of "boundaried" minors of detail at most h (the detail of a boundaried graph is the maximum between its number of edges and its number of non-boundary vertices). This notion is inspired (but is not the same) by the one defined by Robertson and Seymour in [START_REF] Robertson | Graph Minors. XIII. The Disjoint Paths Problem[END_REF]. Using standard "zooming" arguments, we can prove that, given a flat wall, we can find a large h-homogeneous subwall inside it (Lemma 4.3). Homogeneous subwalls are very useful because, as we explain below, they permit the application of the irrelevant vertex technique adapted to our purposes.

The most complicated step towards proving (2.1) is to find an "irrelevant" vertex inside a sufficiently large (in terms of h) flat wall of a boundaried graph that is not affected by its boundary (Theorem 5.2). Informally, here "irrelevant" means a non-boundary vertex of R that can be avoided by any minor model of a graph on at most h vertices and edges that traverses the boundary of R, no matter the graph that may be glued to it and no matter how this model traverses the boundary of R; see §5 for the precise definition. The irrelevant vertex technique originated in the seminal work of Robertson and Seymour [START_REF] Robertson | Graph Minors. XIII. The Disjoint Paths Problem[END_REF][START_REF]XXII. Irrelevant vertices in linkage problems[END_REF] and has become a very useful tool used in various kinds of linkage and cut problems [START_REF] Adler | Irrelevant vertices for the planar Disjoint Paths Problem[END_REF][START_REF] Jansen | A near-optimal planarization algorithm[END_REF][START_REF] Kociumaka | Deleting vertices to graphs of bounded genus[END_REF][START_REF] Kratsch | Representative Sets and Irrelevant Vertices: New Tools for Kernelization[END_REF][START_REF] Reed | Rooted routing in the plane[END_REF]. Nevertheless, given the nature of our setting, it is critical that the size of the flat wall where the irrelevant vertex appears does not depend on the boundary size. To the best of our knowledge, this property is not guaranteed by the existing results on the irrelevant vertex technique (such as [44, (10.2)] and its subsequent proof in [START_REF]XXII. Irrelevant vertices in linkage problems[END_REF]). To achieve it and, moreover, in order to make an estimation of the parametric dependencies, we develop a self-reliant theoretical framework that uses the following ingredients:

• With a flat wall W we associate a bipartite graph W , which we call its leveling; cf. Subsection 4.3 for the precise definition. In particular, this graph has a vertex for every flap of the flat wall, and can be embedded in a disk in a planar way.

• It turns out to be more convenient to work with topological minor models instead of minor models; we can afford it since for every graph H there are at most f (H) different topological minor minimal graphs that contain H as a minor (Observation 1).

The reason for this is that it is easier to deal with the branch vertices of a topological minor model in the analysis. Given a topological minor model, we say that a flap of a wall is dirty if it contains a branch vertex of the model, or there is an edge from the flap to an apex vertex of the wall. We also define the leveling of a topological minor model, and we equip its dirty flags with colors that encode their h-folios. We now proceed to explain how to reroute the colored leveling of a topological minor model.

• In order to reroute (colored levelings of) topological minor models, it will be helpful to use railed annuli, a structure introduced in [START_REF] Kaminski | Contraction checking in graphs on surfaces[END_REF] that occurs as a subgraph inside a flat wall (Proposition 5.1) and that has the following nice property, recently proved in [START_REF] Golovach | Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable[END_REF] (Proposition 5.2): if a railed annulus is large enough compared to h, every topological minor model of a graph on at most h vertices traversing it can be rerouted so that the branch vertices are preserved and such that, more importantly, the intersection of the new model with a large prescribed part of the railed annulus is confined, in the sense that it is only allowed to use a well-defined set of paths in that part, which does not depend on the original model.

• We also need a technical result with a graph drawing flavor (Lemma 5.1) guaranteeing that large enough railed annuli contain topological minor models of every graph of maximum degree three with the property, in particular, that certain vertices are pairwise far apart in the embedding. Using this result and the one in [START_REF] Golovach | Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable[END_REF] mentioned above, we can finally prove (Theorem 5.1) that every topological minor model of a graph H inside a graph with a large flat wall W can be "collapsed" inside the wall, in the following sense: G contains another topological minor model of a graph H , such that H is a minor of H , and such that the new model avoids the central part of the annulus; here is where the irrelevant vertex will be found.

• To conclude, it just remains to "lift" the constructed embedding of the colored leveling of the topological minor to an embedding of the "original" minor in the flat wall (Theorem 5.2). For that, we exploit the fact that we have rerouted the model inside an hhomogeneous subwall not affected by the boundary, which allows to mimic the behavior of the original minor inside the flaps of the wall, using that all bricks have the same variety of h-folios.

The above arguments, incorporated in the proof of Theorem

5.2, imply that if R ∈ R (t)
h is a minimumsized representative, then its boundary affects all large enough flat walls, as otherwise we could remove an irrelevant vertex and find a smaller equivalent representative. In particular, it follows that, for every R ∈ R

(t) h , we have p h,r (R) ≤ t (Corollary 5.1).
Combining that the parameter p h,r is "bidimensional" and separable along with the fact that p h,r (R) ≤ t for every R ∈ R (t) h , we prove in Lemma 6.2 (whose proof is an adaptation of [START_REF]Bidimensionality and kernels[END_REF]Lemma 3.6] -see also [START_REF] Fomin | Bidimensionality and ker-969 Copyright[END_REF]) that every representative R ∈ R (t) h has a vertex subset S containing its boundary, with |S| ≤ 2t, whose removal leaves a graph of treewidth bounded by a function of h; such a set is called a treewidth modulator.

Once we have a treewidth modulator of size O(t) of a representative R, all that remains is to pipeline it with known techniques to compute an appropriate protrusion decomposition [START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF] (Lemma 6.3) and to reduce protrusions to smaller equivalent ones of size bounded by a function of h -we use the version given in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] adapted to the F-M-Deletion problem-(Lemma 6.4), imply-

ing that |V (R)| = O h (t) for every every R ∈ R (t)
h and concluding the proof of (2.1).

It should be noted that all the items above do not need to be converted into an algorithm, they are just used in the analysis: the conclusion is that

if R ∈ R (t) h is a minimum-sized representative, then |V (R)| = O h (t),
as otherwise some reduction rule could be applied to it (either by removing an irrelevant vertex or by protrusion replacement), thus obtaining an equivalent representative of smaller size and contradicting its minimality. Our main result can be formally stated as follows.

c F such that the F-M-Deletion problem is solvable in time c tw•log tw F •n on n-vertex graphs of treewidth at most tw.
In the full version we provide an estimation of the constant c F in Theorem 2.1 based on the parametric dependencies of the Unique Linkage Theorem [START_REF] Kawarabayashi | A shorter proof of the graph minor algorithm: the unique linkage theorem[END_REF][START_REF]XXII. Irrelevant vertices in linkage problems[END_REF].

Preliminaries

Sets and integers. We denote by N the set of nonnegative integers and we set N + = N \ {0}. Given two integers p and q, the set [p, q] refers to the set of every integer r such that p ≤ r ≤ q. For an integer p ≥ 1, we set

[p] = [1, p] and N ≥p = N \ [0, p -1] . In the set [1, k] × [1, k] , a row is a set {i} × [1, k] and a column is a set [1, k] × {i} for some i ∈ [1, k] .
For a set S, we denote by 2 S the set of all the subsets of S.

Graphs. All the graphs that we consider in this paper are undirected, finite, and without loops or multiple edges. We use standard graph-theoretic notation, and we refer the reader to [START_REF] Diestel | Graph Theory[END_REF] for any undefined terminology. Let G be a graph. We say that a pair Treewidth. Let G = (V, E) be a graph. A tree decomposition of G is a pair (T, X = {X t } t∈V (T ) ) where T is a tree and X is a collection of subsets of V such that:

(L, R) ∈ 2 V (G) × 2 V (G) is a separation of G if L ∪ R = V (G)
•

t∈V (T ) X t = V, • ∀e = {u, v} ∈ E, ∃t ∈ V (T ) : {u, v} ⊆ X t , and • ∀v ∈ V , T [{t | v ∈ X t }] is connected.
We call the vertices of T nodes and the sets in X bags of the tree decomposition (T, X ). The width of (T, X ) is equal to max{|X t | -1 | t ∈ V (T )} and the treewidth of G is the minimum width over all tree decompositions of G. We denote the treewidth of a graph G by tw(G).

For t ∈ N, we say that a set

S ⊆ V (G) is a t- treewidth modulator of G if tw(G \ S) ≤ t. Boundaried graphs. Let t ∈ N. A t-boundaried graph is a triple G = (G, B, ρ) where G is a graph, B ⊆ V (G), |B| = t, and ρ : B → [t] is a bijection. We say that G 1 = (G 1 , B 1 , ρ 1 ) and G 2 = (G 2 , B 2 , ρ 2 ) are isomorphic if there is an isomorphism from G 1 to G 2 that extends the bijection ρ -1 2 • ρ 1 .
The triple (G, B, ρ) is a boundaried graph if it is a t-boundaried graph for some t ∈ N. As in [START_REF] Robertson | Graph Minors. XIII. The Disjoint Paths Problem[END_REF], we define the detail of a boundaried graph G = (G, B, ρ) as detail(G) := max{|E(G)|, |V (G) \ B|}. We denote by B (t) the set of all (pairwise non-isomorphic) t-boundaried graphs and by B (t) h the set of all (pairwise non-isomorphic) tboundaried graphs with detail at most h. We also set B = t∈N B (t) .

Minors and topological minors of boundaried graphs. We say that a t-boundaried graph

G 1 = (G 1 , B 1 , ρ 1 ) is a minor of a t-boundaried graph G 2 = (G 2 , B 2 , ρ 2 ), denoted by G 1 m G 2 ,
if there is a sequence of removals of non-boundary vertices, edge removals, and edge contractions in G 2 , disallowing contractions of edges with both endpoints in B 2 , that transforms G 2 to a boundaried graph that is isomorphic to G 1 (during edge contractions, boundary vertices prevail). Note that this extends the usual definition of minors in graphs without boundary.

We say that (M, T ) is a tm-pair if M is a graph, T ⊆ V (M ), and all vertices in V (M ) \ T have degree two. We denote by diss(M, T ) the graph obtained from M by dissolving all vertices in V (M ) \ T, that is, for every vertex v ∈ V (M ) \ T, with neighbors u and w, we delete v and, if u and w are not adjacent, we add the edge {u, w}. A tm-pair of a graph G is a tm-pair (M, T ) where if M is a subgraph of G.

Given two graphs H and G, we say that a tmpair (M, T ) of G is a topological minor model of H in G if H is isomorphic to diss(M, T ). We denote this isomorphism by σ M,T : V (H) → T. We call the vertices in T branch vertices of (M, T ). We call each path in M between two distinct branch vertices and with no internal branch vertices a subdivision path of (M, T ) and the internal vertices of such paths, i.e., the vertices of V (M )\T, are the subdivision vertices of (M, T ). We also extend σ M,T so to also map each e = {x, y} ∈ E(H) to the subdivision path of M with endpoints σ M,T (x) and σ M,T (y). Furthermore, we extend σ M,T so to also map each subgraph H of H to the subgraph of M consisting of the vertices of σ M,T (T ) and the paths in σ M,T (e), e ∈ E(H ).

If M = (M, B, ρ) ∈ B and T ⊆ V (M ) with B ⊆ T, we call (M, T ) a btm-pair and we define diss(M, T ) = (diss(M, T ), B, ρ). Note that we do not permit dissolution of boundary vertices, as we consider all of them to be branch vertices. If G = (G, B, ρ) is a boundaried graph and (M, T ) is a tm-pair of G where B ⊆ T, then we say that (M, T ), where M = (M, B, ρ),

is a btm-pair of G = (G, B, ρ). Let G i = (G i , B i , ρ i ), i ∈ [2]. We say that G 1 is a topological minor of G 2 , denoted by G 1 tm G 2 , if G 2 has a btm-pair (M, T ) such that diss(M, T ) is isomorphic to G 1 .
Given a G = (G, B, ρ) ∈ B, we define ext(G) as the set containing every topological minor minimal boundaried graph G = (G , B, ρ) among those that contain G as a minor. Notice that we insist that B and ρ are the same for all graphs in ext(G). Moreover, we do not consider isomorphic boundaried graphs in ext(G) as different graphs. The set ext(G) helps us to express the minor relation in terms of the topological minor relation because of the following simple observation.

Observation 1. If G 1 , G 2 ∈ B, then G 1 m G 2 ⇐⇒ ∃G ∈ ext(G 2 ) : G 1 tm G. Moreover, there is a function f 1 : N → N such that if G is a boundaried graph with detail h, then every graph in ext(G) has detail at most f 1 (h). Folios. We define the h-folio of G = (G, B, ρ) ∈ B: h-folio(G) = {G ∈ B | G tm G ∧ G has detail ≤ h}.
Using the fact that an h-folio is a collection of K h+1minor-free boundaried graphs, it follows that the h-folio of a t-boundaried graph has at most 2 O((h+t)•log(h+t) elements. Therefore the number of distinct h-folios of tboundaried graphs is given by the following lemma (also observed in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF]).

Lemma 3.1. For every t, h ∈ N, |{h-folio(G) | G ∈ B (t) h }| = 2 2 O((h+t)•log(h+t)) .
Equivalent boundaried graphs and representatives. We say that two boundaried graphs

G 1 = (G 1 , B 1 , ρ 1 ) and G 2 = (G 2 , B 2 , ρ 2 ) are compatible if ρ -1 2 •ρ 1 is an isomorphism from G 1 [B 1 ] to G 2 [B 2 ]. Given two compatible boundaried graphs G 1 = (G 1 , B 1 , ρ 1 )
and G 2 = (G 2 , B 2 , ρ 2 ), we define G 1 ⊕ G 2 as the graph obtained if we take the disjoint union of G 1 and G 2 and, for every i ∈ [|B 1 |], we identify vertices ρ -1 1 (i) and ρ -1 2 (i).

Given h ∈ N, we say that two boundaried graphs G 1 and G 2 are h-equivalent, denoted by G 1 ≡ h G 2 , if they are compatible and, for every graph H on at most h vertices and h edges and every boundaried graph F that is compatible with G 1 (hence, with G 2 as well), it holds that

H m F ⊕ G 1 ⇐⇒ H m F ⊕ G 2 . (3.2)
Note that ≡ h is an equivalence relation on B. A minimum-sized (in terms of number of vertices) element of an equivalence class of ≡ h is called representative of ≡ h . A set of t-representatives for ≡ h is a collection containing a minimum-sized representative for each equivalence class of ≡ h . Given t, h ∈ N, we denote by R (t) h a set of t-representatives for ≡ h .

Let F be a finite non-empty collection of nonempty graphs; we call such a collection proper. A proper collection is called connected if all its graphs are connected. We extend the minor relation to F such that, given a graph G, F m G if and only if there exists a graph H ∈ F such that H m G. We also denote ex m (F) = {G | F m G}, i.e., ex m (F) is the class of graphs that do not contain any graph in F as a minor.

Definition of the problem. Let F be a proper collection. We define the graph parameter m F as the function that maps graphs to non-negative integers as follows:

m F (G) = min{|S| | S ⊆ V (G) ∧ G \ S ∈ ex m (F)}.
The main objective of this paper is to study the problem of computing the parameter m F for graphs of bounded treewidth. The corresponding decision problem is formally defined as follows.

F-M-Deletion

Input: A graph G and an integer k ∈ N. Parameter: The treewidth of G.

Output: Is m F (G) ≤ k?
At this point, we wish to stress that the folioequivalence defined in (3.2) is related but is not the same as the one defined by "having the same h-folio". Indeed, observe first that if G 1 and G 2 are compatible t-boundaried graphs and h-folio(G 1 ) = h-folio(G 2 ) then G 1 ≡ h G 2 , therefore the folio-equivalence is a refinement of ≡ h . In fact, a dynamic programming procedure for solving F-M-Deletion can also be based on the folio-equivalence, and this has already been done in the general algorithm in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF], which has a double-exponential parametric dependence due to the bound of Lemma 3.1. In this paper we build our dynamic programming on the equivalence ≡ h and we essentially prove that ≡ h is "coarse enough" so to reduce the double-exponential parametric dependence of the dynamic programming to a single-exponential one. In fact, this has already been done in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] for the case where F contains some planar graph, as this structural restriction directly implies an upper bound on the treewidth of the representatives. To deal with the general case, the only structural restriction for the (non-trivial) representatives is the exclusion of H as a minor. All the combinatorial machinery that we introduce in the next two sections is intended to deal with the structure of this general and (more entangled) setting.

In this section we deal with flat walls. More precisely, in Subsection 4.1 we define them and we state the Flat Wall Theorem of Robertson and Seymour [START_REF] Robertson | Graph Minors. XIII. The Disjoint Paths Problem[END_REF], using the terminology of [START_REF] Kawarabayashi | A new proof of the flat wall theorem[END_REF]. In Subsection 4.2 we define a graph parameter related to flat walls and prove that it behaves bidimensionally and is separable. Finally, in Subsection 4.3 we define homogeneous subwalls and prove that a flat wall contains a large homogeneous subwall.

4.1 The Flat Wall Theorem Before defining flat walls, we need to introduce walls and renditions, following the recent framework of [START_REF] Kawarabayashi | A new proof of the flat wall theorem[END_REF].

Walls. Let k, r ∈ N. The (k × r)-grid is the Cartesian product of two paths on k and r vertices, respectively. An elementary r-wall, for some odd r ≥ 3, is the graph obtained from a (2r × r)-grid with vertices (x, y) ∈ [2r] × [r], after the removal of the "vertical" edges {(x, y), (x, y + 1)} for odd x + y, and then the removal of all vertices of degree one. Notice that, as r ≥ 3, an elementary r-wall is a planar graph that has a unique (up to topological isomorphism) embedding in the plane R 2 such that all its finite faces are incident to exactly six edges. The perimeter of an elementary r-wall is the cycle bounding its infinite face, while the cycles bounding its finite faces are called bricks. Also, the vertices in the perimeter of an elementary r-wall that have degree two are called pegs, while the vertices (1, 1), (2, r), (2r -1, 1), (2r, r) are called corners (notice that the corners are also pegs).

Given an elementary r-wall W , some i ∈ {1, 3, . . . , 2r -1}, and i = (i + 1)/2, the i -th vertical path of W is the one whose vertices, in order of appearance, are (i, 1), (i, 2), (i + 1, 2), (i + 1, 3), (i, 3), (i, 4), (i + 1, 4), (i + 1, 5), (i, 5), . . . , (i, r -2), (i, r -1), (i + 1, r -1), (i + 1, r). Also, given some j ∈ [2, r -1] the jth horizontal path of W is the one whose vertices, in order of appearance, are (1, j), (2, j), . . . , (2r, j). The first horizontal path is the one containing the vertices (1, 1), (2, 1), . . . , (2r-1, 1) while the r-th horizontal path is the one containing the vertices (1, r), (2, r), . . . , (2r, r). We call these two last paths the lowest and the highest paths of W, respectively.

An r-wall is any graph W obtained from an elementary r-wall W after subdividing edges. The following theorem of Kawarabayashi and Kobayashi [START_REF] Kawarabayashi | Linear min-max relation between the treewidth of Hminor-free graphs and its largest grid[END_REF] provides a linear relation between the treewidth and the height of a largest wall in a minor-free graph. Theorem 4.1. There is a function f 2 : N → N such that, for every q, r ∈ N and every K q -minor-free graph G, if tw(G) ≥ f 2 (q) • r, then G contains an r-wall. In particular, one may choose f 2 (q) = 2 O(q 2 log q) . We call the vertices of an r-wall W that where added after the subdivision operations subdivision vertices, while we call the rest of the vertices (i.e., those of W ) branch vertices. A cycle of W is a brick (resp. the perimeter) of W if its branch vertices are the vertices of a brick (resp. the perimeter) of W . We denote by C(W ) the set of all cycles of W , by bricks(W ) the set of all the bricks of W , and we use D(W ) in order to denote the perimeter of the wall W.

A vertical (resp. horizontal ) path of W is one whose branch vertices are the vertices of a vertical (resp. horizontal) path of W . Notice that the perimeter and the bricks of an r-wall W are uniquely defined regardless of the choice of the elementary r-wall W . A subwall of W is any subgraph W of W that is an r -wall, with r ≤ r, and such the vertical (resp. horizontal) paths of W are subpaths of the vertical (resp. horizontal) paths of W.

Given an r-wall W, we say that a pair (P, C) ⊆ D(W ) × D(W ) is a choice of pegs and corners for W if W is the subdivision of an elementary r-wall W where P and C are the pegs and the corners of W , respectively (clearly, C ⊆ P ). A subgraph W of a graph G is called a wall of G if W is an r-wall for some odd r ≥ 3 and we refer to r as the height of the wall W.

The layers of an r-wall W are recursively defined as follows. The first layer of W is its perimeter. For i = 2, . . . , (r -1)/2, the i-th layer of W is the (i-1)-th layer of the subwall W obtained from W after removing from W its perimeter and removing recursively all occurring vertices of degree one. The central vertices of an r-wall are its two branch vertices that do not belong to any layer. See Figure 3 for an illustration of these notions. Notice that, given a ∆-painting Γ, the pair (N (Γ), {c ∩ N | c ∈ C(Γ)}) is a hypergraph whose hyperedges have cardinality at most three, and Γ can be seen as a plane embedding of this hypergraph in ∆.

Let G be a graph, and let Ω be a cyclic permutation of a subset of V (G) that we denote by V (Ω). By an Ωrendition of G we mean a triple (Γ, σ, π), where

• Γ is a ∆-painting for some closed disk ∆,

• π : N (Γ) → V (G) is an injection, and We say that an Ω-rendition (Γ, σ, π) of G is tight if the following conditions are satisfied:

• σ assigns to each cell c ∈ C(Γ) a subgraph σ(c) of G, such that (1) G = c∈C(Γ) σ(c), (2)
1. for every c ∈ C(Γ) there is a path in σ(c) between any two vertices in π(c ∩ N ) and 2. there is no other Ω-rendition of G satisfying Condition 1 with smaller number of cells.

Flat walls. Let G be a graph and let W be a wall a of G. We say that W is a flat wall of G if there is a separation (X, Y ) of G and a choice (P, C) of pegs and corners for W such that

• V (W ) ⊆ Y, • P ⊆ X ∩ Y ⊆ V (D(W )), and
• if Ω is the cyclic ordering of the vertices X ∩ Y
as they appear in D(W ), then there exists an Ω-

rendition (Γ, σ, π) of G[Y ].
Given a flat wall W of a graph G as above, we call G[Y ] the compass of W in G, denoted by compass(W ).

We call X ∩ Y the frontier of W. We call the set ground(W ) := π(N (Γ)) ground set of W. We clarify that ground(W ) consists of vertices of the compass of W that are not necessarily vertices of W. We also call the graphs in flaps(W ) := {σ(c) | c ∈ C(Γ)} flaps of the wall W.

For each flap F ∈ flaps(W ) we define its base 5 as the set ∂F := V (F ) ∩ ground(W ). We also refer to the triple (Γ, σ, π) as a rendition of the compass of W in G. We always assume that this rendition is a tight one. Based on this assumption and by using Menger's theorem, it is easy to prove the following.

Observation 2. Let W be a flat wall of a graph G and let K be the compass of W. For every flap F of W , there exists |∂F | pairwise vertex-disjoint paths in K from ∂F to the frontier of W. Moreover, any two vertices in ∂F are connected by a path in F.

Let G be a graph. We say that a pair (A, W ) is an (a, r)-apex-wall pair of G if A ⊆ V (G), |A| ≤ a and W is a flat r-wall of G \ A. We are now ready to state the Flat Wall Theorem, first proved By Robertson and Seymour [START_REF] Robertson | Graph Minors. XIII. The Disjoint Paths Problem[END_REF] and then reproved by Kawarabayashi et al. [START_REF] Kawarabayashi | A new proof of the flat wall theorem[END_REF] and Chuzhoy [START_REF] Chuzhoy | Improved bounds for the flat wall theorem[END_REF]. The version we state here is by Chuzhoy [START_REF] Chuzhoy | Improved bounds for the flat wall theorem[END_REF]. Theorem 4.2. There is a constant c 1 ∈ N such that, for every odd r ≥ 3 and every q ∈ N, every graph G that

• is K q -minor-free and

• contains a z-wall where z = c 1 • (q • (r + q)), contains a (q -5, r)-apex-wall pair (A, W ).

Affecting flat walls

We proceed to define a graph parameter and then prove that it is bidimensional and separable.

Let G be a graph, (A, W ) be an (a, r)-apex-wall pair of G, and S ⊆ V (G). We say that S affects

(A, W ) if N G [V (compass(W ))] ∩ (S \ A) = ∅. For a, r ∈ N, we define p a,r (G) = min{k | ∃S ⊆ V (G) : |S| ≤ k ∧ S affects every (a, r)-apex-wall pair (A, W ) of G}.
Using Theorem 4.1 and Theorem 4.2, we prove that the above parameter grows quadratically with the height of a largest wall, or equivalently, by Theorem 4.1, with its treewidth. Lemma 4.1. ( ) There is a function f 3 : N 2 → N such that if q, r ∈ N >0 , and G is a K q -minor-free graph, then tw(G) ≤ f 3 (q, r) • max 1, p q-5,r (G) . In particular, one may choose f 3 (q, r) = r • 2 O(q 2 log q) . We now prove that the parameter p a,r is separable, that is, that when considering a separation of a graph, the value of the parameter is "evenly" split along both sides of the separation, possibly with an offset bounded by the order of the separation. Lemma 4.2. Let a, r ∈ N, let G be a graph, and let S ⊆ V (G) such that S affects every (a, r)-apex-wall pair of G. Then, for every separation (L, R) of S in G, the set L∩(R∪S) affects every (a, r)-apex-wall pair of G[L].

Proof. Suppose for contradiction that (A, W ) is an (a, r)-apex-wall pair of G[L] that is not affected by L ∩ (R ∪ S). In particular, it holds that V (compass(W )) ⊆ L \ R. Since by assumption (A, W ) is affected by S but not by L ∩ (R ∪ S), there should exist a vertex v ∈ S ∩ (R \ L) with a neighbor in V (compass(W )) ⊆ L \ R, contracting the hypothesis that (L, R) is a separation of G.

Homogeneous subwalls

Before defining homogeneous subwalls, we need to define partially diskembedded graphs and introduce the concept of a leveling of a flat wall. This concept can be seen as a way to capture the "plane structure" of a flat wall in terms of a graph embeddable in a disk and might be useful in further applications of the Flat Wall Theorem.

Partially disk-embedded graphs.

A closed disk (resp. open disk) ∆ is a set homeomorphic to the set {(x, y) ∈ R 2 | x 2 + y 2 ≤ 1} (resp. {(x, y) ∈ R 2 | x 2 + y 2 < 1}). A disk of ∆ is a closed or an open disk that is a subset of ∆. We say that a graph G is partially disk-embedded in some closed disk ∆, if there is some subgraph K of G that is embedded in ∆ such that (V (G) ∩ ∆, V (G) \ int(∆)) is a separation of G,
where int is used to denote the interior of a subset of the plane. From now on, we use the term partially ∆embedded graph G to denote that a graph G is partially disk-embedded in some closed disk ∆. We also call the graph K = G ∩ ∆ compass of the ∆-embedded graph G and we always assume that G is accompanied by an embedding of its compass in ∆, that is the set G∩∆. We say that G is a ∆-embedded graph if it is partially ∆embedded graph and G ⊆ ∆ (the whole G is embedded in ∆).

Levelings. Let W be a flat wall of a graph G. We define the leveling of W in G, denoted by W , as the bipartite graph where one part is the ground set of W, the other part is the set of flaps of W, and, given a pair (v, F ) ∈ ground(W ) × flaps(W ), the set {v, F } is an edge of W if and only if v ∈ ∂F. Again, keep in mind that W may contain (many) vertices that are not in W. Notice that the incidence graph of the plane hypergraph (N (Γ), {c ∩ N | c ∈ C(Γ)}) is isomorphic to W via an isomorphism that extends π and, moreover, bijectively corresponds cells to flaps. This permits us to treat W as a ∆-embedded graph where bd(∆) ∩ W is the frontier of W. We call the vertices of ground(W ) (resp. flaps(W )) ground-vertices (resp. flap-vertices) of W .

Recall that each edge of compass(W ) belongs to exactly one flap of W. If both of the endpoints of this edge are in the boundary of this flap, then we say that this edge is a short edge of compass(W ). We define the graph W • as the graph obtained from W if we subdivide once every short edge in W.

The next observation, which is used in the proof of Theorem 5.2, is a consequence of the following three facts: flap-vertices of W have degree at most three, all the vertices of a wall have degree at most three, and every separation (A, B) of order at most three of a wall is trivial. Observation 3. If W is a flat wall of a graph G, then the leveling W of W in G contains a subgraph W that is isomorphic to some subdivision of W • via an isomorphism that maps each ground vertex to itself.

We call the graph W as in Observation 3 representation of the flat wall W in W and we see it as a ∆-embedded subgraph of W . Notice that the above observation permits to bijectively map each cycle of W to a cycle of W that is also a cycle of W . That way, each cycle C of W corresponds to a cycle C of W denoted by C and we call C as the representation of C in W . From now on, we reserve the " "-notation to denote the correspondence between W (resp. C) and W (resp. C ). We define the function flaps : C(W ) → 2 flaps(W ) so that, for each cycle C of W, flaps(C) contains each flap F of W that, when seen as a flap-vertex of the ∆-embedded graph W , belongs to the closed disk bounded by C .

Homogeneous subwalls. Let G be a graph and W be a flat wall of G. Let also (Γ, σ, π) be a rendition of the compass of W in G. Recall that Γ = (U, N ) is a ∆-painting for some closed disk ∆. Given a flap F, we denote by Ω(F ) the counter-clockwise ordering of the vertices of ∂F as they appear in the corresponding cell of C(Γ). Notice that as |∂F | ≤ 3, this cyclic ordering is significant only when |∂F | = 3, in the sense that (x 1 , x 2 , x 3 ) remains invariant under shifting, i.e.,

(v 1 , v 2 , v 3 ) ≡ (v 2 , v 3 , v 1 ) but not under inversion, i.e., (v 1 , v 2 , v 3 ) ≡ (v 3 , v 2 , v 1 ).
Let G be a graph and let (A, W ) be an (a, r)-apexwall pair of G. For each cell F ∈ flaps(W

) with t F = |∂F |, we fix ρ F : ∂F → [a + 1, a + t F ] such that (ρ -1 F (a + 1), . . . , ρ -1 F (a + t F )) ≡ Ω(c).
We also fix a bijection ρ A : A → [a]. For each flap F ∈ flaps(W ) we define the boundaried graph F A := (G[A∪F ], A∪∂F, ρ A ∪ρ F ) and we denote by F A the underlying graph of

F A . Notice that G[V (compass(W )) ∪ A] = F ∈flaps(W) F A .
Given some ∈ N, we say that two flaps

F 1 , F 2 ∈ flaps(W ) are (A, )-equivalent, denoted by F 1 ∼ A, F 2 , if -folio(F A 1 ) = -folio(F A 2 )
. For each F ∈ flaps(W ), we define the ( , a)-color of F, denoted by ( , a)-color(F ), as the equivalence class of ∼ A, to which F A belongs.

Let W be the leveling of W in G \ A and let W be the representation of W in W . Recall that W is a ∆-embedded graph. For each cycle C of W , we define the ( , a)-palette of C, denoted by ( , a)-palette(C), as the set of al the ( , a)-colors of the flaps that appear as vertices of W in the closed disk bounded by C in ∆ (recall that by C we denote the representation of C in W ). Let W be a subwall of W. We say that W is an ( , a)-homogeneous subwall of W if every brick B of W has the same ( , a)-palette (seen as a cycle of W ).

We would like to stress that, according to our definition, we do not consider a homogeneous subwall of a flat wall as a flat subwall itself. This permits us to avoid to define, in particular, the pegs and the rendition that would be associated with that flat subwall.

In the next lemma we prove that a sufficiently large flat wall contains a large enough homogeneous subwall. .

Finding an irrelevant vertex

In this section we show how to find an irrelevant vertex inside a sufficiently large (in terms of the collection F) flat wall of a boundaried graph that is not affected by its boundary. We start by defining in Subsection 5.1 railed annuli, a structure introduced in [START_REF] Kaminski | Contraction checking in graphs on surfaces[END_REF], and reused later in [START_REF] Golovach | The parameterized complexity of graph cyclability[END_REF][START_REF] Golovach | Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable[END_REF], which occurs as a subgraph inside a flat wall and that turns out to be quite handy to guarantee a "confinement" property of topological minor models (cf. Proposition 5.2). In Subsection 5.2 we first use graph drawing tools to prove that we can assume that our model is embedded "nicely" inside a railed annulus, in the sense that certain vertices are sufficiently pairwise far apart (cf. Lemma 5.1), which will be helpful in order to reroute the model. We then prove (cf. Theorem 5.1) that the model can be rerouted -possibly, by obtaining another topological minor model that can be contracted to a dissolution of the original model-so that, in particular, a large enough central region of the railed annulus is avoided by the model, and such that a prescribed subset of degree-3 vertices of the original model cannot be affected by contractions in order to obtain the desired model. Once we have all these ingredients, we finally show in Subsection 5.3 how the desired irrelevant vertex can be found inside a large enough flat wall that is not affected by the boundary (cf. Theorem 5.2). In order to prove this result, the notion of homogeneous subwall is crucial. We also need, in particular, to define an appropriate "flat" representation of a topological minor model, called its leveling, which we equip with colors encoding the "critical" zones in which we will have to be very careful to do the rerouting.

5.1 A lemma for model taming Before stating Proposition 5.2, we need some definitions. Railed annuli. Let G be a partially ∆-embedded graph and let C = [C 1 , . . . , C r ], r ≥ 2, be a collection of vertex-disjoint cycles of the compass of G. We say that the sequence Let r ∈ N ≥3 and q ∈ N ≥3 with r odd. An (r, q)railed annulus of a ∆-partially-embedded graph G is a pair A = (C, P) where C = [C 1 , . . . , C r ] is a ∆nested collection of cycles of G and P = [P 1 , . . . , P q ] is a collection of pairwise vertex-disjoint paths in G, called rails, such that • for every j ∈ [q], P j ⊆ ann(C), and

C is a ∆-nested sequence of cycles of G if every C i is the boundary of an open disk D i of ∆ such that ∆ ⊇ D 1 ⊇ • • • ⊇ D r . From now on, each ∆-nested sequence C = [C 1 , . . . , C
• for every (i, j) ∈ [r] × [q], C i ∩ P j is a non-empty
path that we denote by P i,j .

See Figure 4 for an example of a (5, 8)-railed annulus. The following proposition states that large railed annuli can be found inside a modestly larger wall and will be used in the next section. The proof is easy and can be found, for instance, in, [START_REF] Kaminski | Contraction checking in graphs on surfaces[END_REF]).

Proposition 5.1. For every odd x ∈ N, if W is a ( 9 2 • x × 9 2 •
x )-wall, then there is a collection P of x paths in W such that if C is the collection of the first x layers of W, then (C, P) is an (x, x)-railed annulus of W where the first cycle of C is the perimeter of W.

Moreover, the open disk defined by the x-th cycle of C contains the central vertices of W. We define the annulus of A = (C, P) as the annulus of C. We call C 1 and C r the outer and the inner cycle of A, respectively. Also, if

(i, i ) ∈ [r] 2 with i < i then we define A i,i = ([C i , • • • , C i ], P ∩ ann(C, i, i )).
The union-graph of an (r, q)-railed annulus A = (C, P) is defined as

G(A) := ( i∈[r] C i ) ∪ ( i∈[q] P i ).
Clearly, G(A) is a planar graph and we always assume that its infinite face is the one whose boundary is the fist cycle of C.

Let A be a (r, q)-railed annulus of a partially ∆embedded graph G. Let r = 2t + 1, for some t ≥ 0. Let also s ∈ [r] where s = 2t + 1, for some 0 ≤ t ≤ t. Given some I ⊆ [q], we say that a subgraph

M of G is (s, I)-confined in A if M ∩ ann(C, t + 1 -t , t + 1 + t ) ⊆ i∈I P i .
The following proposition has been recently proved by Golovach et al. [START_REF] Golovach | Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable[END_REF]Theorem 3]. Proposition 5.2. There exist two functions f 5 , f 6 :

Z ≥0 → Z ≥0 such that if • s is a positive odd integer,
• H is a graph on g edges,

• G is a ∆-partially-embedded graph,

• A = (C, P) is an (r, q)-railed annulus of G, where r ≥ f 6 (g) + 2 + s and q ≥ 5/2 • f 5 (g),

• (M, T ) is a topological minor model of H in G such that T ∩ ann(A) = ∅, and Moreover f 6 (g) = O((f 5 (g)) 2 ).

• I ⊆ [q] where |I| > f 5 (g),

Model rerouting in disk-embedded graphs

Using classic results on how to optimally draw planar graphs of maximum degree three into grids (see e.g., [START_REF] Kant | Algorithms for Drawing Planar Graphs[END_REF]) one may easily derive the following.

Proposition 5.3. There is a function f 7 : N → N such that for every -vertex planar graph H with maximum degree three there is a tm-pair (M, T ) of the (f 7 ( ) × f 7 ( ))-grid, denoted by Γ, that is a topological minor model of H in Γ. Moreover, it holds that f 7 ( ) = O( ).

Let Γ be an (r × r)-grid for some r ≥ 3. We see a Γ-grid as the union of r horizontal paths and r vertical paths. Given an i ∈ r 2 , we define the i-th layer of Γ recursively as follows: the first layer of Γ is its perimeter, while, if i ≥ 2, the i-th layer of Γ is the perimeter of the (r -2(i-1)×r -2(i-1))-grid created if we remove from Γ its i -1 first layers. When we deal with a (r × r)-grid Γ, we always consider its embedding where the infinite face is bounded by the first layer of Γ.

Safely arranged models. Let G be a plane graph. Given two vertices x and y of G, we define their facedistance in G as the smallest integer i such that there exists an arc of the plane (i.e., a subset homeomorphic to the interval [0, 1]) between x and y that does not cross the infinite face of the embedding, crosses no vertices of G, and crosses at most i edges of G. Given two subgraphs of W , we define their face-distance as the minimum face-distance between two of their vertices. We denote by F Given a graph H a set Q ⊆ V (H) and a graph G, we say that φ :

V (G) → 2 V (H) is a Q-respecting contraction-mapping of H to G if • x∈V (H) φ(x) = V (G), • ∀x, y ∈ V (H), if x = y then φ(x) ∩ φ(y) = ∅, • ∀x ∈ V (H), G[φ(x)] is connected,
• ∀{x, y} ∈ E(H), G[φ(x) ∪ φ(y)] is connected, and

• ∀x ∈ Q, |φ(x)| = 1.
The critical point in the above definitions is that vertices in Q are not "uncontracted" when transforming H to G. Given a non-negative integer x, we denote by odd(x) the minimum odd number that is not smaller than x.

Intrusion of a topological minor model. Let G be graph, let S ⊆ V (G), and let (M, T ) be a tppair of G. We define the S-intrusion of (M, T ) in G as the maximum value between |S ∩ T | and the number of subdivision paths of (M, T ) that contain vertices of S. Notice that S can intersect many times a subdivision path of (M, T ), however the value of the S-intrusion counts each such path only once.

Using Proposition 5.1, Proposition 5.2, and Lemma 5.1 we prove the following. Moreover, it holds that f 9 (c, ) = O(c • (f 5 ( 2 )) 2 ).

See Figure 5 for an illustration of the conditions guaranteed by Theorem 5.1. (l, l)-railed annulus of W where the outer cycle of C is the perimeter of W and such that the two central vertices of W belong to the interior of D l .

Proof. Let g = 2 , r = f 5 (g) + 1, s = odd(f 8 (c, r, 3 + r)), x = odd(max{f 6 ( ) + 2 + s, 5/2 • f 5 (h) }), l = ( + 1) • x,
Let M the union of all subdivision paths of (M, T ) that intersect ∆ ∩ V (G) and let T be the endpoints of these paths. Moreover, we denote H = diss( M , T ) and observe that H is a subgraph of H. Intuitively, H is the subgraph of H whose topological minor model ( M , T ) is the part of (M, T ) intersects the disk ∆. As the ∆ ∩ V (G)-intrusion of (M, T ) in G is at most , the same bound applies to the ∆∩V (G)-intrusion of ( M , T ) in G. This in turn implies that | T ∩ ∆| ≤ and that |E( H)| ≤ .

Since, l = ( + 1) • x, there is a b ≤ • x + 1 ≤ l such that A := ann(C b,b+x-1 )) does not contain any vertex of T. We define T out = T \ D b and T in = T ∩ D b+x-1 . Clearly, {T out , T in } is a partition of T .

We set A = (C b,b+x-1 , P ∩ A). By applying Propo-sition 5.2 on s, H, g, the ∆-boundaried graph G, the (x, x)-railed annulus A , the tm-pair ( M , T ), and the set I = [r], we have that G contains a topological minor model ( M , T ) of H in G such that M is (s, I)-confined in A and M \ ann(A ) ⊆ M \ ann(A ). We enhance M by adding to it all subdivision paths of (M, T ) that are not intersecting ∆. That way, we have that ( M , T ) is a topological minor model of H in G such that M is (s, I)-confined in A and M \ ann(A ) ⊆ M \ ann(A ).

Let p = b + x-s 2 and q = b + x+s 2 -1 and notice that q ≤ l. We set A := ann(C p,q ) and we define A := (C p,q , P ) where P = P ∩ A . Let P = {P 1 , . . . , P r }. Observe that, from the second property of Proposition 5.2, the connected components of M ∩ A are some of the paths in P . This means that there is a subset of indices {i 1 , . . . , i r } ⊆ I such that

M ∩ A = P i 1 ∪ • • • ∪ P i r . Let Z = {z i 1 , . . . , z i r } be the set of endpoints of the paths P i 1 , . . . , P i r that are contained in C p . Let M in = M ∩ D p , M out = (G \ D p ) \ E(C p ), and observe that M = M in ∪ M out and that Z = V ( M in ) ∩ V ( M out ).
Moreover, all vertices of Z have degree one in both M in and M out . Let Hin (resp. Hout ) be the graph obtained from M in (resp.

M out ) by dissolving all vertices in T in (resp. T out ) except from those in Z . Also ( M in , T in ∪Z) (resp. ( M out , T out ∪Z)) is a topological minor model of Hin (resp. Hout ).

Notice that Hin has vertex set T in ∪ Z and can be seen as a D-embedded graph on at most 3 + r edges where bd(D) ∩ H = Z and (z i 1 , . . . , z i r ) is the ordering of the vertices of Z as they appear in C p . Observe now that Hin can be seen as the contraction of another Dembedded graph Ĥin on at most 3 + r vertices that has maximum degree at most three. Moreover, we can assume that the vertices of Hin that have degree at most three are also vertices of Ĥin that are not affected by the contractions while transforming Ĥout to Hout . This implies that there is a Q-respecting contractionmapping of Hout to Ĥout . Again, in the embedding of Ĥin in D, (z i 1 . . . , z i r ) is the ordering of the vertices of Z as they appear in bd(D).

Keep in mind that H+ = Hout ∪ Hin is a minor of Ĥ+ := Hout ∪ Ĥin and that if we dissolve in H+ all the vertices in Z we obtain H. Also let Ĥ be the graph obtained if we dissolve in Ĥ+ all the vertices in Z. Clearly Ĥ is a minor of H.

We now apply Lemma 5.1 for c, r, r , , the Dembedded graph Ĥin , the set Z, and the (s, s)-railed annulus A of the D p -disk embedded graph G ∩ D p and obtain a tm-pair ( M in , T in ) of G(A ) that is a topological minor model of Ĥin and such that for each j ∈ [r], the function σ M in , T in maps vertex z i j to itself. Notice that G(A ) is a subgraph of W ∩ann(C p,q ). From the second property of Lemma 5.1, ( M in , T in ) is safely c-dispersed in W ∩ ann(C p,q ). From the third property of Lemma 5.1, it follows that none of the vertices of T in \ {w i 1 , . . . , w i r } is within face-distance less than c from some vertex in C p ∪ C q in W ∩ ann(C p,q ).

We now consider the graph M = M in ∪ M out . Properties Observe that ( M , T in ∪ T out ∪ Z) is a topological minor model of Ĥ+ , which in turn implies that ( M , T in ∪ T out ) is a topological minor model of Ĥ. We now set T = T in ∪ T out . As there is a Q-respecting contractionmapping of Hout to Ĥout , we also have that there is a Q-respecting contraction-mapping of H = diss(M, T ) to Ĥ = diss( M , T ) and Property 5 holds. As T in ⊆ int(ann(A )) ⊆ D p = D b+f 10 ( )-1 and T out ⊆ G \ D b , we deduce that T ∈ G \ ann(C b,b+f 10 ( )-1 ), which yields Property 2.

Rerouting minors of small intrusion

Let W be an r-wall and c ≥ 0. We call a cycle C of W c-internal if it is within face-distance at least c from the perimeter of W. Given a 0-internal cycle C of W , we define its internal pegs (resp. external pegs) as its vertices that are incident to edges of W that belong to the interior (resp. exterior) of C (we see edges as open sets). Notice that each vertex of C is either an internal or an external peg. Given two subgraphs H 1 and H 2 of a graph H we define the distance in H between H 1 and H 2 as the minimum distance between a vertex in H 1 and a vertex in H 2 .

Given a 1-internal brick B of W , one can see the union of all bricks of W that have a common vertex with B, as a subdivision of the graph in Figure 6. We call this subgraph X of W the brick-neighborhood of B. The perimeter P of a brick-neighborhood is defined in the obvious way. The next lemma is based on Observation 2. Vertices irrelevant to minors. Let G be a graph, H be a minor of G, and S ⊆ V (G). We define the Sminor-intrusion of H in G as the minimum S-intrusion in G over all tm-pairs (T, M ) of G such that (T, M ) is a topological minor model of G and diss(T, M ) ∈ ext(H).

Let Z = (Z, B, ρ) be a t-boundaried graph and ∈ N. We say that a vertex v ∈ V (Z) \ B is anirrelevant vertex of Z if for every boundaried graph C = (C, B, ρ) that is compatible with Z, every minor of C ⊕ Z with (V (Z) \ B)-minor-intrusion in G at most , is also a minor of C ⊕ (Z \ v, B, ρ). Informally, such an irrelevant vertex can be removed without affecting the occurrences of any minor of small minor-intrusion, where the intrusion is defined without taking into account the branching vertices in the boundary. Using Theorem 5.1 we can finally prove the main result of this section. does not contain any 2h-irrelevant vertex. To see this, recall that in (3.2) the equivalence is defined in terms of graphs H on at most h vertices and at most h edges, and that every topological minorminimal in ext(H) has at most 2h vertices and at most 2h edges. Thus, from Theorem 5.2, B should affect every (a, f 11 (a, 2h))-apex-wall pair of G, for every value of a. We conclude the following. Deletion (when F is connected and contains a planar graph) also works for F-TM-Deletion if we additionally require F to contain a subcubic planar graph (in order to bound the treewidth of the representatives). The main obstacle for applying our approach in order to achieve a time O * (2 O(tw•log tw) ) for every connected collection F, is that topological-minor-free graphs do not enjoy the flat wall structure that is omnipresent in our proofs. Another reason is that in our rerouting procedure, in order to find an irrelevant vertex (Theorem 5.1), we may find a different topological minor model that corresponds to the same minor. Nevertheless, we think that this latter difficulty can be overcome for planar graphs -or even minor-free graphs-by making use of the rerouting potential of Proposition 5.2, as this is done in [START_REF] Golovach | Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable[END_REF] for planar graphs.

Figure 1 :

 1 Figure 1: The chair and the banner.

  and there is no edge in G between L \ R and R \ L. The order of a separation (L, R) is the value |L∩R|. Given a graph G and a set S ⊆ V (G), be denote by ∂(S) the set of vertices in S that have a neighbor in V (G)\S. For S ⊆ V (G), we use the shortcut G\S to denote G[V (G) \ S]. The contraction of an edge e = {u, v} of a simple graph G results in a simple graph G obtained from G \ {u, v} by adding a new vertex uv adjacent to all the vertices in the set N G (u) ∪ N G (v) \ {u, v}, where N G (u) denotes the set of neighbors of u in G. A graph G is a minor of a graph G if G can be obtained from G by a sequence of vertex removals, edge removals, and edge contractions. If only edge contractions are allowed, we say that G is a contraction of G.

Figure 3 :

 3 Figure 3: An 11-wall and its five layers.

  for distinct c, c ∈ C(Γ), σ(c) and σ(c ) are edge-disjoint,(3) for every cell c ∈ C(Γ), π(c ∩ N ) ⊆ V (σ(c)), (4) for every cell c ∈ C(Γ), V (σ(c)) ∩ c ∈C(Γ)\{c} V (σ(c )) ⊆ π(c ∩ N ), and (5) π(N (Γ)∩bd(∆)) = V (Ω), such that the points in N (Γ) ∩ bd(∆) appear in bd(∆) in the same ordering as their images, via π, in Ω.

Lemma 4 .

 4 3. ( ) There is a function f 4 : N 3 → N such that if , r, a ∈ N, where r is an odd number, G is a graph, and (A, W ) is an (a, f 4 ( , r, a))-apex-wall pair of G, then W has an ( , a)-homogeneous subwall of height r. Moreover, it holds that f 4 ( , r, a) = r 2 2 O((a+ )•log(a+ ))

  r ] will be accompanied with the sequence [D 1 , . . . , D r ] of the corresponding open disks as well as the sequence [D 1 , . . . , D r ] of their closures. Given x, y ∈ [r] with x ≤ y, we call the set D x \ D y (x, y)-annulus of C and we denote it by ann(C, x, y). Finally we say that ann(C, 1, r) is the annulus of C and we denote it by ann(C).

5 Figure 4 :

 54 Figure 4: An example of a (5, 8)-railed annulus and its inner disk D 5 .

  then G contains an topological minor model ( M , T ) of H in G such that 1. T = T, 2. M is (s, I)-confined in A, and 3. M \ ann(A) ⊆ M \ ann(A).

G

  (x) the set of all vertices of G that are within face-distance at most i from vertex x.Given a c ≥ 0 and a tm-pair (M, T ) of G, we say that (M, T ) is safely c-dispersed in G if• every two distinct vertices t, t ∈ T are within facedistance at least 2c + 1 in G, and• for every t ∈ T of degree d in M , the graph M [F c G (t) ∩ V (M )]consists of d paths with t as a unique common endpoint. With Proposition 5.3 at hand, we can prove the following useful lemma. Lemma 5.1. ( ) There is a (polynomial) function f 8 : N 3 → N such that the following holds. Let c, r, r , ∈ N, r ≤ r, H be a D-embedded ( + r )-vertex graph, and Z := {z 1 , . . . , z r } ⊆ V (H) such that • the vertices of H have degree at most three, • Z is an independent set of H, • all vertices of Z have degree one in H, • bd(D) ∩ H = Z, and • (z 1 , . . . , z r ) is the cyclic ordering of the vertices of Z as they appear in the boundary of D. Let also G be a ∆-embedded graph, A = (C, P) be a (f 8 (c, r, ), f 8 (c, r, ))-railed annulus of G, where C = [C 1 , . . . , C f 8 (c,r, ) ], w i be the endpoint of P i that is contained in C 1 , for i ∈ [r], and I := {i 1 , . . . , i r } ⊆ [r]. Then the union-graph Γ:= G(A) of A contains a tmpair (M, T ) that is a topological minor model of H in Γ such that • for each j ∈ [r ], σ M,T (z j ) = w i j , • the tm-pair (M, T ) is safely c-dispersed in Γ,and • none of the vertices of T \ {w i 1 , . . . , w i r } is within face-distance less than c from some vertex in C 1 or in C r . Moreover, it holds that f 8 (c, r, ) = O(cr( + r)). Let G be a partially ∆-embedded graph and let C = [C 1 , . . . , C r ] be a ∆-nested sequence of cycles of G and let [D 1 , . . . , D r ] (resp. [D 1 , . . . , D r ]) be the sequences of the corresponding open (resp. closed) disks. Let also (M, T ) be a tm-pair of G and p ∈ [r]. We define the p-crop of (M, T ) in C, denoted by (M, T ) D p , as the tm-pair (M , T ) where M = M ∩ D p and T = (T ∩ D p ) ∪ (V (C p ∩ M )).

Theorem 5 . 1 .

 51 There are functions f 9 : N 2 → N and f 10 : N → N such that the following holds. Let c, ∈ N and let G be a partially ∆-embedded graph, whose compass contains a9 2 • f 9 (c, ) -wall W with bd(∆) as perimeter. Let also C 1 , . . . , C f 9 (c, ) be the firstf 9 (c, )layers of W and D 1 , . . . , D f 9 (c, ) be the open disks of ∆ that they define. If (M, T ) is a tm-pair of G whose ∆ ∩ V (G)-intrusion in G is at most and Q is a subset of T containingvertices of degree at most three in M, then there is a tm-pair ( M , T ) of G and an integer b ∈ [f 9 (c, )] such that 1. M \ D b is a subgraph of M \ D b , 2. ann(C b,b+f 10 (c, )-1 ) ∩ T = ∅, 3. ( M , T ) D b+f 10 (c, ) is a tm-pair of W that is safely c-dispersed in W and none of the vertices of T ∩ D b+f 10 (c, ) is within face-distance less than c from some vertex of C b+f 10 (c, ) ∪ C f 9 (c, ) in W. 4. M ∩ int(D f 9 (c, ) ) = ∅, 5. there is a Q-respecting contraction-mapping of diss(M, T ) to diss( M , T ), and 6. M does not intersect the two centers of W.

  and y = 9 2 l . We will prove the theorem for f 9 ( ) = l and f 10 ( ) = x-s 2 . Let G be a partially ∆-embedded graph, whose compass contains a y-wall W with bd(∆) as perimeter. Let also C = [C 1 , . . . , C l ] be the first l layers of W and let [D 1 , . . . , D r ] (resp. [D 1 , . . . , D r ]) be the sequences of the corresponding open (resp. closed) disks of ∆ bounded by the cycles in C. From Proposition 5.1 there is a collection P = {P 1 , . . . , P x } of paths in W such that A = (C, P) is an

Figure 5 :

 5 Figure 5: A visualization of how a tm-pair (M, T ) is rearranged to a new tm-pair ( M , T ) as in Theorem 5.1. The figure depicts in red the part of the tm-pair ( M , T ) that intersects the disk ∆. The cycles correspond to the first f 9 (c, ) layers of W. The black vertices are the vertices in Q, while the circled vertices inside the turquoise area are the "new" branch vertices of T that are vertices of W. The "green clouds" are the non-singleton images of the Q-respecting contractionmapping of diss(M, T ) to diss( M , T ).

3 and 6

 6 follow by the conclusions of the previous paragraph. Moreover, M does not intersect D q+1 and, as q ≤ l, it neither intersects D l+1 and Property 4 holds. Notice also that M \ ann(A ) ⊆ M \ ann(A ) implies M \ D b ⊆ M \ D b . This along with the fact that M \ D b = M \ D b , yield Property 1.

Figure 6 :

 6 Figure 6: The base graph for the definition of a brickneighborhood -the external pegs of the perimeter of X are the black round vertices.

Theorem 5 .

 5 2. ( ) There is a function f 11 : N 2 → N such that, for every a, ∈ N and every boundaried graph Z = (Z, B, ρ), if (A, W ) is an (a, f 11 (a, ))-apex-wall pair of Z that is not affected by B, then Z contains an -irrelevant vertex. Moreover, it holds that f 11 (a, ) =(f 5 ( 2 )) 2 2 O((a+ 2 )•log(a+ 2 )).By definition of the set R (t)h , its elements are of minimum size, and therefore a boundaried graph G = (G, B, ρ) ∈ R (t) h

Corollary 5 . 1 .

 51 If t, h, a ∈ N and G = (G, B, ρ) is a boundaried graph in R (t)h , then it holds that p a,f 11 (a,2h) (G) ≤ t.6 Bounding the size of the representativesIn this section we use the results obtained in the previous sections to prove that every representative in R (t) h has size linear in t. For this, we first prove in Subsection 6.1 that every representative in R (t) h has a set of at most 2t vertices containing its boundary whose 965 Copyright © 2020 by SIAM Published under the terms of the Creative Commons CC BY 4.0 license

The notation O * (•) suppresses polynomial factors depending on the size of the input graph.

The ETH states that

3-SAT on n variables cannot be solved in time 2 o(n) ; see[START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF] for more details.

In these papers[START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF][START_REF]A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth[END_REF], we also considered the version of the problem where the graphs in F are forbidden as topological minors; in the current paper will will focus exclusively on the minor version.

We use n and tw for the number of vertices and the treewidth of the input graph, respectively.

Downloaded 11/05/20 to 90.51.87.174. Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/page/terms

Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). ‡ Supported by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019.

removal leaves a graph with treewidth bounded by a constant depending only on the collection F; such a set is called a treewidth modulator.

Once we have the treewidth modulator, we can use known results from the protrusion machinery to achieve our goal. Namely, in Subsection 6.2 we show how to obtain a linear protrusion decomposition of a representative, and we reduce each of the linearly many protrusions in the decomposition to an equivalent protrusion of constant size. In the full version we give upper bounds on the constants depending on the collection F involved in our algorithm. These upper bounds depend explicitly on the parametric dependencies of the Unique Linkage Theorem [START_REF] Kawarabayashi | A shorter proof of the graph minor algorithm: the unique linkage theorem[END_REF][START_REF]XXII. Irrelevant vertices in linkage problems[END_REF].

6.1 Finding a treewidth modulator of linear size Given a graph G and a set S ⊆ V (G), we say that a separation

3 |S|. We need the following well-known property of graphs of bounded treewidth (see e.g. [START_REF] Bodlaender | A Partial k-Arboretum of Graphs with Bounded Treewidth[END_REF][START_REF] Cygan | Parameterized Algorithms[END_REF]). Lemma 6.1. Let G be a graph and let S ⊆ V (G). There is a 2/3-balanced separation (L, R) of S in G of order at most tw(G) + 1.

Using Lemma 4.1, Lemma 4.2, Corollary 5.1, and Lemma 6.1 we prove the following result, whose proof is an adaptation to our setting of the one of [START_REF]Bidimensionality and kernels[END_REF]Lemma 3.6] (see also [START_REF] Fomin | Bidimensionality and ker-969 Copyright[END_REF]). We stress that p is not a bidimensional parameter in the way this is defined in [START_REF] Demaine | Subexponential parameterized algorithms on graphs of bounded genus and Hminor-free graphs[END_REF][START_REF] Fomin | Bidimensionality[END_REF][START_REF] Fomin | Bidimensionality and ker-969 Copyright[END_REF][START_REF]Bidimensionality and kernels[END_REF], therefore Lemma 6.2 cannot be derived by directly applying the results of [START_REF]Bidimensionality and kernels[END_REF]. Lemma 6.2. ( ) There is a function

h , then G contains an f 12 (q, h)-treewidth modulator that contains B and has at most 2t vertices. Moreover, it holds that f 12 (q, h)

.

6.2 Finding a linear protrusion decomposition and reducing protrusions Equipped with Lemma 6.2, the next step is to construct an appropriate protrusion decomposition of a representative. We first need to define protrusions and protrusion decompositions of graphs and boundaried graphs.

the protrusions of P and the set R 0 the core of P.

The above notions can be naturally generalized to boundaried graphs, just by requiring that both boundaries -of the host graph and of the protrusion-behave as one should expect, namely that the intersection of the protrusion with the boundary of the considered graph is a subset of the boundary of the protrusion.

Protrusions and protrusion decompositions of boundaried graphs. Given a boundaried graph G = (G, B, ρ), a tree decomposition of G is any tree decomposition of G with a bag containing B. The treewidth of a boundaried graph G, denoted by tw(G), is the minimum width of a tree decomposition of G.

Given a boundaried graph G = (G, B, ρ) and α, t ∈ N, an (α, β)-protrusion decomposition of G is a sequence P = R 0 , R 1 , . . . , R of pairwise disjoint subsets of V (G) such that

the protrusions of P and the set R 0 core of P.

The following theorem is a reformulation using our notation of one of the main results of Kim et al. [START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF], which is stronger than what we need uin the sense that also applies to graphs excluding a topological minor. Theorem 6.1. Let c, β, t be positive integers, let H be an q-vertex graph, and let G be an n-vertex Htopological-minor-free graph. If we are given a set Having stated the above definitions, the following lemma is an easy consequence of Lemma 6.2 and Theorem 6.1.

Lemma 6.3. There is a function

.

Proof. By Lemma 6.2, G contains an f 12 (q, h)-treewidth modulator M that contains B and has at most 2t vertices. We can now apply Theorem 6.1 to G and M with H = K q , c = 2, and β = f 12 (q, h), obtaining a (f 13 (q, h) • t, f 13 (q, h))-protrusion decomposition P of G with M contained in the core of P and f 13 (q, h) := 2 • f 12 (q, h) • 40q 2 2 5q log q . Since B ⊆ M and M contained in the core of P, it can be easily seen that P is also a (f 13 (q, h) • t, f 13 (q, h))-protrusion decomposition of G.

Once we have the protrusion decomposition given by Lemma 6.3, all that remains is to replace the protrusions by equivalent ones of size depending only on the collection F. The protrusion replacement technique, which is nowadays part of the basic toolbox of parameterized complexity, originated in the meta-theorem of Bodlaender et al. [START_REF] Bodlaender | Meta) Kernelization[END_REF], whose objective was to produce linear kernels for a wide family of problems on graphs of bounded genus. This technique was later extended to graphs excluding a fixed minor by Fomin et al. [START_REF] Fomin | Bidimensionality and ker-969 Copyright[END_REF] and then to graphs excluding a fixed topological minor by Kim et al. [START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF]. We could directly apply the results of Fomin et al. [START_REF] Fomin | Bidimensionality and ker-969 Copyright[END_REF] to the protrusion decomposition of a representative given by Lemma 6.3, hence reducing each protrusion to an equivalent one of size O F (1), yielding an equivalent representative of size O F (t). However, the drawback of the results in [START_REF] Fomin | Bidimensionality and ker-969 Copyright[END_REF] (and also in [START_REF] Bodlaender | Meta) Kernelization[END_REF][START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF]) is that they do not provide explicit bounds on the hidden constants. In order to be able to do so, we apply the protrusion replacement used by Baste et al. [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF], which is suited for the F-M-Deletion problem. This yields explicit constants because it uses ideas similar to the ones presented by Garnero et al. [START_REF] Garnero | Explicit Linear Kernels via Dynamic Programming[END_REF] (later generalized in [START_REF]Explicit linear kernels for packing problems[END_REF]) for obtaining kernels with explicit constants.

Given a function ξ : N 2 → N and a t-boundaried graph G, we say that G is ξ-protrusion-bounded if, for every t ∈ N, all β-protrusions of G have at most ξ(β) vertices. The following lemma is again a reformulation using our notation of one of the results of Baste et al. [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF]. Namely, it is a consequence of the proof 6 of [4, Lemma 15]. 6 In the statement of [4, Lemma 15] it is required that the Lemma 6.4. There is a function

h , then G is f 14 (q, h)-protrusionbounded. Moreover, f 14 (q, h) = 2 2 2 O(f 13 (q,h))•log f 13 (q,h))

.

Using Lemma 6.3 and Lemma 6.4, we can easily prove Theorem 6.2, that is the main result on which the algorithm of Theorem 2.1 is based (cf. §2). In particular, it implies (2.1). Theorem 6.2. There is a function

Moreover, it holds that f 15 (q, h) ≤ f 13 (q, h)• (f 14 (q, h) + 1).

Proof. By Lemma 6.3, G admits a (f 13 (q, h) • t, f 13 (q, h))-protrusion decomposition P. By Lemma 6.4, each of the protrusions of P has at most f 14 (q, h) vertices. Therefore,

and the theorem follows with f 15 (q, h) := f 13 (q, h) • (f 14 (q, h) + 1).

The dynamic programming algorithm. Having proved Corollary 6.1, we can just reuse the dynamic programming algorithm given in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] to compute the parameter m F (G) in the claimed running time. For the sake of completeness, let us comment some details of this algorithm, whose details can be found in [4, proof of Theorem 3]. First of all, to run the algorithm we need to have the set R (t) h of representatives at hand. This can be done easily relying on Theorem 6.2, by generating all t-boundaried graphs on at most f 15 (h, h) • t family F contains a planar graph, an assumption that is not true anymore in our case. However, in the proof this fact is only used to guarantee that the considered protrusion has treewidth bounded by a function depending only on F . Thanks to Lemma 6.3, we can assume that this also holds in our setting. Lemma 14] for more details. To simplify the description of the dynamic programming update operations, the algorithm in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] in written in terms of branchwidth instead of treewidth. Without defining branchwidth here, it is enough to say that it is parametrically equivalent to treewidth, in the sense that both parameters differ by a constant factor and whose corresponding decompositions can be easily transformed from one to the other [START_REF] Robertson | Graph Minors. X. Obstructions to Tree decomposition[END_REF]. Also, the algorithm in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] is written in terms of topological minors, that is, it computes a minimum-size set of vertices S ⊆ V (G) whose removal leaves a graph without any of the graphs in a fixed collection F as a topological minor; we denote |S| =: tm F (G). It is easy to see that computing this parameter suffices for computing m F (G), since, as observed in [4, Lemma 4], for every proper collection F and every graph G, it holds that m F (G) = tm F (G), where F is the family containing every topological minor minimal graph among those that contain some graph in F as a minor; note that F has size bounded by a small function of F (see Observation 1).

The algorithm then computes, in a typical bottomup manner, at every bag separator B of the branch decomposition associated with a t-boundaried graph G B and for every representative R ∈ R Theorem 6.3. Let t, h ∈ N, F be a proper connected collection of size at most h, and G be an n-vertex graph of treewidth at most t. Then m F (G) can be computed by an algorithm that runs in 2 (2•f 16 (h)•t+1)•log t • n steps.

Further research

Our main algorithmic result is an algorithm solving F-M-Deletion in time O * (2 O(tw•log tw) ) for every connected collection F. One may wonder why the connectivity of F is necessary. In fact, in the whole algorithm (see Figure 2) the connectivity of the graphs in F is only used at the very end, when we apply the dynamic programming algorithm of [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] based on representatives. This algorithm uses the connectivity of F in the "base case", namely to guarantee that the representative of a graph G without boundary is the empty boundaried graph if and only if G does not contain any of the graphs in F as a minor (see [START_REF] Baste | Hitting minors on bounded treewidth graphs[END_REF]Lemma 7]). We think that this is a technical hurdle, rather than an intrinsic one, and we believe that the condition on the connectivity of F can be dropped, that is, that there exists an algorithm to solve F-M-Deletion in time O * (2 O(tw•log tw) ) for every collection F. As an evidence towards this, note that the minor obstructions for being embeddable on a surface of Euler genus at most g contain disconnected graphs if g ≥ 2 (for instance, the disjoint union of two K 5 's is an obstruction for being embeddable on the torus [START_REF] Mohar | Graphs on surfaces[END_REF]), and that Kociumaka and Pilipczuk [START_REF] Kociumaka | Deleting vertices to graphs of bounded genus[END_REF] presented an algorithm running in time O * (2 O((tw+g)•log(tw+g)) ) for deleting a minimum number of vertices to obtain a graph embeddable on a surface of Euler genus at most g.

We also presented a framework to obtain lower bounds for ruling out algorithms in time O * (2 o(tw•log tw) ) under the ETH. In particular, when F = {H} and H is connected, it settles completely the asymptotic complexity of {H}-M-Deletion (Theorem 1.1). However, we do not have a complete classification when |F| ≥ 2, even for connected F. To ease the presentation, let us call a connected graph H easy (resp. hard

with both H 1 and H 2 being connected. Using the recent results of Baste [START_REF] Baste | Composing dynamic programming tree-decomposition-based algorithms[END_REF], it is possible to prove that if both H 1 and H 2 are easy, then F is easy as well (easiness of graph collections is defined in the obvious way). However, if both H 1 and H 2 are hard, then strange things may happen. For instance, Bodlaender et al. [START_REF] Bodlaender | A faster parameterized algorithm for pseudoforest deletion[END_REF] presented an algorithm running in time O * (2 O(tw) ) for Pseudoforest Deletion, which consists in, given a graph G and an integer k, deciding whether one can delete at most k vertices from G to obtain a pseudoforest, i.e., a graph where each connected component contains at most one cycle. Note that Pseudoforest Deletion is equivalent to {diamond, butterfly}-M-Deletion. While both the diamond and the butterfly are hard graphs, {diamond, butterfly} is an easy collection. The cases where H 1 is easy and H 2 is hard seem even trickier. Obtaining (tight) lower bounds when F may contain disconnected graphs is a challenging avenue for further research.

It is also interesting to consider the version of the problem where the graphs in F are forbidden as topological minors; we call this problem F-TM-Deletion. While the lower bounds that we presented in this article also hold for F-TM-Deletion (with the exception of K 1,i for i ≥ 4; see [START_REF] Baste | Hitting minors on bounded treewidth graphs[END_REF]), the algorithm in time O * (2 O(tw•log tw) ) for every connected collection F does not work for topological minors. In this direction, the algorithm in time O * (2 O(tw•log tw) ) in [START_REF]Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth[END_REF] for F-M-