Marin Bougeret
email: marin.bougeret@lirmm.fr

Bart M P Jansen
email: b.m.p.jansen@tue.nl

Ignasi Sau
email: ignasi.sau@lirmm.fr

Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel

Keywords: 2012 ACM Subject Classification Theory of computation → Graph algorithms analysis; Theory vertex cover, parameterized complexity, polynomial kernel, structural parameterization, bridge-depth Digital Object Identifier 10.4230/LIPIcs.ICALP.2020.16 Category Track A: Algorithms, Complexity and Games

We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can reduce any instance (G, k) of the Vertex Cover problem to an equivalent one, whose size is polynomial in the size of a pre-determined complexity parameter of G. A long line of previous research deals with parameterizations based on the number of vertex deletions needed to reduce G to a member of a simple graph class F, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes F for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to F, admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families F for which such a kernelization exists. We introduce a new graph parameter called bridge-depth, and prove that a polynomial kernelization exists if and only if F has bounded bridge-depth. The proof is based on an interesting connection between bridge-depth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number.

Theorem 1.1 gives a clean and unified explanation for all the minor-closed families F that were previously considered individually [START_REF] Bougeret | How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs[END_REF][START_REF] Fedor | Vertex cover structural parameterization revisited[END_REF][START_REF] Eva-Maria | Smaller parameters for vertex cover kernelization[END_REF][START_REF] Bart | Vertex cover kernelization revisited -upper and lower bounds for a refined parameter[END_REF][START_REF] Majumdar | Polynomial kernels for vertex cover parameterized by small degree modulators[END_REF], and generalizes these results as far as possible. To the best of our knowledge, Theorem 1.1 captures all known (deterministic) kernelizations for structural parameterizations of Vertex Cover. (There are randomized kernelizations [START_REF] Eva-Maria | Elimination distances, blocking sets, and kernels for vertex cover[END_REF][START_REF] Kratsch | A randomized polynomial kernelization for vertex cover with a smaller parameter[END_REF][START_REF] Kratsch | Representative sets and irrelevant vertices: New tools for kernelization[END_REF] which apply for distance to classes F that are not minor-closed, such as bipartite graphs.) For example, we capture the case of F being a forest [START_REF] Bart | Vertex cover kernelization revisited -upper and lower bounds for a refined parameter[END_REF] since forests have bridge-depth one, and the case of F being graphs of constant tree-depth [START_REF] Bougeret | How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs[END_REF][START_REF] Bart | Polynomial kernels for hitting forbidden minors under structural parameterizations[END_REF] since bridge-depth does not exceed tree-depth. In this sense, bridge-depth can be seen as the ultimate common generalization of feedback vertex number and tree-depth (which are incomparable parameters) in the context of polynomial kernels for Vertex Cover.

We consider it one of our main contributions to identify the graph parameter bridge-depth as the right way to capture the kernelization complexity of Vertex Cover parameterizations.

Techniques. To describe our techniques, we introduce some terminology. Let α(G) denote the independence number of graph G, i.e., the maximum size of a set of pairwise nonadjacent vertices. A blocking set in a graph G is a vertex set Y ⊆ V (G) such that α(G \ Y ) < α(G). Hence if Y is a blocking set, then every maximum independent set in G contains a vertex from Y . Earlier kernelizations for Vertex Cover parameterized by distance to a graph class F, starting with the work of Jansen and Bodlaender [START_REF] Bart | Vertex cover kernelization revisited -upper and lower bounds for a refined parameter[END_REF], all rely, either implicitly or explicitly, on having upper-bounds on the size of (inclusion-)minimal blocking sets for graphs in F [START_REF] Bougeret | How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs[END_REF][START_REF] Fedor | Vertex cover structural parameterization revisited[END_REF][START_REF] Eva-Maria | Smaller parameters for vertex cover kernelization[END_REF][START_REF] Bart | Vertex cover kernelization revisited -upper and lower bounds for a refined parameter[END_REF][START_REF] Majumdar | Polynomial kernels for vertex cover parameterized by small degree modulators[END_REF]. For example, it is known that minimal blocking sets in a bipartite graph have size at most two [START_REF] Eva-Maria | Smaller parameters for vertex cover kernelization[END_REF]Cor. 11], while minimal blocking sets in graphs of tree-depth c have size at most 2 c [5, Lemma 1]. Similarly, all the existing superpolynomial kernelization lower bounds for parameterizations by distance to F, rely on F having minimal blocking sets of arbitrarily large size. Indeed, if F is closed under disjoint union and has arbitrarily large blocking sets, it is easy to prove a superpolynomial lower bound (cf. [START_REF] Eva-Maria | Elimination distances, blocking sets, and kernels for vertex cover[END_REF]Thm. 1]).

Since all positive cases for kernelization are when minimal blocking sets of graphs in F have bounded size, while one easily obtains lower bounds when the size of minimal blocking sets of graphs in F is unbounded, the question rises whether a bound on the size of minimal I C A L P 2 0 2 0 16:4

Bridge-Depth Characterizes Kernelization Complexity of Vertex Cover

blocking sets is a necessary and sufficient condition for the existence of polynomial kernels. To our initial surprise, we show that for minor-closed families F, this is indeed the case: the purely structural property of having bounded-size minimal blocking sets can always be leveraged into preprocessing algorithms.

For an insight into our techniques, consider an instance (G, k) of Vertex Cover, together with a vertex set X ⊆ V (G) such that G \ X ∈ F for some minor-closed family F that has bounded-size minimal blocking sets. The goal of the kernelization is then to reduce to an equivalent instance of size |X| O (1) in polynomial time. Using ideas of the previous kernelizations [START_REF] Bougeret | How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs[END_REF][START_REF] Bart | Vertex cover kernelization revisited -upper and lower bounds for a refined parameter[END_REF], it is quite simple to reduce the number of connected components of G \ X to size |X| O (1) . To obtain a polynomial kernel, the challenge is therefore to bound the size of each such component C of G \ X to |X| O (1) , so that the overall instance size becomes polynomial in |X|. However, the non-existence of large minimal blocking sets does not seem to offer any handle for reducing the size of individual components of G \ X. The route to the kernelization therefore goes via the detour of bridge-depth. We prove the following relation between the sizes of minimal blocking sets and bridge-depth. Theorem 1.2. Let F be a minor-closed family of graphs. Then F has bounded bridge-depth if and only if the size of minimal blocking sets of graphs in F is bounded.

Using this equivalence, we can exploit the fact that all minimal blocking sets of F are of bounded size, through the fact that the bridge-depth of G \ X ∈ F is small. This means that there is a bounded-depth elimination process to reduce G \ X to the empty graph. We use this bounded-depth process in a technical kernelization algorithm following a recursive scheme, inspired by the earlier kernelization for the parameterization by distance to bounded tree-depth [START_REF] Bougeret | How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs[END_REF].

Let us now discuss the ideas behind the equivalence of Theorem 1.2. We prove that the bridge-depth of graphs in a minor-closed family F is upper-bounded in terms of the maximum size of minimal blocking sets for graphs in F, by exploiting the Erdős-Pósa property in an interesting way. We analyze an elementary graph structure called necklace of length t, which is essentially the multigraph formed by a path of t double-edges. If a simple graph G ∈ F contains a necklace of length t as a minor, then there is a minor G of G (which therefore also belongs to F) that has a minimal blocking set of size Ω(t). Hence to show that bridge-depth is upper-bounded in terms of the size of minimal blocking sets of graphs in F, it suffices to show that bridge-depth is upper-bounded by the maximum length of a necklace minor of graphs in F. Since the definition of bridge-depth allows for the contraction of all bridges in a single step, it suffices to consider bridgeless graphs. Then we argue that in a bridgeless graph, any pair of maximum-length necklace minor models intersects at a vertex (cf. Lemma 4.6). By the Erdős-Pósa property, this implies that there is a constant-size vertex set that hits all maximum-length necklace minor models, and whose removal therefore strictly decreases the maximum length of a necklace minor. If the length of necklace minor models is bounded, then after a bounded number of steps of this process (interleaved with contracting all bridges) we reduce the maximum length of necklace minor models to zero, which is equivalent to breaking all cycles of the graph. At that point, the bridge-depth is one by definition, and we have obtained the desired upper-bound on the bridge-depth in terms of the length of the longest necklace minor, and therefore blocking set size.

For the other direction of Theorem 1.2, we prove (cf. Theorem 5.4) the tight bound that a minimal blocking set in a graph G has size at most 2 bd(G) . We use induction to prove this statement, together with an analysis of the structure of a tree of bridges whose removal decreases the bridge-depth. The fact that bipartite graphs have minimal blocking sets of size at most two, allows for an elegant induction step.

Related work.

In a recent paper, Hols, Kratsch, and Pieterse [START_REF] Eva-Maria | Elimination distances, blocking sets, and kernels for vertex cover[END_REF] also analyze the role of blocking sets in the existence of polynomial kernels for structural parameterizations of Vertex Cover. Note that our paper is independent from, and orthogonal to [START_REF] Eva-Maria | Elimination distances, blocking sets, and kernels for vertex cover[END_REF]: we consider the setting of deterministic kernelization algorithms for parameterizations to minorclosed families F, and obtain an exact characterization of which F allow for a polynomial kernelization. Hols et al. [START_REF] Eva-Maria | Elimination distances, blocking sets, and kernels for vertex cover[END_REF] consider hereditary families F and give kernelizations for several such parameterizations, without arriving at a complete characterization. Some of the randomized kernelizations they provide do not fit into our framework, but all the deterministic kernelizations they present are captured by Theorem 1.1. Another contribution of [START_REF] Eva-Maria | Elimination distances, blocking sets, and kernels for vertex cover[END_REF] is to prove that there is a class F with minimal blocking sets of size one where Vertex Cover cannot be solved in polynomial time. In particular, there is no polynomial kernel parameterized by the distance to this family F, and thus bounded minimal blocking set size is not sufficient to get a polynomial kernel. This implies that our minor-closed assumption of Theorem 1.1 cannot be dropped.

We refer to the survey by Fellows et al. [START_REF] Michael | What is known about vertex cover kernelization[END_REF] for an overview of classic results and new research lines concerning kernelization for Vertex Cover. Additional relevant work includes the work by Kratsch [START_REF] Kratsch | A randomized polynomial kernelization for vertex cover with a smaller parameter[END_REF] on a randomized polynomial kernel for a parameterization related to the difference between twice the cost of the linear-programming relaxation of Vertex Cover and the size of a maximum matching.

Organization. Preliminaries on graphs and complexity are presented in Section 2. Section 3 introduces bridge-depth and its properties. In Section 4 we prove one direction of Theorem 1.2, showing that large bridge-depth implies the existence of large minimal blocking sets. In Section 5 we handle the other direction, proving a tight upper-bound on the size of minimal blocking sets in terms of the bridge-depth. We discuss the kernelization algorithm exploiting bridge-depth in Section 6, with the technical content being available in the full version of the article [START_REF] Bougeret | Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel[END_REF] due to space limitations. We conclude the article in Section 7. The proofs of the results marked with "( )" have been also deferred to the full version [START_REF] Bougeret | Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel[END_REF].

Preliminaries

Graphs. We use standard graph-theoretic notation, and we refer the reader to Diestel [START_REF] Diestel | Graph Theory[END_REF] for any undefined terms. All graphs we consider are finite and undirected.

≤ j ≤ i. Given v ∈ V (G), we denote N G (v) = {u | {u, v} ∈ E(G)}, d G (v) = |N G (v)| and given X ⊆ V (G), we denote N G (X) = v∈X N G (v) \ X. Given X, Y ⊆ V (G), we denote by N Y G (X) = N G (X) ∩ Y .
We may omit the subscript G when it is clear from the context. For distinct vertices u and v of a graph G, the graph G obtained by identifying u and v is defined by removing vertices u and v from G, adding a new vertex uv with N G (uv) = N G ({u, v}), and keeping the other vertices and edges unchanged. Given two adjacent vertices u and v, we define the contraction of the edge {u, v} as the identification of u and v. I C A L P 2 0 2 0 16:6

Bridge-Depth Characterizes Kernelization Complexity of Vertex Cover

Given a graph G, we denote by α(G) the size of a maximum independent set in G, by #cc(G) the number of connected components of G, by diam(G) the diameter of G, and by ∆(G) the maximum degree of G. Given a graph G and a set S ⊆ V (G), we say that S is a blocking set in G if α(G \ S) < α(G). The maximum size of an inclusion-wise minimal blocking set of a graph G is denoted by mbs(G).

A graph H is a minor of graph G if H can be obtained from G by a sequence of edge deletions, edge contractions, and removals of isolated vertices. Let us also recall the definition of minor in the context of multigraphs. Let H be a loopless multigraph. An

H-model M in a simple graph G is a collection {S M x | x ∈ V (H)} of pairwise disjoint subsets of V (G) such that G[S M
x ] is connected for every x ∈ V (H), and such that for every pair of distinct vertices x, y of H, the quantity |{{u,

v} ∈ E(G) | u ∈ S M
x , v ∈ S M y }| is at least the number of edges in H between x and y. The vertex set V (M ) of M is the union of the vertex sets of the subgraphs in the collection. We say that a graph G contains a loopless multigraph H as a minor if G has an H-model.

For the following definitions, we refer the reader to [START_REF] Nesetril | Sparsity -Graphs, Structures, and Algorithms[END_REF] for more details and we only recall here some basic notations and facts. The tree-depth of a graph G, denoted by td(G), is defined recursively. The empty graph without vertices has tree-depth zero. The tree-depth of a disconnected graph is the maximum tree-depth of its connected components. Finally, if G is a nonempty connected graph then td(G) = 1 + min v∈V (G) td(G \ v). Equivalent definitions exist in terms of the minimum height of a rooted forest whose closure is a supergraph of G. The tree-width of G is denoted tw(G) (cf. [START_REF] Hans | A partial k-arboretum of graphs with bounded treewidth[END_REF]).

Given a graph family F, an F-modulator in a graph G is a subset of vertices X ⊆ V (G) such that G\X ∈ F. We denote by dist-to-F(G) the size of a smallest F-modulator in G. For a graph measure f that associates an integer with each graph, and an integer c, a c-f-modulator is a modulator to

F f c := {G | f(G) ≤ c}. We denote by c-f-mod(G) := dist-to-F f c (G)
, that is, the size of a smallest c-f-modulator of G. Typical measures f that we consider here are tree-width, tree-depth, and bridge-depth. Notice that 0-tw-mod(G) corresponds to the minimum size of a vertex cover of G, and 1-tw-mod(G) corresponds to the minimum size of a feedback vertex set of G. Finally, IS (resp. VC) denotes the Maximum Independent Set (resp. Minimum Vertex Cover) problem.

Parameterized complexity.

A parameterized problem is a language L ⊆ Σ * × N, for some finite alphabet Σ. For an instance (x, k) ∈ Σ * × N, the value k is called the parameter. For a computable function g : N → N, a kernelization algorithm (or simply a kernel) for a parameterized problem L of size g is an algorithm A that given any instance (x, k) of L, runs in polynomial time and returns an instance (x , k [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Fedor | Kernelization: Theory of Parameterized Preprocessing[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for background on parameterized complexity.

) such that (x, k) ∈ L ⇔ (x , k ) ∈ L with |x |, k ≤ g(k). Consult

An introduction to bridge-depth

Let G be a graph. An edge e ∈ E(G) is a bridge if its removal increases the number of connected components of G. We define G cb as the simple graph obtained from G by contracting all bridges of G (the order does not matter.) Observe that, as contracting an edge cannot create a new bridge, G cb has no bridges, implying that (G cb ) cb = G cb . Given a subgraph T of a graph G, we say that T is a tree of bridges if T is a tree and, for every e ∈ E(T ), e is a bridge in G. Note that a single vertex is, by definition, a tree of bridges. Note also that with any vertex v ∈ V (G cb ) we can associate, in a bijective way, an inclusion-wise maximal tree of bridges

T v of G. The set {T v | v ∈ V (G cb )} is a minor model of G cb in G (a G cb -model, from now on). For any u, v ∈ V (G cb ) such that {u, v} ∈ E(G cb ), there is exactly one edge {u , v } ∈ E(G) with u ∈ T u and v ∈ T v .
The latter claim can be easily verified by supposing that there are two such edges, implying that some edge in T u or T v is involved in a cycle, which contradicts the fact that all the edges in T u and T v are bridges.

Definition 3.1. The bridge-depth bd(G) of a graph G is recursively defined as follows:

If G is the empty graph without any vertices, then bd(G) = 0.

If G has > 1 connected components {G i | i ∈ [ ]}, then bd(G) = max i∈[ ] bd(G i ). If G is connected, then bd(G) = 1 + min v∈V (Gcb) bd(G cb \ v).
Informally, bd behaves like tree-depth except that at each step of the recursive definition we are allowed to delete trees of bridges instead of just single vertices, as proved in Item 4 of the following proposition. The following properties of bridge-depth follow from the definitions in an elementary way, often exploiting the fact that if e is a bridge in G, then e is also a bridge in any minor of G that still contains e. Proposition 3.2. For any graph G the following claims hold:

1. bd(G) = 1 if and only if G is a forest with at least one vertex. 2. bd(G cb ) = bd(G). 3. The parameter bd is minor-closed: if G is a minor of G then bd(G ) ≤ bd(G). 4. If G is connected, then bd(G) = 1 + min T bd(G \ V (T ))
, where the minimum is taken over all trees of bridges T of G.

For any

X ⊆ V (G), we have bd(G) ≤ |X| + bd(G \ X).

tw(G) ≤ bd(G).

Proof. The first item follows easily from the definition, while the second one uses that (G cb ) cb = G cb .

Proof of 3: We prove the claim by induction on |V

(G)| + |E(G)|. Suppose that G has multiple connected components {G i | i ∈ [#cc(G)]}, and let {G i | i ∈ [#cc(G )]} be the connected components of the minor G of G. Then each connected component G j is a minor of some component G i of G on fewer than |V (G)| vertices, which gives bd(G j ) ≤ bd(G i ) by induction. Hence we have bd(G ) = max j∈[#cc(G )] bd(G j ) ≤ max i∈[#cc(G)] bd(G i ) = bd(G).
We now deal with the case that G is connected. In general, if some graph G * is a minor of G, then G * is a minor of a graph G obtained from G by removing an edge, contracting an edge, or removing an isolated vertex. Since G is assumed to be connected, the third case cannot occur here. Then by induction, we have bd(G * ) ≤ bd(G ), so it suffices to prove that bd(G ) ≤ bd(G) for any graph G obtained by removing or contracting an edge. Let us first prove that if

G cb is a minor of G cb , then bd(G ) ≤ bd(G). Indeed, let v * ∈ V (G cb ) such that bd(G) = 1 + bd(G cb \ v * ),

and consider an arbitrary component

G i of G . Note that (G i ) cb is a component of (G ) cb ,
G i ) = bd((G i ) cb ) ≤ bd(G cb \ v * ) < bd(G). Otherwise, any minor model {S x | x ∈ V ((G i ) cb )} of (G i ) cb in G cb contains a branch set S x * with v * ∈ S x * . But then bd((G i ) cb ) ≤ 1 + bd((G i ) cb \ x * ) by definition, and (G i ) cb \ x * is a minor of G cb \ v * ,
and therefore has bridge-depth at most bd(G) -1, so that bd(

(G i ) cb ) ≤ bd(G). Hence for each component G i of G we have bd(G i ) = bd((G i ) cb ) ≤ bd(G), implying bd(G ) ≤ bd(G
T v = {e}, then G cb \ v is composed of two disjoint edges, whereas (G -V (T v )) cb is composed of two isolated vertices. However, it is easy to verify that (G \ V (T v )) cb = (G cb \ v) cb . Let us now prove that min T bd(G \ V (T )) ≤ min v∈V (Gcb) bd(G cb \ v). Let v * be a vertex minimizing bd(G cb \ v). We have min T bd(G \ V (T )) ≤ bd(G \ V (T v * )) = bd((G \ V (T v * ) cb ) using Item 2 in the last equality, and bd((G \ V (T v * ) cb ) = bd((G cb \ v * ) cb ) = bd(G cb \ v * ) using again Item 2.
For the other inequality, let T 0 be a tree of bridges that minimizes bd(G \ V (T )). If T 0 is not inclusion-wise maximal, let T * be any inclusion-wise maximal tree of bridges containing T 0 . Note that as

G \ V (T * ) is a subgraph of G \ V (T 0 ), by Item 3 we get that bd(G \ V (T * )) ≤ bd(G \ V (T 0 )), implying that T * also minimizes bd(G \ V (T )). Let v * ∈ V (G cb ) such that T v * = T * . We have min v∈V (Gcb) bd(G cb \ v) ≤ bd(G cb \ v * ) = bd((G \ T v * ) cb ) = bd(G \ T v * ).

Proof of 5:

We use induction on |X|, the base case X = ∅ being trivial. For the induction step, pick an arbitrary v ∈ X, let X := X \ {v}, and G := G \ X . By induction we have bd(G)

≤ |X | + bd(G ). Let G i be the connected component of G containing v.
Using v as a singleton tree of bridges in G i , Item 4 shows that bd

(G i ) ≤ 1 + bd(G i \ v) ≤ 1 + bd(G \ v). Since all other components G j of G also occur as components of G \ v, it follows that bd(G j ) ≤ bd(G \ v), implying bd(G ) ≤ 1 + bd(G \ v) = 1 + bd(G \ X) since G \ v = G \ X. Hence bd(G) ≤ |X | + 1 + bd(G \ X).

Proof of 6:

We use induction on |V (G)|; the base case follows directly from the definitions. It is well-known (cf. [2, Lemma 6]) that the tree-width of G is the maximum treewidth of its biconnected components. Hence it suffices to prove that for an arbitrary biconnected component

G of G, we have tw(G ) ≤ bd(G ). If G consists of a single edge, then tw(G ) = bd(G ) = 1. Otherwise, G is a connected bridgeless graph. This implies (G ) cb = G , so by Definition 3.1 there is a vertex v ∈ V (G ) such that bd(G ) = 1 + bd(G \ v). Since G is a minor of G, we have bd(G ) ≤ bd(G) by Item 3. By induction, the tree-width of G \ v is at most bd(G \ v) ≤ bd(G) -1.
Adding vertex v to all bags of a tree decomposition of this width, gives a valid tree decomposition of G of width at most bd(G \ v) + 1 ≤ bd(G ). Hence tw(G ) ≤ bd(G ) for all biconnected components of G.

A (c + 1) × (c + 1)-grid is a planar graph of tree-width exactly c + 1 [2, Cor. 89], which implies by Item 6 of Proposition 3.2 that its bridge-depth is larger than c. This gives the following consequence of Proposition 3.2, which will be useful when invoking algorithmic meta-theorems. Observation 3.3. For each c ∈ N, the graphs of bridge-depth at most c form a minor-closed family that excludes a planar graph. By the Graph Minor Theorem [START_REF] Robertson | Graph minors. XX. Wagner's conjecture[END_REF], there is a finite set of forbidden minors H c such that bd(G) ≤ c if and only if G excludes all graphs of H c as a minor. The set H c contains a planar graph, since some planar graphs have bridge-depth > c. The following concept will be crucial to facilitate a recursive approach for reducing graphs of bounded bridge-depth. Proof. Given G, we compute its decomposition into biconnected components, which can be done in linear time taking into account that having bounded bridge-depth implies a linear number of edges [START_REF] Hopcroft | Efficient algorithms for graph manipulation (algorithm 447)[END_REF]. From this decomposition, it is straightforward to identify the inclusion-maximal trees of bridges in G. For each tree of bridges T in G, we can test whether bd(G \ V (T )) < c = bd(G) in linear time using Proposition 3.4, and we output T if this is the case. By Proposition 3.2, such a tree T exists. Since G is decomposed into at most n trees of bridges, and we need a linear-time computation for each T , this results in an O(n 2 )-time algorithm.

Bounded minimal blocking sets imply bounded bridge-depth

The goal of this section is to prove one direction of Theorem 1. This result can be seen as an analog to the fact that the tree-depth of a graph can be bounded in terms of the length of the longest simple path it contains (as a subgraph or as a minor, which is equivalent for paths). A classical proof of this fact (see [START_REF] Nesetril | Sparsity -Graphs, Structures, and Algorithms[END_REF]) is to consider a depth-first search tree of G, bounding the tree-depth of G by the depth of this tree. However, it does not seem immediate to find a similar bound for bridge-depth.

We therefore follow another approach, inspired by the following alternative proof that the tree-depth is upper-bounded by the length of the longest path (which gives a worse bound). Observe that in a connected graph G, any two longest paths intersect at a vertex. (If they did not, one could combine them to make an even longer path.) Given a connected graph G whose longest path has t vertices, we can bound its tree-depth by f (t) := t i=1 i as follows. Let P be a longest path in G. Then the longest path in G \ V (P ) has strictly fewer than t vertices, and by induction the tree-depth of G \ V (P ) is at most f (t -1). From the definition of tree-depth, it follows that the tree-depth of G is at most |V (P )| = t larger than that of G \ V (P ), so the tree-depth of G is at most f (t).

In the case of bridge-depth, where paths are replaced with necklaces contained as minors, we cannot afford to remove the entire set of vertices of the corresponding model of a longest necklace, as the size of this set cannot be bounded in terms of the length t of the necklace. To overcome this problem, we will prove in Lemma 4.6, similarly to the case of paths, that there cannot be two vertex-disjoint longest necklaces. Then we resort to the Erdős-Pósa property, which gives us a set of vertices of size f (t) whose removal decreases the maximum length of a longest necklace. We now formalize these ideas. We need to introduce the Erdős-Pósa property for packing and covering minor models. Let F be a finite collection of simple graphs. An F-model is an H-model for some H ∈ F. Two F-models M 1 and M 2 are disjoint if V (M 1 ) ∩ V (M 2 ) = ∅. Let ν F (G) be the maximum cardinality of a packing of pairwise disjoint F-models in G, and let τ F (G) be the minimum size of a subset X ⊆ V (G) such that G \ X has no F-model. Clearly, ν F (G) ≤ τ F (G). We say that the Erdős-Pósa property holds for F-models if there exists a bounding function

f : N → N such that, for every graph G, τ F (G) ≤ f (ν F (G)).
In the case where F = {H} contains a single connected graph H, Robertson and Seymour [START_REF] Robertson | Graph minors. V. Excluding a planar graph[END_REF] proved the following result.

Theorem 4.4 (Robertson and Seymour [34]). Let H be a connected graph. The Erdős-Pósa property holds for H-models if and only if H is planar.

It is worth mentioning that a tight bounding function when H is planar has been recently obtained by van Batenburg et al. [START_REF] Cames Van Batenburg | A tight Erdös-Pósa function for planar minors[END_REF]. Theorem 4.4 easily implies the following corollary. Corollary 4.5. For every t ≥ 1, the Erdős-Pósa property holds for N t -models.

Proof. For t ≥ 1, let F t be the set containing all minor-minimal simple graphs that contain the necklace N t as a minor. By definition, a simple graph G contains an N t -model if and only if it contains an F t -model. Clearly, all the graphs in F t are connected and planar, and it is easy to see that |F t | is bounded by a function of t. For each F ∈ F t , by Theorem 4.4 there is a function f F such that if G does not contain k vertex-disjoint models of F , then all the F -models of G can be hit by at most f F (k) vertices. This implies that if G does not contain k models of any graph in F t , then the union of all hitting sets has size bounded by F ∈Ft f F (k), and since F t is finite this is a valid bounding function for N t -models.

We denote by f Nt the bounding function for N t -models given by Corollary 4.5. In a connected bridgeless graph, each pair of maximum-length necklace models intersect at a vertex: Lemma 4.6. If G is a connected bridgeless simple graph with nm(G) = t, then ν Nt (G) = 1.

Proof. Suppose for contradiction that G contains two disjoint models M 1 and M 2 of N t . For i ∈ [t + 1] and ∈ [START_REF] Hans | A partial k-arboretum of graphs with bounded treewidth[END_REF], let S i be the vertex set of M given by Observation 4.2. Note that these 2t + 2 subsets of vertices of G are pairwise disjoint, and that for any i ∈ [t], there are at least two edges between S i and S i+1 . Since G is bridgeless and connected, it is 2-edge-connected and by Menger's theorem [11, § 3.3] G contains two edge-disjoint paths between any pair of vertices. Pick two arbitrary vertices x 1 ∈ M 1 , x 2 ∈ M 2 , and let P 1 , P 2 be two edge-disjoint paths between them. Consider the subpath Q of P between the last vertex of M 1 that is visited, until the first vertex of

M 2 . Let Q = (v 1 , . . . , v q ) where v 1 ∈ M 1 and v q ∈ M 2 . Let a such that v 1 ∈ S 1
a and b such that v q ∈ S 2 b . Let us first show that if t is odd, then we can use Q 1 to find an N t -model M for some t > t by "gluing" M 1 and M 2 , leading to a contradiction.

Let S = S 1 a1 ∪ V (Q 1 ) ∪ S 2 b1 . If a 1 > t+1 2 define A = {S 1 1 , . . . , S 1 a1-1 }, and otherwise define A = {S 1 a1+1 , . . . , S 1 t+1 }. Similarly, if b 1 > t+1 2 define B = {S 2 1 , . . . , S 2
b1-1 }, and otherwise define B = {S 2 b1+1 , . . . , S 2 t+1 }. Note that the sets A, S, B are pairwise disjoint. Since t is odd, it can be easily checked that M = A ∪ {S} ∪ B is an N t -model in G for some t > t; see Figure 1(a) for an illustration. us now consider the case where t is even. Note first that if there exists ∈ [START_REF] Hans | A partial k-arboretum of graphs with bounded treewidth[END_REF] such that a = t 2 + 1 or b = t 2 + 1, then we can use Q to find an N t -model for some t > t as in the previous case. Hence, it only remains to consider the case where

S 1 a1 S 1 a2 S 2 b1 S 2 b2 Q 1 Q 2 M 1 M 2 (a) S 1 t 2 +1 (b) Q 1 Q 2 M 1 M 2 v 1 q1 = v 2 q2 v 2 q2-1 v 1 q1-1
a 1 = b 1 = a 2 = b 2 = t 2 + 1, meaning that Q 1 and Q 2 are two edge-disjoint paths, both between S 1 t 2 +1 and S 2 t 2 +1 . Let A = {S 1 1 , . . . , S 1 t 2 }, B = {S 2 1 , . . . , S 2 t 2
}, and

S = S 1 a1 ∪ (V (Q 1 ) \ {v 1 q1 }) ∪ (V (Q 2 ) \ {v 2 q2 }). We claim that M = A ∪ {S, S 2 t 2 +1 } ∪ B is an N t+1 -model. Indeed,
τ Nt (G) ≤ f Nt (ν Nt (G)) = f Nt (1).
Thus, there exists a set X ⊆ V (G) with |X| ≤ f Nt [START_REF] Hans | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF] such that G \ X has no N t -model, implying that nm(G \ X) < t.

We are finally in position to prove the following theorem. Proof. We prove the statement by induction on nm(G), for the function f defined by f (t) := 1 + t i=1 f Ni [START_REF] Hans | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF]. If nm(G) = 0, then G is a forest, and by definition of bridge-depth we get bd(G) = 1 = f (0). Suppose now that nm(G) = t with t > 0.

Consider the case that G is connected. Then G cb is also connected and has no bridge, and thus we can apply Corollary 4.7 and get a set X ⊆ V (G cb ) with |X| ≤ f Nt [START_REF] Hans | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF] such that nm(G ) < t, where G = G cb \ X. By Item 5 of Proposition 3.2, we get that bd(G) = bd(G cb ) ≤ |X| + bd(G ). Let G 1 , . . . , G be the connected components of G . As nm(G ) < t, we get that nm(G i ) < t for every i ∈ [ ]. Then, by induction hypothesis it follows that, for every

i ∈ [ ] , bd(G i ) ≤ f (t -1) = 1 + t-1 i=1 f Ni (1). Thus, as bd(G ) = max i∈[ ] bd(G i ) ≤ 1 + t-1 i=1 f Ni (1), we get that bd(G) ≤ |X| + bd(G ) ≤ f Nt (1) + 1 + t-1 i=1 f Ni (1) = 1 + t i=1 f Ni (1) = f (nm(G)).
Finally, if G is disconnected, let G 1 , . . . , G be its connected components, and note that bd(G) = max i∈[ ] bd(G i ). Since for every i ∈ [ ] it holds that nm(G i ) ≤ nm(G), and since the function f is non-decreasing, by applying the above case to each connected component of G we get that

bd(G) = max i∈[ ] bd(G i ) ≤ max i∈[ ] f (nm(G i )) ≤ max i∈[ ] f (nm(G)) = f (nm(G)).
Now that we established a relation between bridge-depth and necklace minors, our next step is to relate necklace minors to blocking sets. For this purpose, we use the known triangle-path gadget.

Definition 4.9. A triangle-path of length t is the graph consisting of t vertex-disjoint triangles, with vertex sets {{a

i , b i , c i } | i ∈ [t]}, together with the t -1 edges {{b i , a i+1 } | i ∈ [t -1]}. The triangle-path-

minor length of a graph G, denoted by tpm(G), is the largest length of a triangle-path contained in G as a minor, or zero if no such minor exists.

A slight variation of this gadget was used by Fomin and Strømme [START_REF] Fedor | Vertex cover structural parameterization revisited[END_REF]Def. 6]. We observe the following (cf. [START_REF] Fedor | Vertex cover structural parameterization revisited[END_REF]).

Observation 4.10. Let G be a triangle-path of length

t ≥ 2. Then mbs(G) ≥ t + 2, as {a 1 , c 1 } ∪ {b t , c t } ∪ {c i | i ∈ [2, t -1]} is a minimal blocking set.

Proof. Let t = nm(G), and let {S

i | i ∈ [t + 1]} be an N t -model in G. Let i ∈ [ t+1 2 ]
and let e 1 = {u 1 , v 1 } and e 2 = {u 2 , v 2 } be the two edges between S 2i-1 and S 2i , with u ∈ S 2i-1 and v ∈ S 2i . If u 1 = u 2 then there is a partition A 1 , A 2 of S 2i-1 such that u i ∈ A i and A i is connected for i ∈ [2], and we define

L i = {A 1 , A 2 }, R i = {S 2i }. Otherwise, if u 1 = u 2 , then necessarily v 1 = v 2 ,

and we define symmetrically

L i = {S 2i-1 } and R i = {A 1 , A 2 }.
In both cases we get that L i ∪ R i is a model of a triangle, and moreover there is an edge between a vertex in R i and a vertex in

L i+1 for every i ∈ [ t+1 2 -1]. This implies that i∈[ t+1 2 ] (L i ∪ R i ) is a model of a triangle-path of length t+1 2 in G.
Corollary 4.12. There is a function g : N → N such that bd(G) ≤ g(tpm(G)) for all graphs G. Proof. By Lemma 4.11, we have that tpm(G) ≥ nm(G)/2. By letting g(t) := f (2t), where f is the function given by Theorem 4.8, we get the desired result. Using this corollary, we can prove one direction of Theorem 1.2. Theorem 4.14. Let F be a minor-closed family of graphs of unbounded bridge-depth. Then there are graphs in F that have arbitrarily large minimal blocking sets.

Proof. By Corollary 4.13, F contains all triangle-paths. Since a triangle-path of length t contains a minimal blocking set of size t + 2 by Observation 4.10, the theorem follows.

Theorem 4.14 is phrased for graph families, rather than individual graphs. There is no function h such that bd(G) ≤ h(mbs(G)) for all G: a bipartite grid graph can have arbitrarily large tree-width and therefore bridge-depth, but its minimal blocking sets have size at most two (cf. Lemma 5.2).

Bounded bridge-depth implies bounded-size blocking sets

In this section we prove the other direction of Theorem 1.2: minimal blocking sets in a graph G have size at most 2 bd(G) . We need the following consequence of Kőnig's theorem. The next lemma shows that minimal blocking sets in a bipartite graph have at most two vertices. This was known before, see for example [START_REF] Eva-Maria | Smaller parameters for vertex cover kernelization[END_REF]Thm. 14]. Our self-contained proof highlights an additional property of such minimal blocking sets: the two vertices of minimal blocking sets of size two belong to opposite partite sets. This will be crucial later on. Proof. Let M be a maximum matching in G, let V (M ) be the saturated vertices, and let U := V (G) \ V (M ) be the unsaturated vertices. Let R A∩U be the vertices that can be reached by an M -alternating path from A ∩ U (which necessarily starts with a non-matching edge). Let R B∩Y be the vertices that can be reached by an M -alternating path that starts with a matching edge from a vertex of B ∩ Y . Note that both types of alternating paths move from A to B over non-matching edges, and move from B to A over matching edges. We first deal with some cases in which we easily obtain a blocking set Y as desired.

Case 1: A ∩ Y ∩ R A∩U = ∅. Let a ∈ A ∩ Y ∩ R A∩U .
Then a ∈ A can be reached by an Malternating path P that starts in an unsaturated vertex in the same partite set, implying that P has even length and ends with a matching edge into a. Hence M := M ⊕ E(P ), where ⊕ denotes the symmetric difference, is a new maximum matching, and it does not saturate a ∈ A ∩ Y . Lemma 5.1 applied to M implies that all maximum independent sets of G contain a, showing that Y := {a} is a blocking set of size one. Assume now that none of the cases above hold. We will conclude the proof of the lemma by deriving a contradiction. Let R := R A∩U ∪ R B∩Y . The following will be useful.

Claim 5.3. If a ∈ A ∩ R and {a, b} ∈ E(G), then b ∈ B ∩ R.
Proof. By definition, a ∈ A ∩ R implies a is reachable by some M -alternating path P that moves to A over matching edges and moves to B over non-matching edges, such that P starts in a vertex v ∈ (A ∪ U ) ∪ (B ∩ Y ). But then b is also reachable by such an alternating path from v: if {a, b} ∈ M then, since P ends at a, edge {a, b} must be the last edge of P , so a prefix of P is an M -alternating path reaching b; if {a, b} / ∈ M then appending {a, b} to P yields such an M -alternating path. Hence b ∈ R, and b ∈ B follows since G is bipartite. Now consider the following set: S := (A ∩ R) ∪ (B \ R).

We will prove that S is a maximum independent set of G disjoint from Y , contradicting the assumption that Y is a blocking set. To see that S is indeed an independent set, consider any vertex from A ∩ S, which belongs to A ∩ R. By Claim 5.3 all neighbors of a belong to B ∩ R, and are therefore not contained in S. Hence S is indeed an independent set. To see that it is maximum, by Lemma 5.1 it suffices to argue it contains all of U and one endpoint of each edge in M .

To see that S contains all vertices of A ∩ U , note that all such vertices are trivially in R A∩U and therefore in R, implying their presence in A ∩ R and therefore in S. To see that S contains all vertices of B ∩ U , it suffices to show that B ∩ U ∩ R = ∅, which follows from the fact that neither Case 2 nor Case 4 is applicable. Hence S contains all vertices of U .

To see that S contains an endpoint of each edge of M , let {a, b} ∈ M be arbitrary with a ∈ A and b ∈ B. If b / ∈ R then clearly b ∈ S, as desired. If b ∈ R, then this is witnessed by an alternating path P that reaches b and ends with a non-matching edge. Extending P with the edge {a, b} ∈ M then shows that a ∈ R, so that a ∈ A ∩ R is an endpoint of the edge contained in S.

Hence S is a maximum independent set in G. Since Case 1 and Case 3 do not apply, it follows that A ∩ R ∩ Y = ∅, so that S ∩ A contains no vertex from Y . Since all vertices of B ∩ Y are trivially in R B∩Y and therefore in R, it follows that B \ R contains no vertex from Y . Hence S is a maximum independent set in G disjoint from Y , contradicting the assumption that Y is a blocking set.

We will use Lemma 5.2 to power the induction step in the proof of the next theorem, which gives the desired upper-bound on the size of minimal blocking sets in terms of bridge-depth. The main idea in the induction step is as follows. For a connected graph G, we consider a tree of bridges T for which bd(G \ V (T )) < bd(G). We can summarize the relevant ways in which a maximum independent set in G can be composed out of maximum independent sets for the connected components of G \ E(T ), into a weighted tree T that is obtained from T by adding a pendant leaf to each vertex. In turn, maximum-weight independent sets in T correspond to maximum independent sets a bipartite graph obtained from T by replacing each vertex by a set of false twins. Applying Lemma 5.2 to this bipartite graph points to two vertices that form a blocking set. We can translate this back into two components of G \ E(T ) that are sufficient for constructing a blocking set in G, and apply induction using the fact that bd(G \ V (T )) < bd(G).

Theorem 5.4 ( ). Let G be a graph and Y

G ⊆ V (G) a blocking set in G. There is a blocking set Y G ⊆ Y G in G of size at most 2 bd(G) .
Note that Theorem 5.4 and Theorem 4.14 together prove Theorem 1.2. We finish the section by showing that the upper-bound of 2 bd(G) on the size of minimal blocking sets is tight. Theorem 5.5. For every c ∈ N, there is a graph G with bd(G) ≤ c that contains a minimal blocking set of size 2 c . Proof. Recall the notion of triangle-path from Definition 4.9. For t ≥ 2, let a truncated triangle-path of length t be the graph U t obtained from a triangle-path of length t by removing vertices a 1 and b t ; see Figure 2. Analogously to Observation 4.10, we show that Y t := {c i | i ∈ [t]} is a minimal blocking set in U t . Since Y t is an independent set of size t, while (the remainders of) the triangles in U t partition the vertices of U t into t cliques, it follows that α(U t ) = t. The set Y t is a blocking set, since U t \ Y t is a path on 2(t -1) vertices, whose independence number is only t -1. Finally, it is easy to see that for any y ∈ Y t , there is a size-t independent set in U t \ (Y t \ y) that consists of the vertex y and, for every (remainder of a) triangle in U t , the vertex closest to y. Hence U t has a minimal blocking set of size t, for all t ≥ 2. To prove the theorem, it therefore suffices to show that bd(U 2 c ) ≤ c for all c ∈ N. We prove this by induction on c. For c = 1, note that the graph U 2 is just the four-vertex path. Hence it is a forest, implying bd(U 2 ) = 1 by Proposition 3.2. For c > 1, consider the graph U 2 c . By construction, the middle edge e = {b 2 c-1 , a 2 c-1 +1 } is a bridge in U 2 c . Let T be the tree in U 2 c consisting of the single bridge e. Note that removing V (T ) splits U 2 c evenly, into two connected components that are both isomorphic to

U 2 c-1 . By induction, bd(U 2 c-1 ) ≤ c -1. Then Proposition 3.2 shows that bd(U 2 c ) ≤ 1 + bd(U t \ V (T )) = 1 + (c -1) = c.

Kernelization for modulators to bounded bridge-depth

To establish the positive direction of Theorem 1.1, we develop a polynomial kernel for Vertex Cover parameterized by the size of a modulator X whose removal leaves a graph of constant bridge-depth; an approximately optimal such set X can be computed using Proposition 3.5. As the kernelization is technical and consists of many different reduction rules, with a nontrivial size analysis, the material is deferred to the full version [START_REF] Bougeret | Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel[END_REF]. In this limited space, we present the high-level idea behind the kernelization and the role of bridge-depth.

Consider an instance (G, k) of Vertex Cover with a modulator X such that bd(G\X) ∈ O(1). As explained in the introduction, using the fact that minimal blocking sets for the components C of G \ X have bounded size, the number of such components can easily be bounded by |X| O (1) . To bound the size of individual components, the definition of bridge-depth ensures that in each connected component C of G \ X there is a tree of bridges T ⊆ E(C) (called a lowering tree) such that removing the vertex set V (T ) from C decreases the bridge-depth of C. By designing new problem-specific reduction rules, we shrink the tree of bridges to size polynomial in the parameter. This is where the main technical work of the kernelization step lies. It properly subsumes the earlier kernelization for the parameterization by distance to a forest, which is imported as a black box in all previous works [START_REF] Bougeret | How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs[END_REF][START_REF] Fedor | Vertex cover structural parameterization revisited[END_REF][START_REF] Eva-Maria | Smaller parameters for vertex cover kernelization[END_REF][START_REF] Eva-Maria | Elimination distances, blocking sets, and kernels for vertex cover[END_REF][START_REF] Majumdar | Polynomial kernels for vertex cover parameterized by small degree modulators[END_REF]. Having bounded the number of components of G \ X, together with the size of a lowering tree of bridges in each component, we now proceed as follows: in each component C of G \ X we move the vertices from a lowering tree of bridges into the set X. This blows up |X| by a polynomial factor, but strictly decreases the bridge-depth of the graph G \ X. We then recursively kernelize the resulting instance. When the bridge-depth of G \ X reaches zero, the graph G \ X is empty and the kernelization is completed. Full details can be found in the full version [START_REF] Bougeret | Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel[END_REF].

The negative direction of Theorem 1.1 is much easier to establish. Using the fact that a minor-closed family F of unbounded bridge-depth contains all triangle paths, a kernelization lower bound for modulators to such F follows easily using known gadgets.

Conclusion

In this paper we introduced the graph parameter bridge-depth and used it to characterize the minor-closed graph classes F for which Vertex Cover parameterized by F-modulator has a polynomial kernel. It would be interesting to see whether the characterization can be extended to subgraph-closed or even hereditary graph classes. If a characterization exists of the hereditary graph classes whose modulators lead to a polynomial kernel, it will likely not be as clean as Theorem 1.1: it will have to deal with the fact that bipartite graphs can be arbitrarily complex in terms of width parameters, while bipartite modulators allow for a polynomial kernel. Hence such a characterization has to capture parity conditions of F.

A natural attempt to generalize our approach to deal with bipartite graphs is to consider the following parameter, which we call bipartite-contraction-depth: we mimic the definition of bridge-depth (cf. Definition 3.1), except that we redefine the graph G cb to be the graph obtained from G by simultaneously contracting all edges that do not lie on an odd cycle. Note that bipartite-contraction-depth generalizes bridge-depth, in the sense that bridges do not lie on an odd cycle, and that the bipartite-contraction-depth of a graph with an odd cycle transversal of size k is at most k + 1. Having defined this parameter, we would need, in order to obtain a statement similar to Theorem 4.14, that large bipartite-contraction-depth implies the existence of structures that allow to obtain kernel lower bounds, similarly to the fact that large bridge-depth implies the existence of large triangle-paths (cf. Corollary 4.13). The appropriate structure here seems to be an odd-cycle-path of length t, defined as a set of t vertex-disjoint odd cycles C 1 , . . . , C t , and a set of t -1 vertex-disjoint paths (of any length) connecting C i to C i+1 for i ∈ [t -1], in such a way that for every i ∈ {2, . . . , t -1}, the two attachment vertices in C i are distinct. Now the expected property would be that large bipartite-contraction-depth forces long odd-cycle-paths. Unfortunately, this is not true. Indeed, consider the Escher wall of size h depicted in [START_REF] Rautenbach | The Erdös-Pósa Property for Odd Cycles in Highly Connected Graphs[END_REF]Fig. 3]. It is proved in [START_REF] Rautenbach | The Erdös-Pósa Property for Odd Cycles in Highly Connected Graphs[END_REF] that this graph does not contain two vertex-disjoint odd cycles, but a smallest hitting set for odd cycles has size h. Since there are no two vertex-disjoint cycles, a longest odd-cycle-path has length one. On the other hand, it can be easily verified that an Escher wall of size h has bipartite-contraction-depth Ω(h). Informally, this can be seen by noting that, initially, all edges lie on an odd cycle, hence a vertex removal is required, and that each such removal cascades in a constant number of contractions until all edges lie again on an odd cycle. Since a smallest hitting set for odd cycles of an Escher wall of size h has size h, the claimed bound follows. Therefore, summarizing this discussion, if one aims at a result similar to Theorem 1.1 that also applies to families F containing bipartite graphs, it seems that significant new ideas are required.

Another open research direction consists of a further algorithmic exploration of the merits of bridge-depth. We expect that several polynomial-space fixed-parameter tractable algorithms that work for graphs of bounded tree-depth [START_REF] Chen | Width, depth, and space: Tradeoffs between branching and dynamic programming[END_REF][START_REF] Pilipczuk | On space efficiency of algorithms working on structural decompositions of graphs[END_REF] can be extended to work with bridge-depth instead. Which other ways to enrich the recursive definition of tree-depth lead to novel algorithmic insights? As for kernelization purposes, it is plausible that bridge-depth also characterizes the existence of polynomial kernels for other problems other than Vertex Cover, parameterized by the vertex-deletion distance of the input graph to a minor-closed graph class.

Observation 3 . 3 ,Proposition 3 . 4 (

 3334 together with known results on minor testing, imply the following. Follows from[START_REF] Hans | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF] Thm. 7.1]). For each constant c ∈ N, there is a linear-time algorithm to test whether the bridge-depth of a given graph G is at most c.Fomin et al.[START_REF] Fedor | Hitting forbidden minors: Approximation and kernelization[END_REF] Thm. 1.3] gave a generic approximation algorithm for finding a small vertex set that hits forbidden minors from a finite forbidden set containing a planar graph. By Observation 3.3, deleting vertices to obtain a graph of bounded bridge-depth fits into their framework. Proposition 3.5 (Follows from [15, Thm. 1.3]). For each fixed c ∈ N there is a polynomialtime algorithm that, given a graph G, outputs a set X ⊆ V (G) such that bd(G \ X) ≤ c and |X| ≤ O(|X opt | log 2/3 |X opt |), where |X opt | is the minimum size of such a set.

Definition 3 . 6 .Proposition 3 . 7 .

 3637 A lowering tree T of a graph G is a tree of bridges (possibly consisting of a single vertex and no bridges) such that bd(G \ V (T )) = bd(G) -1. Item 4 of Proposition 3.2 implies that any connected graph G has a lowering tree. For each fixed c ∈ N there is an algorithm that, given a connected graph G on n vertices of bridge-depth c, computes a lowering tree in O(n 2 ) time.

Figure 1

 1 Figure 1 (a) Example with t = 3 and a1 = b1 = 2. (b) Example with t = 4.

2 t 2 +1

 22 note in particular there are two edges between S and S as we cannot havev 1 q1-1 = v 2 q2-1 and v 1 q1 = v 2 q2 because Q 1 and Q 2 are edge-disjointand G is a simple graph; see Figure 1(b) for an illustration. By combining Corollary 4.5 with Lemma 4.6 we easily get the following corollary.

Corollary 4 . 7 .

 47 Let G be a connected bridgeless graph and t = nm(G). Then G contains a set of vertices X with |X| ≤ f Nt[START_REF] Hans | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF] such that nm(G \ X) < nm(G), where f Nt : N → N is the bounding function given by Corollary 4.5.I C A LP 2 0 2 0 16:12 Bridge-Depth Characterizes Kernelization Complexity of Vertex Cover Proof. By Lemma 4.6, it follows that ν Nt (G) = 1, and therefore by Corollary 4.5

Theorem 4 . 8 .

 48 There is a function f : N → N such that bd(G) ≤ f (nm(G)) for all graphs G.

Lemma 4 . 11 .

 411 For any graph G, tpm(G) ≥ nm(G)+1

2 .

 2

Corollary 4 . 13 .

 413 Let F be a minor-closed family of graphs. If F has unbounded bridge-depth then it contains the family F tp of all triangle-paths.

Lemma 5 . 1 .

 51 Let G be a bipartite graph and let M be a maximum matching in G. Every maximum independent set of G contains all vertices that are not saturated by M , and exactly one endpoint of each edge in M . Proof. Consider a maximum independent set S in G. Then S := V (G) \ S is a minimum vertex cover of G. By Kőnig's theorem (cf. [11, Thm. 2.1.1]) we have |S| = |M |. Since S is a vertex cover it contains at least one endpoint of each edge of M ; since |S| = |M | it contains exactly one endpoint of each edge of M , and no other vertices of G. So the complement S contains all vertices that are not saturated by M , and exactly one endpoint of each edge in M .

Lemma 5 . 2 .

 52 Let G be a bipartite graph with partite sets A and B. If Y ⊆ V (G) is a blocking set in G, then there is a blocking set Y ⊆ Y in G such that one of the following holds: |Y | = 1, or Y = {a, b} for some a ∈ A and b ∈ B.

Case 2 :

 2 B ∩ U ∩ R B∩Y = ∅. By definition, some u ∈ B ∩ U can be reached by an Malternating path P that starts in some vertex b ∈ B ∩ Y that belongs to the same partite set. Similarly as in the previous case, M := M ⊕ E(P ) is a new maximum matching that does not saturate b, so by Lemma 5.1 applied to M we conclude that Y := {b} is a blocking set of size one. Case 3: A ∩ Y ∩ R B∩Y = ∅. By definition, some a ∈ A ∩ Y is reachable by an Malternating path P from some b ∈ B ∩ Y , and P starts with a matching edge. Since it ends in the other partite set, it ends with a matching edge as well; hence both a and b are saturated. We claim that Y := {a, b} is a blocking set in G, as desired. Let a = a 1 , b 1 , . . . , a k , b k = b be the vertices on P , so that {a i , b i } ∈ M for all i ∈ [k] and {b i , a i+1 } ∈ E(G) \ M for i ∈ [k -1]. By Lemma 5.1, a maximum independent set in G contains one endpoint of each of the edges {a i , b i } ∈ M . A maximum independent set avoiding a 1 therefore has to contain b 1 , preventing it from containing a 2 , forcing it to contain b 2 , and so on. Hence a maximum independent set avoiding a 1 contains b k , proving that Y := {a, b} = {a 1 , b k } is a blocking set in G. Case 4: B ∩ U ∩ R A∩U = ∅. Then some unsaturated vertex of A can reach an unsaturated vertex of B by an M -alternating path P . But then M is not a maximum matching since M ⊕ E(P ) is larger; a contradiction. Hence this case cannot occur.

a 2 b 2 a 3 b 3 a 4 b 4 a 5 b 5 8 Figure 2

 582 Figure 2 Truncated triangle path U8 of length 8, illustrating Theorem 5.5. Removing the fat middle bridge and its incident vertices, leaves two connected components isomorphic to U4.

  and therefore a minor of G cb by hypothesis. If (G i ) cb is a minor of the graph G cb \ v

* , then by induction and Item 2 we have bd(

0 2 0 16:8 Bridge-Depth Characterizes Kernelization Complexity of Vertex Cover Thus

  , it only remains to prove that G cb is a minor of G cb . Let us first assume that G is obtained from G by removing an edge e.Let {T v | v ∈ V (G cb )} be the G cb -model in Ggiven by the trees of bridges. If e is not a bridge, then e is an edge between T u and T v for some vertices u, v ∈ V (G cb ). To obtain G cb as a minor, we start from G cb , remove edge {u, v}, and for any edge e between T u and T v (for any u , v ∈ V (G cb )) that has become a bridge in G because of the removal of e, we contract {u , v }. This implies that G cb is a minor of G cb . Otherwise, if e is a bridge, then there exists u ∈ V (G cb ) such that e ∈ E(T u ), and G has two connected components G 1 and G 2 . To obtain (G i ) cb as a minor, for i ∈[START_REF] Hans | A partial k-arboretum of graphs with bounded treewidth[END_REF], we start from G cb and remove any vertex v such that T v ∩ V (G i ) = ∅ (notice that u appears both in (G 1 ) cb and (G 2 ) cb ). Thus, both (G 1 ) cb and (G 2 ) cb are minors of G cb , hence G cb as well. The case where G is obtained from G by contracting an edge e can be proved using similar but simpler arguments. Indeed, if e is a bridge in G, then we have that G cb = G cb , and if it is not, if suffices to contract in G cb the edge {u, v} with u, v ∈ V (G cb ) such that e is an edge between T u and T v .

).

I C A L P 2

Proof of 4: Let v ∈ V (G cb ) and T v be its associated tree of bridges in G. Observe first that we may have

(G \ V (T v )) cb = G cb \ v. Indeed,

if for example we consider G composed of two vertex-disjoint triangles {a, b, c}, {a , b , c } and an edge e = {a, a }, and if we consider

0 2 0 16:10 Bridge-Depth Characterizes Kernelization Complexity of Vertex Cover

  2, showing that if F has bounded-size minimal blocking sets, then F has bounded bridge-depth. As explained in Section 1, we prove this via the intermediate structure of necklace minors and show that the bridge-depth of a graph G can be upper-bounded in terms of the longest necklace contained in it as a minor.

I C A L P 2

Funding Bart M. P. Jansen: This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch). Ignasi Sau: Supported by French projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).