11institutetext: Eindhoven University of Technology, P.O. Box 513, 5600 MB
Eindhoven, the Netherlands

# Kernelization for Feedback Vertex Set via Elimination Distance to a Forest

David Dekker 11 Bart M.P. Jansen 11

###### Abstract

We study efficient preprocessing for the undirected Feedback Vertex Set
problem, a fundamental problem in graph theory which asks for a minimum-sized
vertex set whose removal yields an acyclic graph. More precisely, we aim to
determine for which parameterizations this problem admits a polynomial kernel.
While a characterization is known for the related Vertex Cover problem based
on the recently introduced notion of bridge-depth, it remained an open problem
whether this could be generalized to Feedback Vertex Set. The answer turns out
to be negative; the existence of polynomial kernels for structural
parameterizations for Feedback Vertex Set is governed by the elimination
distance to a forest. Under the standard assumption
$\mathrm{NP}\not\subseteq\mathrm{coNP}/\mathrm{poly}$, we prove that for any
minor-closed graph class $\mathcal{G}$, Feedback Vertex Set parameterized by
the size of a modulator to $\mathcal{G}$ has a polynomial kernel if and only
if $\mathcal{G}$ has bounded elimination distance to a forest. This captures
and generalizes all existing kernels for structural parameterizations of the
Feedback Vertex Set problem.

###### Keywords:

Feedback Vertex Set Kernelization Elimination distance.

##  1 Introduction

For NP-complete problems, a polynomial time algorithm solving any problem
instance exactly is unlikely to exist. However, as one is often interested in
solving specific instances, one can try to exploit characteristics of problem
instances and develop algorithms that are fast when the input has certain
properties. We therefore associate a parameter with each problem instance. In
our context, a problem instance is a graph for which we ask for the existence
of a vertex set of size at most $\ell$ having certain properties. Such a
parameterized instance can be denoted with a triple $(G,\ell,k)$, where we are
asking for the existence of a solution of size at most $\ell$ for a graph $G$
with parameter $k$. We say that an algorithm is _fixed parameter tractable_
(FPT) for such a parameterization if it solves any instance $(G,\ell,k)$ of
size $n$, as described above, in time bounded by $f(k)n^{\mathcal{O}(1)}$ for
some computable function $f\colon\mathbb{N}\rightarrow\mathbb{N}$.

A strongly related field is that of _kernelization_. This field focuses on
reducing a parameterized instance $(G,\ell,k)$ in polynomial time to an
equivalent instance $(G^{\prime},\ell^{\prime},k^{\prime})$ whose size is
bounded by a computable function of the parameter. We speak of a polynomial
kernel when this function is a polynomial. It is known that a decidable
parameterized problem is fixed parameter tractable if and only if it admits a
kernelization [5]. In our quest for determining which parameterizations enable
efficient algorithms, it is therefore interesting to determine those that
allow a polynomial kernel.

This paper focuses on polynomial kernels for the undirected Feedback Vertex
Set problem, which is an NP-complete problem in graph theory as originally
identified by Karp [34]. For an undirected graph $G$, a vertex set $X\subseteq
V(G)$ is a _feedback vertex set_ if the graph is acyclic after removal of $X$.
We call such a vertex set whose removal yields a graph in some graph class
$\mathcal{G}$ a $\mathcal{G}$-modulator and define the deletion distance to
$\mathcal{G}$ as its minimum size. The Feedback Vertex Set problem now asks
for the minimum size of such a feedback vertex set, or equivalently, the
deletion distance to a forest. For a graph $G$, we let $\textnormal{{fvs}}(G)$
(the _feedback vertex number_ of $G$) denote that minimum size. Our main
question is for which parameterizations the Feedback Vertex Set problem admits
a polynomial kernel.

Before exploring the Feedback Vertex Set problem further, we should mention
the related Vertex Cover problem. It asks for a minimum set of vertices
hitting all edges in a graph. While a kernel in the solution size with a
linear number of vertices can be obtained using various techniques [1, 14, 15,
13, 39], a polynomial kernel in a structurally smaller parameter was only
discovered in 2011, when Jansen and Bodlaender developed a polynomial kernel
in the feedback vertex number of a graph [31]. From there, many polynomial
kernels for Vertex Cover were discovered in modulators to even larger graph
classes [38, 9, 21, 26]. In 2020, Bougeret, Jansen and Sau proved the
following characterization under common hardness assumptions: Vertex Cover
admits a polynomial kernel in the size of a modulator to a minor-closed graph
family $\mathcal{G}$ if and only if $\mathcal{G}$ has bounded _bridge-depth_
[8]. With this result, they generalized all existing work on kernels in the
size of modulators to minor-closed graph families, and they proved that their
results cannot be improved further under common hardness assumptions.

These results now bring us back to the Feedback Vertex Set problem. For this
problem, finding a polynomial kernel in the solution size had been an open
problem for a long time. The first polynomial kernel with size bound
$\mathcal{O}(k^{11})$ was obtained in 2006 and it was subsequently improved to
a quadratic kernel [12, 7, 41]. After the improvements for Vertex Cover,
researchers also tried to develop polynomial kernels in smaller parameters for
Feedback Vertex Set [30, 37, 33]. It remained an open problem whether these
results could be generalized further or whether there exists some parameter
that characterizes Feedback Vertex Set similarly to how bridge-depth
characterizes Vertex Cover. In particular, Bougeret, Jansen and Sau suggested
in their paper on Vertex Cover that the deletion distance to constant bridge-
depth might also be an interesting parameter to consider for problems such as
Feedback Vertex Set. We therefore aim to answer the question for which graph
families $\mathcal{G}$ the Feedback Vertex Set problem admits a polynomial
kernel when parameterized by the size of a $\mathcal{G}$-modulator.

#### Our results

To our initial surprise, the results for Vertex Cover cannot be generalized to
Feedback Vertex Set. It turns out that a minor-closed graph family
$\mathcal{G}$ must have bounded _elimination distance to a forest_ (Definition
1), in order to allow a polynomial kernel in a $\mathcal{G}$-modulator. This
concept was introduced by Bulian and Dawar [11] and is another generalization
of the more common parameter treedepth [40]. Our result is described in
Theorem 1.1.

######  Theorem 1.1.

Let $\mathcal{G}$ be a minor-closed graph family. Then Feedback Vertex Set
admits a polynomial kernel in the size of a $\mathcal{G}$-modulator if and
only if $\mathcal{G}$ has bounded elimination distance to a forest, assuming
that $\mathrm{NP}\not\subseteq\mathrm{coNP}/\mathrm{poly}$.

The minor-closed and hardness assumptions are only needed for the lower bound.
To the best of our knowledge, our kernel generalizes all known polynomial
kernels for the Feedback Vertex Set problem. Both the kernel and its
correctness proof follow the structure of the kernel for $\mathcal{F}$-Minor
Free Deletion in the deletion distance to a graph of constant treedepth by
Jansen and Pieterse [33]. The correctness proof of their kernel crucially
relies on their Lemma 3 whose technical proof spans thirty pages. We require a
variation of this lemma. On the one hand, our variation is more involved since
it deals with elimination distance to a forest rather than treedepth; on the
other hand, it is simpler since it concerns only Feedback Vertex Set rather
than $\mathcal{F}$-Minor Free Deletion. As a result of this simplification, we
can formulate the lemma in terms of reducing some vertex sets $S$ and $T$. As
one of our main contributions, we prove this lemma using a strategy that
differs significantly from the one followed in earlier work [33].

######  Lemma 1.

Let $G$ be a connected graph with disjoint vertex sets $S,T\subseteq V(G)$.
Suppose that any minimum feedback vertex set $X$ of $G$ misses some vertex
from $S$ or leaves two vertices from $T$ connected in $G-X$. Then there exist
sets $S^{*}\subseteq S$ and $T^{*}\subseteq T$ whose sizes only depend on the
elimination distance to a forest of $G$, such that any minimum feedback vertex
set $X$ of $G$ misses some vertex from $S^{*}$ or leaves two vertices from
$T^{*}$ connected in $G-X$.

Once Lemma 1 is proven, the kernelization upper bounds follow similarly to
earlier work [33]. As for the lower bound in Theorem 1.1, we are also able to
generalize our proof for other $\mathcal{F}$-Minor Free Deletion problems as
described in Theorem 1.2.

######  Theorem 1.2.

Let $\mathcal{G}$ be a minor-closed family of graphs and let $\mathcal{F}$ be
a finite set of biconnected planar graphs on at least three vertices. If
$\mathcal{G}$ has unbounded elimination distance to an $\mathcal{F}$-minor
free graph, then $\mathcal{F}$-Minor Free Deletion does not admit a polynomial
kernel in the size of a $\mathcal{G}$-modulator, unless
$\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$.

#### Related work

FPT algorithms for Feedback Vertex Set parameterized by the solution size are
known with running times $\mathcal{O}^{*}(3.490^{k})$ (deterministic) and
$\mathcal{O}^{*}(2.7^{k})$ (randomized) [35, 28, 36]. The parameterization by
treewidth has led to deterministic $\mathcal{O}^{*}(11.36^{k})$ and randomized
$\mathcal{O}^{*}(3^{k})$ algorithms [18, 6]. Other FPT algorithms include
parameterizations by deletion distance to a chordal graph, by cliquewidth and
by the number of vertices of degree at least $4$ [30, 29, 10, 37]. Recently,
Donkers and Jansen proposed a parameterization based on the complexity of the
solution structure [20]. They introduced the notion of _antlers_ , similar to
the notion of crown decompositions for Vertex Cover.

#### Organization

Section 2 introduces all relevant terminology. Section 3 presents our kernel
and thereby proves the ‘if’ direction of Theorem 1.1. Then Section 4 contains
the proof of Theorem 1.2, thereby also proving the ‘only if’ direction of
Theorem 1.1. Lastly, Section 5 contains our conclusions and discusses future
work.

##  2 Preliminaries

For a positive integer $n$, we use the shorthand $[n]$ for the set of all
natural numbers $i$ with $1\leq i\leq n$. All graphs we consider are finite,
undirected and simple. When $G$ is a graph, we let $V(G)$ denote the vertex
set of $G$ and $E(G)$ the edge set. For $S\subseteq V(G)$, the graph $G-S$ is
the graph where all vertices in $S$ and all incident edges are removed, and
the graph $G[S]$ is the subgraph of $G$ induced by the vertices in $S$. When
an edge exists between two vertices in $G$, we say that these vertices are
_adjacent_. The _neighbors_ of $v$ in $G$, denoted with $N_{G}(v)$, are the
vertices adjacent to a vertex $v\in V(G)$ in $G$. For $S\subseteq V(G)$, we
say that $v\in V(G-S)$ is adjacent to $S$ if there exists some edge between
$v$ and a vertex in $S$. The set $N_{G}(S)$ contains all vertices $v\in
V(G-S)$ for which this holds. We will sometimes slightly abuse notation and
speak of a vertex being adjacent to some subgraph, rather than to the vertices
in that subgraph. We say that two vertices are _connected_ in $G$ when they
are in the same connected component. The set $\textnormal{{cc}}(G)$ denotes
the set of connected components (or shortly components) of $G$. For sets
$S,T\subseteq(V)$, we say that $S$ _separates_ $T$ if each component of $G-S$
contains at most one vertex from $T$. Notice that we do not require $S$ and
$T$ to be disjoint. Such a set $S$ is a _vertex multiway cut_ of $T$ in $G$.
We use the notation $\mathcal{O}_{\eta}(f(n))$ to describe the functions in
$\eta$ and $n$ which can be bounded by $g(\eta)\cdot f(n)$ for some computable
function $g$.

A concept that will be used extensively is the concept of graph minors. This
uses the notion of _edge contraction_. When $uv$ is an edge in a graph $G$,
contracting this edge replaces vertices $u$ and $v$ by a new vertex whose set
of neighbors is $N_{G}(\\{u,v\\})$. Now $H$ is a _minor_ of $G$ if $H$ can be
obtained from $G$ by removing vertices, removing edges and contracting edges.
Alternatively, one can define $H$ to be a minor of $G$ if there exists a
_minor model_ $\phi\colon V(H)\to 2^{V(G)}$, such that for any $v\in V(H)$ the
graph $G[\phi(u)]$ is connected, for any distinct $u,v\in V(H)$ we have
$\phi(u)\cap\phi(v)=\emptyset$, and for any edge $uv$ in $H$ there exists an
edge between a vertex in $\phi(u)$ and a vertex in $\phi(v)$ in $G$.

A graph $G$ has an $\mathcal{H}$-_minor_ for a set of graphs $\mathcal{H}$ if
$G$ contains some graph $H\in\mathcal{H}$ as a minor. For a minor model $\phi$
of $H$ in $G$ and a set $S\subseteq V(H)$, we use the shorthand notation
$\phi(S)\coloneqq\bigcup_{v\in S}\phi(v)$. We say that a minor model $\phi$ of
$H$ in $G$ is _minimal_ , if there does not exist a minor model
$\phi^{\prime}$ of $H$ in $G$ with $\phi^{\prime}(V(H))\subsetneq\phi(V(H))$.
A minor model $\phi$ of $H$ in $G$ and a minor model $\phi^{\prime}$ of
$H^{\prime}$ in $G$ _intersect_ if
$\phi(V(H))\cap\phi^{\prime}(V(H^{\prime}))\neq\emptyset$.

###  2.1 Elimination distance and treewidth

Our work relies crucially on the concept of elimination distance as introduced
by Bulian and Dawar [11].

######  Definition 1 (Elimination distance).

Let $G$ be a graph and $\mathcal{G}$ a graph family. Then the elimination
distance of $G$ to $\mathcal{G}$ is

$\textnormal{{ed}}_{\mathcal{G}}(G)=\begin{cases}0&\text{if
$G\in\mathcal{G}$,}\\\
\max_{G^{\prime}\in\textnormal{{cc}}(G)}\textnormal{{ed}}_{\mathcal{G}}(G^{\prime})&\text{if
$\lvert\textnormal{{cc}}(G)\rvert>1$,}\\\ \min_{v\in
V(G)}\textnormal{{ed}}_{\mathcal{G}}(G-\\{v\\})+1&\text{otherwise.}\\\
\end{cases}$

We only consider graph families $\mathcal{G}$ that are minor-closed. We use
the shorthand $\mathcal{G}_{F}$ for the graph family containing precisely all
forests. We say that a graph family $\mathcal{G}$ has bounded elimination
distance to some graph class $\mathcal{H}$ if all graphs in $\mathcal{G}$ have
bounded elimination distance to $\mathcal{H}$. The elimination distance of a
graph $G$ to the empty graph is called the _treedepth_ of $G$ and is denoted
with $\textnormal{{td}}(G)$. More intuitively, the elimination distance to a
graph class $\mathcal{G}$ can be interpreted as the minimum number of
‘elimination iterations’ that are necessary to obtain a graph where every
connected component is in $\mathcal{G}$. In such an iteration, one is allowed
to remove one vertex from each connected component. This interpretation leads
to the notion of an elimination forest.

######  Definition 2 ($\mathcal{G}$-elimination forest).

Let $G$ be a graph and $\mathcal{G}$ a graph family. A
$\mathcal{G}$-elimination forest of $G$ is a tuple $\left(F,(B_{u})_{u\in
V(F)}\right)$ where $F$ is a rooted forest and where each vertex $v\in V(F)$
has a bag $B_{v}\subseteq V(G)$ such that:

  * •

The bags define a partition of $V(G)$, i.e. for any vertex $v\in V(G)$ there
is a unique vertex $u\in V(F)$ with $v\in B_{u}$.

  * •

For any non-leaf $u$ of $F$, its bag $B_{u}$ contains precisely one vertex.

  * •

For any leaf $u$ of $F$, the graph $G[B_{u}]$ is connected and
$G[B_{u}]\in\mathcal{G}$.

  * •

For any edge $uv$ in $G$, let $s,t\in V(F)$ be the vertices such that $u\in
B_{s}$ and $v\in B_{t}$. Then $s$ is an ancestor of $t$, or $t$ is an ancestor
of $s$ in $F$.

We define the height of an elimination forest $F$ to be the maximum number of
edges on a path from the root to a leaf in $F$. One can prove with induction
that this height is equal to the elimination distance we defined earlier.

We will use these elimination forests extensively for our kernel and therefore
introduce some shorthand notation. Let $(F,(B_{u})_{u\in V(F)})$ be a
$\mathcal{G}$-elimination forest. Let $v$ be a vertex in $F$. The _tail_ of
$v$, denoted with $\textnormal{{tail}}(v)$, is defined as the union of $B_{u}$
over all proper ancestors $u$ of $v$. The closed tail $\textnormal{{tail}}[v]$
also includes $B_{v}$. Similarly, $\textnormal{{tree}}(v)$ denotes the union
of $B_{u}$ over all proper descendants $u$ of $v$ and $\textnormal{{tree}}[v]$
also includes $B_{v}$. The subgraph of $G$ induced by all vertices in
$\textnormal{{tree}}[v]$ is denoted with $G_{v}$. We will sometimes slightly
abuse notation and use $G_{v}$ as a vertex set. We use the shorthand
$G_{v}^{+}$ to describe the induced subgraph on the vertices in
$\textnormal{{tree}}[v]\cup\textnormal{{tail}}[v]$.

We will also introduce the notion of _bridge-depth_ as introduced by Bougeret,
Jansen and Sau [8]. A _bridge_ in a graph $G$ is an edge whose removal
increases the number of connected components of $G$. The concept of bridge-
depth now allows us to delete a set of vertices $S$ as long as $G[S]$ is
connected and each edge in $G[S]$ is a bridge in $G$. Such a structure $G[S]$
is called a _tree of bridges_. Observe that a single vertex is always a tree
of bridges.

######  Definition 3 (Bridge-depth).

Let $G$ be a graph. The bridge-depth of $G$ is defined as

$\textnormal{{bd}}(G)=\begin{cases}0&\text{if $G$ is the empty graph,}\\\
\displaystyle\max_{G^{\prime}\in\textnormal{{cc}}(G)}\textnormal{{bd}}(G^{\prime})&\text{if
$\lvert\textnormal{{cc}}(G)\rvert>1$,}\\\
\displaystyle\min_{\begin{subarray}{c}S\subseteq V(G):\\\ \text{$G[S]$ is a
tree of bridges}\end{subarray}}\textnormal{{bd}}(G-S)+1&\text{otherwise.}\\\
\end{cases}$

Cf. [8] for equivalent definitions. Lastly, we sometimes use the more common
concept of _treewidth_ which can be defined using a _tree decomposition_.

######  Definition 4 (Tree decomposition).

Let $G$ be a graph. A tree decomposition of $G$ is a tuple $(R,(B_{u})_{u\in
V(R)})$ where $R$ is a rooted tree and where each node $u\in V(R)$ has a bag
$B_{u}\subseteq V(G)$ with the following properties:

  * •

For every vertex $v\in V(G)$, there exists a node $u\in V(R)$ with $v\in
B_{u}$.

  * •

For every edge $vw\in E(G)$, there exists a node $u\in V(R)$ with
$\\{v,w\\}\subseteq B_{u}$.

  * •

For every vertex $u\in V(G)$, the subgraph of $R$ induced by all vertices
whose bag contains $u$ is a tree.

For $u\in V(R)$ in the setting above, we let $G_{u}$ be the subgraph of $G$
induced by the union of $B_{v}$ over all descendants $v$ of $u$ in the rooted
tree $R$, i.e.

$G_{u}=G\left[\bigcup_{v\in V(R_{u})}B_{v}\right].$

The _width_ of a tree decomposition is defined as the size of its largest bag
minus 1. The _treewidth_ of a graph $G$, denoted with $\textnormal{{tw}}(G)$,
can now be defined as the minimum width over all tree decompositions of $G$.
We mention some useful properties of these concepts in Proposition 1.

######  Proposition 1.

Let $G$ be a graph with $\mathcal{G}_{F}$-elimination forest
$\left(F,(B_{u})_{u\in V(F)}\right)$ and let $\eta$ be an integer such that
$\textnormal{{ed}}_{\mathcal{G}_{F}}(G)\leq\eta$. Let $X$ be a minimum
feedback vertex set in $G$ and let $v$ be a leaf in $F$. Then the following
claims hold.

  1. 1.

$\textnormal{{tw}}(G)\leq\textnormal{{bd}}(G)\leq\textnormal{{ed}}_{\mathcal{G}_{F}}(G)+1$.

  2. 2.

$X$ contains at most $\eta$ vertices from $B_{v}$.

  3. 3.

If there exists a path in $G$ from a vertex in $B_{v}$ to a vertex outside
$B_{v}$, then this path contains a vertex in $\textnormal{{tail}}(v)$.

  4. 4.

Let $u\in V(F)$, then $u$ has at most $\eta$ children $c$ where $X\cap G_{c}$
is not a minimum feedback vertex set in $G_{c}$.

###### Proof.

Proof of 1. Observe that a single vertex is also a tree of bridges. One can
therefore derive that
$\textnormal{{bd}}(G)\leq\textnormal{{ed}}_{\mathcal{G}_{F}}(G)+1$. There is a
difference of one, since a forest has elimination distance 0 to a forest while
its bridgedepth is 1. Besides, it is known that
$\textnormal{{tw}}(G)\leq\textnormal{{bd}}(G)$ for any graph $G$ [8,
Proposition 3.2], thereby concluding the proof.

Proof of 2. Suppose towards a contradiction that $X$ is a minimum feedback
vertex set in $G$, but $\lvert B_{v}\cap X\rvert>\eta$. We claim that
$X^{\prime}\coloneqq(X\setminus B_{v})\cup\textnormal{{tail}}(v)$ is a
feedback vertex set in $G$ of smaller size. Since
$\lvert\textnormal{{tail}}(v)\rvert\leq\eta$, it follows that $\lvert
X^{\prime}\rvert<\lvert X\rvert$. Furthermore, suppose towards a contradiction
that $X^{\prime}$ is not a feedback vertex set, then it contains some cycle
disjoint from $\textnormal{{tail}}(v)$. However, then this cycle must also be
disjoint from $B_{v}$, as $G[B_{v}]$ is a forest and
$N(B_{v})\subseteq\textnormal{{tail}}(v)$ which are all in $X^{\prime}$.
Therefore, this cycle must also be contained in $G-X$ which is a contradiction
with $X$ being a feedback vertex set. We conclude that any minimum feedback
vertex set contains at most $\eta$ vertices from $B_{v}$.

Proof of 3. If there exists path from a vertex in $B_{v}$ to a vertex outside
$B_{v}$, then there also exists an edge between a vertex in $B_{v}$ to a
vertex outside $B_{v}$. By definition of an elimination forest and since $v$
is a leaf, this edge has an endpoint in the bag of a proper ancestor of $v$,
so it is in $\textnormal{{tail}}(v)$.

Proof of 4. Let $C$ denote the set of children of $u$ and let
$C^{\prime}\subseteq C$ be those children $w$ where $X\cap G_{w}$ is not a
minimum feedback vertex set in $G_{w}$. Assume towards a contradiction that
$\lvert C^{\prime}\rvert>\eta$, then we are going to construct a feedback
vertex set with strictly fewer vertices. For all children $w\in C^{\prime}$,
let $X^{\prime}_{w}$ be a minimum feedback vertex set in $G_{w}$. We now claim
that

$X^{\prime}\coloneqq\left(X\setminus\bigcup_{w\in C^{\prime}}(X\cap
G_{w})\right)\cup\textnormal{{tail}}[u]\cup\bigcup_{w\in
C^{\prime}}X^{\prime}_{w}$

is a feedback vertex set in $G$ with less vertices than $X$. Since $\lvert
X\cap G_{w}\rvert>\lvert X^{\prime}_{w}\rvert$ for each $w\in C^{\prime}$,
$\lvert C^{\prime}\rvert>\eta$ and
$\lvert\textnormal{{tail}}[u]\rvert\leq\eta$, it follows that $\lvert
X^{\prime}\rvert<\lvert X\rvert-\eta+\eta=\lvert X\rvert$.

Observe that any cycle that does not contain vertices in $G_{w}$ for some
child $w\in C^{\prime}$ must be broken by $X^{\prime}$, as no vertex from this
cycle was removed from $X$ while $X$ is a feedback vertex set. Similarly, any
cycle that only contains vertices in $G_{w}$ for some $w\in C^{\prime}$ must
be broken by $Y$, because $X^{\prime}_{w}$ is a feedback vertex set in
$G_{w}$. Any remaining cycle in $G-X^{\prime}$ therefore must contain a vertex
in $G_{w}$ for some $w\in C^{\prime}$ and a vertex outside this subgraph. By
Proposition 1.3, any path in this component between a vertex in $G_{w}$ and a
vertex outside $G_{w}$ must contain a vertex from
$\textnormal{{tail}}(w)=\textnormal{{tail}}[u]$. This implies directly that
also any cycle of the last category must be broken by $X^{\prime}$. We can
conclude that $X^{\prime}$ is a feedback vertex set with strictly fewer
vertices than $X$, thereby contradicting that $X$ is a minimum feedback vertex
set. ∎

##  3 Kernelization upper bounds

We present a kernelization algorithm for Feedback Vertex Set in the deletion
distance to a graph of constant elimination distance to a forest. The
structure follows the kernelization algorithm for the generalized
$\mathcal{F}$-Minor Free Deletion problem parameterized by deletion distance
to a graph of constant treedepth, as presented by Jansen and Pieterse [33,
Lemma 3]. The proof of their algorithm requires a lemma on labeled minors.
Since we restrict ourselves to the feedback vertex set problem, our
reformulation in Lemma 1 in the introduction suffices for our purposes. We
repeat and prove this formulation in Section 3.2 and describe the
kernelization algorithm in Section 3.3. We first need to address some
preliminaries.

###  3.1 Additional preliminaries for Section 3

Let $G$ be a graph and $X\subseteq V(G)$. For our kernel, it will be important
to bound the number of relevant components of $G-X$ when $X$ is a modulator to
a graph with constant elimination distance to a forest. This will be done by
characterizing how a component $C\in\textnormal{{cc}}(G-X)$ is connected to
$X$. To this end, we define the following notation.

######  Definition 5 ($\mathcal{S}_{G}$ and $\mathcal{T}_{G}$).

Let $G$ be a graph with $X\subseteq V(G)$ and $C\in\textnormal{{cc}}(G-X)$.
Then

$\displaystyle\mathcal{S}_{G}(C,X)\coloneqq\\{v\in V(C)\;|\;\lvert
N_{G}(v)\cap X\rvert\geq 2\\},$
$\displaystyle\mathcal{T}_{G}(C,X)\coloneqq\\{v\in V(C)\;|\;\lvert
N_{G}(v)\cap X\rvert=1\\}.$

These sets characterize how $C$ is connected to the remainder of $G$. The
vertices in $\mathcal{S}_{G}(C,X)$ are those vertices in $C$ with at least two
neighbors in $X$, while the vertices in $\mathcal{T}_{G}(C,X)$ are those with
exactly one neighbor. We will often use these sets in the context of a
feedback vertex set missing vertices from $\mathcal{S}_{G}(C,X)$ or leaving a
pair in $\mathcal{T}_{G}(C,X)$ connected. We therefore use the notation with
$\mathcal{S}$ and $\mathcal{T}$ in analogy with sets $S$ and $T$ in the
formulation of Lemma 1. The following proposition presents such a relation
between these sets and feedback vertex sets. Recall that we say that a vertex
set $X$ separates a vertex set $T$ in a graph $G$ if each connected component
of $G-X$ contains at most one vertex from $T$.

######  Proposition 2.

Let $G$ be a graph, $X\subseteq V(G)$ and $C^{*}\in\textnormal{{cc}}(G-X)$.
Define $\widehat{G}=G-V(C^{*})$. Let $\widehat{Y}$ be a feedback vertex set in
$\widehat{G}$ and let $Y^{*}$ be a feedback vertex set in $C^{*}$. Define
$X_{0}=X\setminus\widehat{Y}$. If $Y^{*}$ contains
$\mathcal{S}_{G}(C^{*},X_{0})$ and separates $\mathcal{T}_{G}(C^{*},X_{0})$,
then $\widehat{Y}\cup Y^{*}$ is a feedback vertex set in $G$.

One should observe that this statement is slightly stronger than requiring
that $Y^{*}$ contains $\mathcal{S}_{G}(C^{*},X)$ and separates
$\mathcal{T}_{G}(C^{*},X)$. We will rely on our weakened assumption when
applying Proposition 2.

###### Proof of Proposition 2.

Assume towards a contradiction that $\widehat{Y}\cup Y^{*}$ is not a feedback
vertex set in $G$. Then observe that any cycle must contain vertices both from
$C^{*}$ and from $\widehat{G}$, since any other cycle is broken trivially by
either $\widehat{Y}$ or $Y^{*}$. This implies that there exists a path of at
least two vertices in $C^{*}-Y^{*}$ whose endpoints have a neighbor in
$X_{0}$: the path cannot contain only one vertex, since such a vertex would
have two neighbors in $X$, while $\mathcal{S}_{G}(C^{*},X_{0})$ is included in
$Y^{*}$. Therefore, the path has length at least one and both endpoints are in
$\mathcal{T}_{G}(C^{*},X_{0})$. However, then a pair of vertices in
$\mathcal{T}_{G}(C^{*},X_{0})$ is connected in $C^{*}-Y^{*}$, reaching a
contradiction with the assumption that $Y^{*}$ separates
$\mathcal{T}_{G}(C^{*},X_{0})$. It follows that $G-(Y^{*}\cup\widehat{Y})$ is
acyclic and that $Y^{*}\cup\widehat{Y}$ is a feedback vertex set in $G$. ∎

The following proposition explains a property of acyclic graphs which is
useful in the context of feedback vertex sets.

######  Proposition 3.

Let $G$ be an acyclic graph with $X\subseteq V(G)$ and let
$\mathcal{C}=\textnormal{{cc}}(G-X)$. Let $X^{*}\subseteq X$. There are at
most $\lvert X^{*}\rvert-1$ components $C\in\mathcal{C}$ for which there exist
distinct $u,v\in X^{*}$ such that some $u$–$v$ path contains a vertex in $C$.

###### Proof.

Assume towards a contradiction that there exist $\lvert X^{*}\rvert$ of these
components. For such a component $C$, let $P_{C}$ be a minimal path that has
its endpoints in $X^{*}$ while it also contains a vertex in $C$. Observe that
such a path contains at least three vertices and notice that the minimality of
the path implies that all vertices other than the endpoints are in $C$. If two
of these paths have the same endpoints, we directly obtain a cycle in $G$
consisting of these two paths. Otherwise, we create an auxiliary graph $H$ on
vertex set $X^{*}$. We add an edge between $z_{1},z_{2}\in V(X^{*})$ if for
some component $C$ the path $P_{C}$ has endpoints $z_{1}$ and $z_{2}$. Since
we add $\lvert X^{*}\rvert$ unique edges to a graph of at most $\lvert
X^{*}\rvert$ vertices, $H$ contains a cycle. Now consider the cyclic walk in
$G$ traversing all paths corresponding to the edges in the cycle in $H$. We
claim that each vertex occurs only once in this walk. Observe that no vertex
in $X^{*}$ occurs twice, as only the endpoints of each path corresponding to a
child are in $Z$. Furthermore, a vertex outside $X^{*}$ cannot occur on
multiple paths since those paths contain vertices from different components.
Therefore all vertices are unique in the walk, so we obtain a cycle in $G$
which contradicts it being acyclic. We conclude that there exist at most
$\lvert X^{*}\rvert-1$ of these components. ∎

A relation between Proposition 3, feedback vertex sets and the earlier defined
functions $\mathcal{S}$ and $\mathcal{T}$ is described in Proposition 4.

######  Proposition 4.

Let $G$ be a graph, $X\subseteq V(G)$ and
$\mathcal{C}=\textnormal{{cc}}(G-X)$. Let $Y$ be a feedback vertex set in $G$
and let $X^{*}\subseteq X\setminus Y$. Then there are at most $\lvert
X^{*}\rvert-1$ components $C\in\mathcal{C}$ for which $Y\cap V(C)$ misses a
vertex in $\mathcal{S}_{G}(C,X^{*})$ or leaves a pair of vertices in
$\mathcal{T}_{G}(C,X^{*})$ connected in $C-Y$.

###### Proof.

Let $\mathcal{C}^{\prime}$ denote the set of all components $C\in\mathcal{C}$
for which $Y\cap V(C)$ misses a vertex in $\mathcal{S}_{G}(C,X^{*})$ or leaves
a pair of vertices in $\mathcal{T}_{G}(C,X^{*})$ connected in $C-Y$. Observe
that for none of these components $C$, the graph $C-Y$ contains a path of
length one or more where both endpoints are adjacent to the same vertex $u\in
X^{*}$ in $G-Y$, as this contradicts $Y$ being a feedback vertex set.
Therefore for each $C\in\mathcal{C}^{\prime}$, there exists a path in $G-Y$
containing a vertex in $C$ such that both endpoints are distinct vertices from
$X^{*}$. By applying Proposition 3, we now obtain the required bound on
$\mathcal{C}^{\prime}$. ∎

We will also use the following lemma on the time complexity of determining
minimum feedback vertex sets in a graph of bounded elimination distance to a
forest. We should note that both results can also be derived from Courcelle’s
theorem as explained by Jansen and Pieterse in the context of graphs of
bounded treedepth [33].

######  Lemma 2.

Let $G$ be a graph and $\eta$ an integer such that
$\textnormal{{ed}}_{\mathcal{G}_{F}}(G)\leq\eta$. Let $S,T\subseteq V(G)$.
Then one can compute $\textnormal{{fvs}}(G)$ in time
$n^{\mathcal{O}_{\eta}(1)}$. Furthermore, one can determine whether there
exists a minimum feedback vertex set in $G$ that contains $S$ and separates
$T$ in time $n^{\mathcal{O}_{\eta}(1)}$.

###### Proof sketch.

As the approach is standard while working out the details would be tedious, we
only sketch the high-level ideas for completeness. Observe that by Proposition
1.1, $G$ also has treewidth at most $\eta+1$ and we can determine a tree
decomposition of width $\eta+1$ in polynomial time for fixed $\eta$ [4]. We
let $\left(R,(B_{u})_{u\in V(R)}\right)$ denote such a tree decomposition. The
size of a minimum feedback vertex set can be obtained with dynamic programming
over this tree decomposition. The subproblem for node $t\in V(R)$ with
$Z\subseteq B_{t}$ and a partition $\mathcal{P}$ of $B_{t}-Z$ can be defined
as the size of a minimum feedback vertex set $Y$ in $G_{t}$, such that

  * •

$Y\cap B_{t}$ equals $Z$.

  * •

Two vertices of $B_{t}$ are in the same set in $\mathcal{P}$ if and only if
they are in the same connected component in $G_{t}-Y$.

Since $\lvert B_{t}\rvert\leq\eta+2$, the number of partitions can be bounded
by $(\eta+2)^{\eta+2}$, which will yield a polynomial running time for
constant $\eta$. We refer to [17, Section 7.3.3] for a description of the
recurrences for these type of problems.

With a minor modification, we can also derive the size of a minimum set of
vertices $Y$ in $G$ such that $Y$ is a feedback vertex set, $Y$ contains $S$
and $Y$ separates $T$ in $G$. Observe that the minimum size of such a set is
equal to the size of a minimum feedback vertex set, if and only if there
exists a minimum feedback vertex set that also contains $S$ and separates $T$.
After removing $S$ from the graph, we use a similar dynamic programming
approach over a tree decomposition. The subproblem for node $t\in V(R)$ with
$Z\subseteq B_{t}$ and a partition $\mathcal{P}$ of $B_{t}-Z$ now also takes a
boolean value for each class of the partition and asks for the minimum size of
a feedback vertex set $Y$ in $G_{t}$ that separates $T\cap V(G_{t})$ such that

  * •

$Y\cap B_{t}$ equals $Z$.

  * •

Two vertices of $B_{t}$ are in the same set in $\mathcal{P}$ if and only if
they are in the same connected component in $G_{t}-Y$.

  * •

A connected component of $G_{t}-Y$ contains no vertices in $T$ if the boolean
value for the corresponding class of the partition is False.

  * •

A connected component of $G_{t}-Y$ contains precisely one vertex in $T$ if the
boolean value for the corresponding class of the partition is True.

When merging two subtrees, we must ensure that a connected component contains
only one vertex in $T$ after merging. We leave the details of the recursion to
the reader. ∎

Lastly, we will use the concept of a _vertex multiway cut_ [2]. Given a graph
$G$ and a set of vertices $T\subseteq V(G)$ (often called the _terminals_),
the minimum vertex multiway cut problem asks for a minimum set $S\subseteq
V(G)$ such that no connected component of $G-S$ contains more than one
terminal. We say that such a set $S$ _separates_ $T$. It is important that
this vertex set $S$ is allowed to intersect the set $T$. Notice that the edge
multiway cut problem is a more common variant, which is for example explained
in detail by Garg, Vazirani and Yannakakis [24]. We will explore a special
case of covering/packing duality on trees regarding these cuts, for which we
use the following definition.

######  Definition 6 ($T$-path).

Let $G$ be a graph and let $T\subseteq V(G)$ be a set of vertices. A
$T$-_path_ is a path in $G$ whose endpoints are two distinct vertices in $T$.

If for a graph $G$ with $T\subseteq V(G)$ there exists a collection of $k$
vertex-disjoint $T$-paths, then any vertex multiway cut of $T$ in $G$ has size
at least $k$. While the converse is not true in general, it does hold on a
tree.

######  Proposition 5.

Let $G$ be a tree and let $T\subseteq V(G)$ be a set of terminals. If
$Z\subseteq V(G)$ is a minimum vertex multiway cut of $T$ with size $k$, i.e.
in $G-Z$ all vertices in $T\setminus Z$ are in different connected components,
then there exists a collection of $k$ vertex-disjoint $T$-paths.

###### Proof.

For a vertex $v$ in a rooted tree, we use $G_{v}$ to denote the subgraph of
$G$ induced by all descendants of $v$, similar to elimination trees. Pick a
root $r$ of the tree arbitrarily. We will assume that $Z$ has the following
property: for any $u\in Z$ (other than the root) with parent $w$, the set
$(Z\setminus\\{u\\})\cup\\{w\\}$ is not a vertex multiway cut of $T$. Observe
that we can construct such a vertex multiway cut greedily from any minimum
vertex multiway cut by repeatedly replacing a vertex by its parent when the
result still separates $T$ in $G$.

We will now use induction on $k$, the size of a minimum vertex multiway cut.
If $k=1$, then observe that $\lvert T\rvert\geq 2$ as otherwise the empty set
suffices to separate $T$. Therefore, we can identify a $T$-path in the tree.
Now suppose that $k>1$ and suppose that the claim holds for any tree with a
minimum vertex multiway cut of size smaller than $k$. Take a tree $G$ that has
a minimum vertex multiway cut $Z$ of size $k$. Find a vertex $u\in Z$ such
that $G_{u}\cap Z=\\{u\\}$, i.e. there are no other vertices from the vertex
multiway cut in the subtree rooted at $u$. Observe that we can always find
such a vertex that is not the root of the tree. Then we can identify a
$T$-path between two terminals in $G_{u}$: replacing $u$ by its parent does
not yield a vertex multiway cut, so there are at least two terminals in
$G_{u}$. Observe that the $T$-path is contained in $G_{u}$ as well. Now let
$G^{\prime}$ be the graph where $G_{u}$ is removed from $G$. Observe that it
is a tree and that a minimum vertex multiway cut has size $k-1$: the set
$Z\setminus\\{u\\}$ is a valid vertex multiway cut on $G^{\prime}$ and if a
smaller vertex multiway cut $Z^{\prime}$ would exist on $G^{\prime}$, then
$Z^{\prime}\cup\\{u\\}$ would have been a smaller vertex multiway cut on $G$.
Therefore, we can apply the induction hypothesis to obtain a collection of
$k-1$ vertex-disjoint $T$-paths in $G^{\prime}$. Together with the $T$-path
that we identified in $G_{u}$, we obtain a collection of $k$ vertex-disjoint
paths in $G$, proving the induction step. ∎

###  3.2 Proof of main lemma

We repeat the formulation of Lemma 1 as stated in the introduction.

######  Lemma 1.

Let $G$ be a connected graph with disjoint vertex sets $S,T\subseteq V(G)$.
Suppose that any minimum feedback vertex set $X$ of $G$ misses some vertex
from $S$ or leaves two vertices from $T$ connected in $G-X$. Then there exist
sets $S^{*}\subseteq S$ and $T^{*}\subseteq T$ whose sizes only depend on the
elimination distance to a forest of $G$, such that any minimum feedback vertex
set $X$ of $G$ misses some vertex from $S^{*}$ or leaves two vertices from
$T^{*}$ connected in $G-X$.

We can split up Lemma 1 into two parts. Lemma 3 will bound the number of
vertices in the $\mathcal{G}_{F}$-elimination tree that contain a vertex in
$S$ or $T$. This part corresponds to the original treedepth formulation in
[33, Lemma 3], but is significantly simplified for our restricted setting.
Lemma 4 bounds the number of vertices in $S$ and $T$ in a bag of the
elimination tree.

######  Lemma 3.

Let $G$ be a connected graph with disjoint vertex sets $S,T\subseteq V(G)$.
Let $\left(R,(B_{u})_{u\in V(R)}\right)$ be a $\mathcal{G}_{F}$-elimination
tree of $G$ of height $\eta$. Suppose that any minimum feedback vertex set $X$
of $G$ misses a vertex from $S$ or leaves two vertices from $T$ connected.
Then this also holds for some subsets $S^{*}\subseteq S$ and $T^{*}\subseteq
T$, such that any vertex in the elimination tree has at most $3\eta\cdot
2^{\eta}$ children $u$ for which $G_{u}$ contains a vertex from $S^{*}$ or
$T^{*}$.

######  Lemma 4.

Let $G$ be a connected graph with disjoint vertex sets $S,T\subseteq V(G)$.
Let $\left(R,(B_{u})_{u\in V(R)}\right)$ be a $\mathcal{G}_{F}$-elimination
tree of $G$ of height $\eta$. Suppose that any minimum feedback vertex set $X$
of $G$ misses a vertex from $S$ or leaves two vertices from $T$ connected.
Then this also holds for some subsets $S^{*}\subseteq S$ and $T^{*}\subseteq
T$, such that for any leaf $u$ in the elimination tree, the set $B_{u}$
contains at most $\eta$ vertices from $S^{*}$ and at most
$\mathcal{O}(\eta^{2})$ from $T^{*}$.

Observe that these two lemmas directly imply Lemma 1.

###### Proof of Lemma 1.

Let $G$ be a graph with vertex sets $S$ and $T$ as stated in Lemma 1 and let
$\left(R,(B_{u})_{u\in V(R)}\right)$ be a $\mathcal{G}_{F}$-elimination tree
of $G$. We can first apply Lemma 3 to obtain sets $S^{\prime}$ and
$T^{\prime}$ satisfying the guarantee of that lemma: for each vertex in the
elimination tree $R$, we can bound the number of children $u$ for which
$B_{u}$ contains a vertex in $S^{\prime}$ or $T^{\prime}$. Now define subgraph
$R^{\prime}$ of elimination tree $R$ to be the induced subgraph of $R$ by
precisely those vertices $u\in V(R)$ for which $G_{u}$ contains some vertex in
$S^{\prime}$ or $T^{\prime}$. If $R^{\prime}$ is the empty graph, then
$S^{\prime}$ and $T^{\prime}$ are empty, thereby directly implying Lemma 1.
Otherwise, $R^{\prime}$ is still a rooted tree with height at most $\eta$. By
Lemma 3, each vertex in this subtree has at most $3\eta\cdot 2^{\eta}$
children. Since the height of the tree is at most $\eta$, there are at most
$(3\eta\cdot 2^{\eta})^{\eta}$ vertices in each layer of $R^{\prime}$, thereby
bounding the number of vertices in $u\in V(R)$ for which $B_{u}$ contains a
labeled vertex. However, for leaves $u$ of the elimination tree, there is no
bound on the number of vertices in $B_{u}\cap(S^{\prime}\cup T^{\prime})$ yet.
By applying Lemma 4 now on graph $G$ and sets $S^{\prime}$ and $T^{\prime}$,
we obtain sets $S^{*}\subseteq S^{\prime}$ and $T^{*}\subseteq T^{\prime}$
such that for each vertex $u$ in elimination tree $R$, the number of vertices
in $B_{u}\cap(S^{*}\cup T^{*})$ is bounded by a function of $\eta$. By
bounding the total number of labeled vertices by a function of $\eta$, this
concludes the proof of Lemma 1. ∎

We now prove Lemma 3 and Lemma 4.

###### Proof of Lemma 3.

In analogy to the original formulation in [33], a _labeled vertex_ is a vertex
in $S$ or $T$. When we remove a label from a vertex, we remove the vertex from
$S$ and $T$ while the vertex remains in the graph. Suppose that we pick
$S^{*}$ and $T^{*}$ such that no minimum feedback vertex set contains $S^{*}$
and separates $T^{*}$, while the latter property does not hold for any other
pair of sets $S^{\prime},T^{\prime}$ with $S^{\prime}\subseteq S^{*}$ and
$T^{\prime}\subseteq T^{*}$. We claim that for such sets $S^{*}$ and $T^{*}$,
any vertex in the elimination tree $R$ has at most $3\eta\cdot 2^{\eta}$
children $u$ for which $G_{u}$ contains a labeled vertex. We will also refer
to the set $T^{*}$ as the set of terminals.

Assume towards a contradiction that vertex $v$ has more child subtrees with
labels. Let these children be $c_{1},\dots,c_{\ell}$. For each of these
children $c_{i}$, there exists a minimum feedback vertex set $X_{i}$ in $G$
that witnesses the fact that the labels cannot be removed from $G_{c_{i}}$.
This set $X_{i}$ will therefore miss a vertex in $S^{*}\cap G_{c_{i}}$ or
leave a vertex in $T^{*}\cap G_{c_{i}}$ connected to some other vertex in
$T^{*}$, while $X_{i}$ contains all vertices in $S^{*}\setminus G_{c_{i}}$ and
separates all vertices in $T^{*}\setminus G_{c_{i}}$. Define
$Z_{i}\coloneqq\textnormal{{tail}}[v]\setminus X_{i}$.

Now fix a set $Z\subseteq\textnormal{{tail}}[v]$. We will bound the number of
children $c_{i}$ for which $Z_{i}=Z$ by $3\eta$. Suppose towards a
contradiction that there are $3\eta+1$ of these children. Let $C$ be the set
containing these vertices. Pick some child $c_{j}\in C$ and observe the
following.

  * •

By Proposition 1.4, there are at most $\eta$ children $c_{i}\in C$ where
$X_{j}\cap G_{c_{i}}$ is not a minimum feedback vertex set in $G_{c_{i}}$.

  * •

There are at most $\eta$ children $c_{i}\in C$ with $i\neq j$ such that a
terminal in $G_{c_{i}}$ is connected to a vertex in $Z$ in
$G^{+}_{c_{i}}-X_{j}$, i.e. (recall the notation in Section 2.1) in the
induced subgraph on the remaining vertices in the subtree and tail of $c_{i}$.
Otherwise, two children other than $c_{j}$ have a terminal connected to the
same vertex in $Z$, while $X_{j}$ separates all terminals outside $G_{c_{j}}$.

  * •

There are at most $\eta-1$ children $c_{i}\in C$ such that in
$G_{c_{i}}^{+}-X_{j}$, there exists a path between distinct vertices in $Z$
that uses some vertex in $G_{c_{i}}$. Otherwise, we claim that we can directly
construct a cycle in $G-X_{j}$. Consider for example the auxiliary
(multi)graph on vertex set $Z$ which contains, for each child $c_{i}\in C$ for
which $G_{c_{i}}^{+}-X_{j}$ contains such a path, say between $z_{1},z_{2}\in
Z$, one edge $z_{1}z_{2}$. This auxiliary graph contains a cycle since it has
too many edges to be acyclic, which implies that there exists a cycle in
$G-X_{j}$.

Pick a child $c_{k}\in C$ which is neither $c_{j}$ nor in the list of
$3\eta-1$ children above. As $\lvert C\rvert>3\eta$, such a vertex exists. By
the first item above, we can deduce that $X_{j}\cap G_{c_{k}}$ is a minimum
feedback vertex set in $G_{c_{k}}$. Besides, this set contains $S^{*}\cap
G_{c_{k}}$, it separates all terminals in $T^{*}\cap G_{c_{k}}$, and it
separates $T^{*}\cap G_{c_{k}}$ from $Z$. Furthermore, no path exists in
$G_{c_{k}}^{+}-X_{j}$ that connects two vertices in $Z$ and also contains some
vertex in $G_{c_{k}}$.

######  Claim.

The set $X^{\prime}\coloneqq(X_{k}\setminus G_{c_{k}})\cup(X_{j}\cap
G_{c_{k}})$ is a minimum feedback vertex set in $G$ which contains $S^{*}$ and
separates $T^{*}$.

###### Proof.

First, observe that any cycle that is not trivially broken must contain
vertices both in $G_{c_{k}}$ and outside $G_{c_{k}}$. However, when such a
cycle leaves $G_{c_{k}}$, it must enter $Z$. This cycle cannot contain only
one vertex in $Z$, as it would then also be a cycle in $G_{c_{k}}^{+}-X_{j}$.
As no pair of vertices in $Z$ is connected by a path containing some vertex in
$G_{c_{k}}$, such a cycle cannot exist at all. Since $X_{j}\cap G_{c_{k}}$ is
a minimum feedback vertex set in $G_{c_{k}}$, it follows that $X^{\prime}$
must be a minimum feedback vertex set in $G$.

Furthermore, $X_{j}\cap G_{c_{k}}$ contains $S^{*}\cap G_{c_{k}}$ and
separates $T^{*}\cap G_{c_{k}}$. As $X_{k}\setminus G_{c_{k}}$ does the same
for the remainder of $S^{*}$ and $T^{*}$, we only need to verify that no
terminal in $G_{c_{k}}$ is connected to a terminal outside $G_{c_{k}}$.
Because $T^{*}\cap G_{c_{k}}$ is also separated from $\textnormal{{tail}}[v]$,
this cannot happen. Therefore, $X^{\prime}$ is a minimum feedback vertex set
containing $S^{*}$ and separating $T^{*}$. ∎

Claim 3.2 contradicts that any minimum feedback vertex set in $G$ misses a
vertex in $S^{*}$ or leaves two vertices in $T^{*}$ connected. We conclude
that there are at most $3\eta$ children $c_{i}$ of $v$ for which a witnessing
minimum feedback vertex set has $Z_{i}=Z$. As there are at most $2^{\eta}$
subsets of $\textnormal{{tail}}[v]$ for any non-leaf $v$, this leads to the
bound of at most $3\eta\cdot 2^{\eta}$ children for which the labels cannot be
removed. ∎

It remains to prove Lemma 4.

###### Proof of Lemma 4.

Pick some leaf $v$ of elimination tree $R$, for which we want to ensure that
there are $\mathcal{O}(\eta^{2})$ vertices with labels among vertices in
$Y\coloneqq B_{v}$. Define $S_{Y}\coloneqq S\cap Y$ and $T_{Y}\coloneqq T\cap
Y$. Our goal is to obtain subsets $S_{Y}^{*}\subseteq S_{Y}$ and
$T_{Y}^{*}\subseteq T_{Y}$ whose sizes are $\mathcal{O}(\eta^{2})$, such that
every minimum feedback vertex set misses a vertex from
$S_{Y}^{*}\cup(S\setminus Y)$ or leaves a pair of terminals in
$T_{Y}^{*}\cup(T\setminus Y)$ connected. By applying this operation to all
leaves of the elimination tree, we obtain the sets promised by Lemma 4.

The construction of $S_{Y}^{*}$ is straightforward. If $\lvert
S_{Y}\rvert>\eta+1$, we let $S_{Y}^{*}$ be an arbitrary subset of $S_{Y}$ of
size $\eta+1$. Otherwise, $S_{Y}^{*}=S_{Y}$.

######  Claim.

Let $X$ be a minimum feedback vertex set in $G$. If $X$ misses a vertex in
$S$, then it also misses a vertex in $S_{Y}^{*}\cup(S\setminus Y)$.

###### Proof.

If $X$ misses a vertex in $S\setminus Y$, then the implication is trivial.
Therefore assume $X$ misses a vertex in $S_{Y}$. If this vertex is not in
$S_{Y}^{*}$, then $\lvert S_{Y}^{*}\rvert=\eta+1$ by construction. By
Proposition 1.2, we know that $\lvert X\cap S_{Y}^{*}\rvert\leq\eta$ so $X$
misses a vertex in $S_{Y}^{*}$. ∎

For the construction of $T_{Y}^{*}$ we distinguish two cases. First, we assume
that $T_{Y}$ cannot be separated with $\eta$ vertices in $G[Y]$ and make the
following observation.

######  Proposition 6.

Let $G$ be a tree and $T\subseteq V(G)$. If $T$ cannot be separated with
$\eta$ vertices, then there exist $\eta+1$ vertex-disjoint paths whose
endpoints are distinct vertices in $T$.

###### Proof.

Let $Z$ be a minimum vertex multiway cut of $T$ in $G$, then $\lvert
Z\rvert\geq\eta+1$. It remains to apply Proposition 5 to obtain $\eta+1$
vertex-disjoint paths whose endpoints are distinct vertices in $T$. ∎

We define $T_{Y}^{*}$ by taking the $2\eta+2$ endpoints of the paths
guaranteed by Proposition 6. Observe that these vertices are all in $T_{Y}$.

######  Claim.

Suppose that $T_{Y}$ cannot be separated with $\eta$ vertices in $G[Y]$. Let
$X$ be a minimum feedback vertex set in $G$. Then $X$ leaves two vertices in
$T_{Y}^{*}$ connected.

###### Proof.

By Proposition 1.2, $X$ can only intersect $\eta$ of the $\eta+1$ vertex-
disjoint paths that were obtained through Proposition 6. Therefore, at least
one path is disjoint from $X$, so its endpoints in $T_{Y}^{*}$ are connected
in $G-X$. ∎

It remains to consider the case where $T_{Y}$ can be separated with $\eta$
vertices. Let $Z$ be a vertex multiway cut of $T_{Y}$ in $G[Y]$ with $\lvert
Z\rvert\leq\eta$ and let $\mathcal{C}\coloneqq\textnormal{{cc}}(G[Y]-Z)$.
Observe that each of these connected components is a tree with at most one
vertex in $T_{Y}$. Let $\mathcal{C}_{T}\subseteq\mathcal{C}$ be the set of
components that contain a vertex in $T_{Y}$. We are now going to mark
components. For each $z\in Z$, mark $\eta+2$ components in $\mathcal{C}_{T}$
that are adjacent to $z$ in $G[Y]$, or all if there are fewer. Similarly, for
each $u\in\textnormal{{tail}}(v)$ we mark up to $\eta+2$ components in
$\mathcal{C}_{T}$ that are adjacent to $v$ in $G_{v}^{+}$. Then we define
$T_{Y}^{*}$ to be the union of all vertices in $T_{Y}$ in the marked
components, together with $Z\cap T_{Y}$. These are at most
$\eta(\eta+2)+\eta(\eta+2)+\eta=\mathcal{O}(\eta^{2})$ vertices.

######  Claim.

Suppose that $T_{Y}$ can be separated with $\eta$ vertices in $G[Y]$. Let $X$
be a minimum feedback vertex set in $G$ and suppose that $X$ leaves two
vertices in $T$ connected. Then $X$ also leaves two vertices in
$T_{Y}^{*}\cup(T\setminus Y)$ connected.

###### Proof.

Let $Z$ be the vertex multiway cut used in the construction of $T_{Y}^{*}$ and
let $t_{1},t_{2}\in T$ be two terminals that are connected in $G-X$. If they
are both in $T_{Y}^{*}\cup(T\setminus Y)$, then the implication is trivial, so
assume that $t_{1}\in T_{Y}$ but not in $T_{Y}^{*}$. Observe that therefore
$t_{1}\not\in Z$. Let $P$ be a path from $t_{1}$ to $t_{2}$ in $G-X$ and let
$z$ be the first vertex on this path that is not in $G[Y]-Z$. We now
distinguish two cases. If $z\in Z$, then observe that $t_{1}$ was in a
component in $\mathcal{C}_{T}$ that was not marked. Then there are $\eta+2$
marked components in $\mathcal{C}_{T}$ adjacent to $z$ in $G[Y]$ of which the
terminals are in $T_{Y}^{*}$. Only $\eta$ of these components can be
intersected by $X$ by Proposition 1.2, so there exists a path between two
terminals in $T_{Y}^{*}$ in $G[Y]$. If $z\not\in Z$, then we obtain that
$z\in\textnormal{{tail}}(v)$ by Proposition 1.3 and the case follows
analogously. ∎

This concludes the construction of the sets $S_{Y}^{*}$ and $T_{Y}^{*}$. If
any minimum feedback vertex set in $G$ misses a vertex in $S$ or leaves a pair
of terminals in $T$ connected, then it also misses a vertex in
$S_{Y}^{*}\cup(S\setminus Y)$ or leaves a pair of terminals in
$T_{Y}^{*}\cup(T\setminus Y)$ connected. By applying this operation to all
leaves of the elimination tree, we obtain the promised sets $S^{*}$ and
$T^{*}$ which concludes the proof of Lemma 4. ∎

With Lemma 3 and Lemma 4 proven, we conclude the proof of Lemma 1: if any
minimum feedback vertex set in a graph $G$ misses a vertex from a set
$S\subseteq V(G)$ or leaves two terminals in a set $T\subseteq V(G)$
connected, then this property also holds for sets $S^{*}\subseteq S$ and
$T^{*}\subseteq T$ whose sizes only depend on
$\textnormal{{ed}}_{\mathcal{G}_{F}}(G)$.

###  3.3 Kernelization algorithm

Our kernel follows the structure of the polynomial kernel for
$\mathcal{F}$-Minor Free Deletion when parameterized by a treedepth-$\eta$
modulator for some integer $\eta$ [33]. Our kernel relies crucially on the
reduction rule specified in Lemma 5, whose correctness relies on Lemma 1.

######  Lemma 5 (Cf. [33, Lemma 6]).

There is a polynomial-time algorithm that, given a graph $G$ with modulator
$X\subseteq V(G)$ such that $\textnormal{{ed}}_{\mathcal{G}_{F}}(G-X)\leq\eta$
for a constant $\eta$, outputs an induced subgraph $G^{\prime}$ of $G$
together with an integer $\Delta$ such that
$\textnormal{{fvs}}(G)=\textnormal{{fvs}}(G^{\prime})+\Delta$ and
$G^{\prime}-X$ has at most $\lvert X\rvert^{\mathcal{O}_{\eta}(1)}$
components.

We can use this reduction rule to obtain a graph $G^{\prime}$ where
$G^{\prime}-X$ has a bounded number of connected components. We can then
identify a set of vertices $Y\subseteq V(G^{\prime}-X)$ with $\lvert
Y\rvert\leq\lvert X\rvert^{\mathcal{O}_{\eta}(1)}$ such that
$\textnormal{{ed}}_{\mathcal{G}_{F}}(G^{\prime}-X-Y)<\eta$. By definition of
elimination distance, every connected component $C$ of $G^{\prime}-X$ contains
a vertex whose removal decreases $\textnormal{{ed}}_{\mathcal{G}_{F}}(C)$. As
we limited the number of connected components by applying Lemma 5, these
vertices constitute a suitable set $Y$. Now observe that $X\cup Y$ is a
modulator to a graph with elimination distance to a forest $\eta-1$ and that
$\lvert X\cup Y\rvert$ is bounded by a polynomial in $\lvert X\rvert$. One can
therefore provide an inductive argument which repeatedly applies Lemma 5 and
increases the modulator such that the elimination distance to a forest of the
remaining graph decreases every iteration. Once we obtain a modulator to a
graph with elimination distance to a forest 1 (which is a forest), we can
apply a known polynomial kernel in the size of a feedback vertex set [27]. We
formalize these ideas in Theorem 3.1.

######  Theorem 3.1.

Let $\eta\geq 0$ be an integer. Let $\mathcal{G}_{\eta}$ be the set of graphs
with elimination distance to a forest at most $\eta$. Then Feedback Vertex Set
admits a polynomial kernel in the size of a $\mathcal{G}_{\eta}$-modulator
$X$.

For our kernel, we will assume that such a $\mathcal{G}_{\eta}$-modulator is
provided together with the input. This has the technical reason that we
otherwise cannot verify efficiently whether such a modulator actually exists.
In other words, we cannot determine efficiently for a graph $G$ with integers
$k$ and $\ell$ whether there exists a feedback vertex set of size $\ell$ and a
$\mathcal{G}_{\eta}$-modulator of size $k$ as the latter is an NP-hard
problem. By providing the modulator $X$ with the parameterized instance, we
only need to verify that $X$ is indeed such a modulator. This can be done
efficiently when $G-X$ has bounded elimination distance to a forest, since
determining elimination distances is fixed parameter tractable in the target
value [11]. In practice, one can determine a $\log(c+1)$-approximation for the
deletion distance to a minor-closed graph family with elimination distance to
a forest bounded by $c$ [25], since the treewidth is bounded as well by
Proposition 1.1. This approximation with an effectively constant approximation
ratio improves the $\lvert X_{\text{OPT}}\rvert\log^{3/2}\lvert
X_{\text{OPT}}\rvert$-approximation which was used in earlier papers [22, 8].
Here, $X_{\text{OPT}}$ denotes a minimum-sized modulator.

###### Proof of Theorem 3.1.

Recall that $X$ is a subset of $V(G)$ such that
$\textnormal{{ed}}_{\mathcal{G}_{F}}(G-X)\leq\eta$. We will prove the theorem
using induction on $\eta$.

If $\eta=0$ then $G-X$ is a forest. It is known that feedback vertex set
admits a quadratic kernel in the size of a solution [17, Section 9.1],
concluding the base case.

If $\eta>0$, we apply Lemma 5 to obtain a graph $G^{\prime}$ and an integer
$\Delta$ such that $G^{\prime}-X$ has at most $\lvert
X\rvert^{\mathcal{O}_{\eta}(1)}$ connected components and
$\textnormal{{fvs}}(G^{\prime})+\Delta=\textnormal{{fvs}}(G)$. Observe that
$G^{\prime}$ and $\Delta$ can be obtained in polynomial time for fixed $\eta$.
We will now extend the modulator $X$ to a modulator $X^{\prime}$ such that
$G^{\prime}-X^{\prime}$ has
$\textnormal{{ed}}_{\mathcal{G}_{F}}(G^{\prime}-X^{\prime})<\eta$. Consider
each connected component $C$ of $G^{\prime}-X$ for which
$\textnormal{{ed}}_{\mathcal{G}_{F}}(C)=\eta$. By definition, for each such
component $C$ there must exist a vertex $v\in V(C)$ such that
$\textnormal{{ed}}_{\mathcal{G}_{F}}(C-\\{v\\})<\eta$. We can find such a
vertex by trying all options for $v$ and determining
$\textnormal{{ed}}_{\mathcal{G}_{F}}(C-\\{v\\})$. This can be done in
polynomial time for constant $\eta$ since determining elimination distances to
minor-closed graph classes is fixed parameter tractable in the target value
[11]. By adding this vertex to $X$ for each considered component $C$, we
obtain a set $X^{\prime}$ whose size is still bounded by a polynomial in
$\lvert X\rvert$ for constant $\eta$ since the number of components to
consider is polynomial in $\lvert X\rvert$. Since each connected component $C$
of $G^{\prime}-X^{\prime}$ has $\textnormal{{ed}}_{\mathcal{G}_{F}}(C)<\eta$,
it follows that
$\textnormal{{ed}}_{\mathcal{G}_{F}}(G^{\prime}-X^{\prime})<\eta$. Then by
induction, the Feedback Vertex Set problem on $G^{\prime}$ admits a polynomial
kernel in the size of $X^{\prime}$, which is a modulator to a graph with
elimination distance to a forest at most $\eta-1$. Since
$\textnormal{{fvs}}(G^{\prime})+\Delta=\textnormal{{fvs}}(G)$ by Lemma 5, we
know that $G^{\prime}$ has a feedback vertex set of size at most $\ell$ if and
only if $G$ has a feedback vertex set of size at most $\ell+\Delta$. This
concludes the induction step. ∎

It remains to prove Lemma 5.

###### Proof of Lemma 5.

Pick $\gamma\in\mathcal{O}_{\eta}(1)$ such that for any graph with elimination
distance to a forest at most $\eta$ and vertex sets $S$ and $T$, Lemma 1
returns subsets $S^{*}\subseteq S$ and $T^{*}\subseteq T$ of size at most
$\gamma$. Define $\tau=\lvert X\rvert+1+3\gamma$ and
$\mathcal{C}=\textnormal{{cc}}(G-X)$.

We are now going to add components from $\mathcal{C}$ to a set
$\mathcal{C}^{\prime}$. We will ensure that the size of $\mathcal{C}^{\prime}$
is polynomial in $\lvert X\rvert$ for constant $\eta$ and use this set to
prove the lemma. Consider each set $X_{0}\subseteq X$ with $\lvert
X_{0}\rvert\leq 3\gamma$. Observe that these are $\mathcal{O}(\lvert
X\rvert^{3\gamma})=\lvert X\rvert^{\mathcal{O}_{\eta}(1)}$ subsets to
consider. For each of these sets $X_{0}\subseteq X$, we do the following for
each component $C\in\mathcal{C}$: we consider the sets $\mathcal{S}(C,X_{0})$
and $\mathcal{T}(C,X_{0})$ as defined in Definition 5. We then determine
whether there exists a minimum feedback vertex set in $C$ containing
$\mathcal{S}(C,X_{0})$ and separating $\mathcal{T}(C,X_{0})$. By Lemma 2, this
can be verified in polynomial time in graphs with bounded elimination distance
to a forest. If there are at most $\tau$ components in $\mathcal{C}$ where
such a minimum feedback vertex set does not exist, then we add all components
to $\mathcal{C}^{\prime}$; otherwise we pick $\tau$ of them. Observe that
$\lvert\mathcal{C}^{\prime}\rvert=\lvert X\rvert^{\mathcal{O}_{\eta}(1)}$,
since we add at most $\tau$ components for each considered subset of $X$.

We now claim the following regarding components that are not in
$\mathcal{C}^{\prime}$.

######  Claim.

For any component $C^{*}\in\mathcal{C}\setminus\mathcal{C}^{\prime}$,
$\textnormal{{fvs}}(G)=\textnormal{{fvs}}(G-V(C^{*}))+\textnormal{{fvs}}(C^{*})$.

###### Proof.

Let $\widehat{G}=G-V(C^{*})$. Let $Y$ be a minimum feedback vertex set in $G$.
Then $Y$ can be split into a feedback vertex set $Y_{1}$ in $\widehat{G}$ and
a feedback vertex set $Y_{2}$ in $C^{*}$. It follows that
$\textnormal{{fvs}}(G)=\lvert Y\rvert=\lvert Y_{1}\rvert+\lvert
Y_{2}\rvert\geq\textnormal{{fvs}}(\widehat{G})+\textnormal{{fvs}}(C^{*})$, and
it remains to prove the other inequality.

Let $\widehat{Y}$ be a minimum feedback vertex set in $\widehat{G}$ and let
$X_{0}=X\setminus\widehat{Y}$. We again consider sets
$\mathcal{S}(C^{*},X_{0})$ and $\mathcal{T}(C^{*},X_{0})$. If there exists a
minimum feedback vertex set $Y^{*}$ in $C^{*}$ that contains
$\mathcal{S}(C^{*},X_{0})$ and separates $\mathcal{T}(C^{*},X_{0})$, then by
Proposition 2, $Y^{*}\cup\widehat{Y}$ is a minimum feedback vertex set in $G$.
It follows that
$\textnormal{{fvs}}(G)\leq\textnormal{{fvs}}(\widehat{G})+\textnormal{{fvs}}(C^{*})$
under these circumstances. Therefore, suppose towards a contradiction that
each minimum feedback vertex set in $C^{*}$ misses a vertex in
$\mathcal{S}(C^{*},X_{0})$ or leaves a pair of vertices in
$\mathcal{T}(C^{*},X_{0})$ connected. Then by Lemma 1, this also holds for
sets $S^{*}\subseteq\mathcal{S}(C^{*},X_{0})$ and
$T^{*}\subseteq\mathcal{T}(C^{*},X_{0})$ whose sizes are bounded by $\gamma$.

Now consider the following set $X^{*}\subseteq X_{0}$: for each vertex in
$S^{*}$, add two arbitrary neighbors in $X_{0}$ to $X^{*}$. For each vertex in
$T^{*}$, add its neighbor in $X_{0}$ to $X^{*}$. Now consider the sets
$\mathcal{S}(C^{*},X^{*})$ and $\mathcal{T}(C^{*},X^{*})$. Observe that
$S^{*}\subseteq\mathcal{S}(C^{*},X^{*})$ and
$T^{*}\subseteq\mathcal{T}(C^{*},X^{*})$. It follows that any minimum feedback
vertex set in $C^{*}$ misses a vertex in $\mathcal{S}(C^{*},X^{*})$ or leaves
a pair of vertices in $\mathcal{T}(C^{*},X^{*})$ connected. Combined with the
fact that $\lvert X^{*}\rvert\leq 3\gamma$, it means that $C^{*}$ could have
been added to $\mathcal{C}^{\prime}$ during its construction when we
considered $X^{*}$ as a subset of $X$. However, the component was not added,
implying that $\mathcal{C}^{\prime}$ contains at least $\tau$ components $C$
where every minimum feedback vertex set misses a vertex from
$\mathcal{S}(C,X^{*})$ or leaves a pair of vertices in $\mathcal{T}(C,X^{*})$
connected. Let $\mathcal{C}^{\prime\prime}$ be the set of these components. By
Proposition 4, there can be at most $3\gamma$ components
$C\in\mathcal{C}^{\prime\prime}$ where $\widehat{Y}\cap V(C)$ misses a vertex
from $\mathcal{S}(C,X^{*})$ or leaves a pair of vertices in
$\mathcal{T}(C,X^{*})$ connected in $C-\widehat{Y}$. Since $\tau=\lvert
X\rvert+1+3\gamma$, there are at least $\lvert X\rvert+1$ components
$C\in\mathcal{C}^{\prime\prime}$ where $\widehat{Y}\cap V(C)$ contains
$\mathcal{S}(C,X^{*})$ and separates $\mathcal{T}(C,X^{*})$, implying that
$\widehat{Y}\cap V(C)$ is not a minimum feedback vertex set in $C$. We will
now construct a different feedback vertex set $\widehat{Y}^{\prime}$ on
$\widehat{G}$:

  * •

For each of the at least $\lvert X\rvert+1$ components
$C\in\mathcal{C}\setminus\\{C^{*}\\}$ where $\widehat{Y}\cap V(C)$ is not a
minimum feedback vertex set of $G[C]$, we add a minimum feedback vertex set in
$C$.

  * •

For every other component $C\in\mathcal{C}\setminus\\{C^{*}\\}$, we take
$\widehat{Y}\cap V(C)$.

  * •

We add $X$ to $\widehat{Y}^{\prime}$.

Observe that $\widehat{Y}^{\prime}$ is a feedback vertex set in $\widehat{G}$:
since $X$ is included in $\widehat{Y}^{\prime}$, any cycle must be contained
in a component in $\mathcal{C}\setminus\\{C^{*}\\}$, but for each of these
components we added a feedback vertex set in $C$ to $\widehat{Y}^{\prime}$.
Furthermore,
$\lvert\widehat{Y}^{\prime}\rvert\leq\lvert\widehat{Y}\rvert-(\lvert
X\rvert+1)+\lvert X\rvert<\lvert\widehat{Y}\rvert$, contradicting the
assumption that $\widehat{Y}$ is a minimum feedback vertex set.

We conclude that there exists a minimum feedback vertex set in $C^{*}$ that
contains $\mathcal{S}(C^{*},X_{0})$ and separates $\mathcal{T}(C^{*},X_{0})$,
proving that
$\textnormal{{fvs}}(G)\leq\textnormal{{fvs}}(\widehat{G})+\textnormal{{fvs}}(C^{*})$
as we saw earlier. ∎

We can now complete the proof of Lemma 5. Let $G^{\prime}$ be the subgraph of
$G$ induced by $X$ and all vertices in components in $\mathcal{C}^{\prime}$.
Observe that the number of components of $G^{\prime}-X$ is polynomial in
$\lvert X\rvert$. Let $\Delta$ be the size of a minimum feedback vertex set in
the subgraph consisting of all components in
$\mathcal{C}\setminus\mathcal{C}^{\prime}$, which we can obtain in polynomial
time by Lemma 2. By applying Claim 3.3 to all components in
$\mathcal{C}\setminus\mathcal{C}^{\prime}$, we conclude that
$\textnormal{{fvs}}(G)=\textnormal{{fvs}}(G^{\prime})+\Delta$. ∎

##  4 Kernelization lower bounds

We first introduce some relevant terminology and its properties.

###  4.1 Additional preliminaries for Section 4

We sometimes slightly abuse the $\mathcal{O}_{\eta}$ notation here and write
$\mathcal{O}_{\mathcal{F}}(f(n))$ for a set of graphs $\mathcal{F}$, rather
than writing the size of the largest graph in $\mathcal{F}$ as subscript. For
a graph $G$ and a set of connected graphs $\mathcal{F}$, we write
$\textnormal{{ed}}_{\neg\mathcal{F}}(G)$ to denote the elimination distance to
an $\mathcal{F}$-minor free graph.

We introduce the notion of a necklace, which turns out to be a crucial
structure.

######  Definition 7.

Let $G$ be a graph and let $\mathcal{F}$ be a collection of connected graphs.
$G$ is an $\mathcal{F}$-_necklace_ of length $t$ if there exists a partition
of $V(G)$ into $S_{1},\dots,S_{t}$ such that

  * •

$G[S_{i}]\in\mathcal{F}$ for each $i\in[t]$ (these subgraphs are the _beads_
of the necklace),

  * •

$G$ has precisely one edge between $S_{i}$ and $S_{i+1}$ for each $i\in[t-1]$,

  * •

$G$ has no edges between any other pair of sets $S_{i}$ and $S_{j}$.

When the length of the necklace is not relevant, we simply speak of an
$\mathcal{F}$-necklace. The following definition specifies a special type of
necklace.

######  Definition 8.

Let $\mathcal{F}$ be a collection of connected graphs. Let $G$ be an
$\mathcal{F}$-necklace of length $t$. We say that $G$ is a _uniform necklace_
if it satisfies two additional conditions.

  * •

There exists a graph $H\in\mathcal{F}$ such that each bead $G[S_{i}]$ is
isomorphic to $H$.

  * •

There exist $x,y\in V(H)$ and graph isomorphisms $f_{i}\colon V(H)\rightarrow
V(G[S_{i}])$ for each bead $G[S_{i}]$, such that for each $i\in[t-1]$, the
edge between $G[S_{i}]$ and $G[S_{i+1}]$ has precisely the endpoints
$f_{i}(x)$ and $f_{i+1}(y)$.

Notice that for a collection of graphs $\mathcal{F}$, we can specify a uniform
necklace uniquely by a graph $H\in\mathcal{F}$, its length $t$ and the two
vertices in $x,y\in V(H)$ indicating the endpoints of the edges between two
consecutive beads. It will be useful to consider all uniform necklaces of
different lengths with this structure. We speak of the _uniform necklace
structure_ $(H,x,y)$ to describe all uniform $\\{H\\}$-necklaces where there
exist isomorphisms as described in Definition 8: for each pair of consecutive
beads $S_{i}$ and $S_{i+1}$ with edge $e$ connecting them, the endpoint of $e$
in $S_{i}$ equals the image of $x$ under the $i$th isomorphism and the
endpoint in $S_{i+1}$ equals the image of $y$ under the $(i+1)$st.

The following proposition explains why we consider this special type of
necklaces.

######  Proposition 7.

Let $\mathcal{F}$ be a finite collection of connected graphs. Let
$\mathcal{G}$ be a minor-closed graph family that contains arbitrarily long
$\mathcal{F}$-necklaces. Then $\mathcal{G}$ also contains arbitrarily long
uniform $\mathcal{F}$-necklaces. Moreover, there exists a graph
$H\in\mathcal{F}$ and vertices $x,y\in V(H)$ such that all uniform necklaces
with structure $(H,x,y)$ are contained in $\mathcal{G}$.

###### Proof.

We first argue that there exists a graph $H\in\mathcal{F}$ such that
$\mathcal{G}$ contains arbitrarily long $\\{H\\}$-necklaces. Observe that if
only a finite number $c$ of beads in necklaces in $\mathcal{G}$ can be
isomorphic to each graph in $\mathcal{F}$, then $\mathcal{G}$ cannot contain
necklaces of length more than $c\cdot\lvert\mathcal{F}\rvert$. It follows that
there exists a graph $H\in\mathcal{F}$ such that $\mathcal{G}$ contains
necklaces where arbitrarily many beads are isomorphic to $H$. If we take such
a necklace, contract all edges in beads which are not isomorphic to $H$ and
then contract the resulting paths between beads sufficiently, we can create
arbitrarily long $\\{H\\}$-necklaces. These are in $\mathcal{G}$ as well since
it is a minor-closed graph family. We can now take an $\\{H\\}$-necklace $G$
of arbitrary length $t$ in $\mathcal{G}$ with beads $G[S_{1}],\dots,G[S_{t}]$.
Let $f_{i}\colon V(H)\to S_{i}$ be a graph isomorphism between $H$ and the
$i$th bead for each $i\in[t]$. Now consider a bead $G[S_{i}]$ with $2\leq
i\leq t-1$ where $u\in S_{i}$ is the endpoint of the edge to $S_{i-1}$ and
$v\in S_{i}$ is the endpoint of the edge to $S_{i+1}$. There are $\lvert
V(H)\rvert$ vertices in $H$ that can be the preimage of $u$ under the $i$th
isomorphism and, similarly, there are $\lvert V(H)\rvert$ options for $v$.
Therefore, by the pigeonhole principle there exist vertices $x,y\in V(H)$ such
that for at least $\lceil\frac{t-2}{\lvert V(H)\rvert^{2}}\rceil$ beads
$G[S_{i}]$, the vertex in $S_{i}$ adjacent with $S_{i-1}$ equals the image of
$x$ under the $i$th isomorphism and the vertex in $S_{i}$ adjacent to
$S_{i+1}$ equals the image of $y$ under that isomorphism. By contracting the
edges within all other beads and by contracting the resulting paths between
beads sufficiently, we obtain a uniform $\mathcal{F}$-necklace of length
$\lceil\frac{t-2}{\lvert V(H)\rvert^{2}}\rceil$ which is contained in
$\mathcal{G}$ as it is minor-closed. By picking $t$ arbitrarily large, we
conclude that $\mathcal{G}$ contains arbitrarily long uniform
$\mathcal{F}$-necklaces.

Furthermore, suppose that for some graph $H$ and vertices $x,y\in V(H)$,
$\mathcal{G}$ does not contain all uniform $\mathcal{F}$-necklaces with
structure $(H,x,y)$. Since $\mathcal{G}$ is minor-closed, this implies that
there exists a constant $c$ bounding the length of all uniform
$\mathcal{F}$-necklaces with structure $(H,x,y)$ in $\mathcal{G}$. Now suppose
towards a contradiction that for no $H\in\mathcal{F}$ and $x,y\in V(H)$,
$\mathcal{G}$ contains all uniform $\mathcal{F}$-necklaces with structure
$(H,x,y)$. As the number of structures is finite for a finite collection of
finite graphs, we can take the maximum of these constants. This constant then
bounds the length of any uniform necklace in $\mathcal{G}$, while we proved
earlier that $\mathcal{G}$ contains arbitrarily long uniform necklaces. We
obtain a contradiction and thereby conclude that there exists an
$H\in\mathcal{F}$ and $x,y\in V(H)$ such that $\mathcal{G}$ contains all
uniform necklaces with structure $(H,x,y)$. ∎

The following observation follows directly from the definitions of a graph
minor.

Let $G$ be a graph and $H$ be a connected graph. If $\phi$ is a minor model of
$H$ in $G$, then the graph $G[\phi(V(H))]$ is connected.

We will often restrict ourselves to necklaces where each graph
$H\in\mathcal{F}$ is _biconnected_ , meaning that $H$ is connected and for any
$v\in V(H)$ the graph $H-\\{v\\}$ is still connected. A _biconnected
component_ of a graph $G$ is a maximal biconnected subgraph of $G$, i.e. it is
a biconnected subgraph of $G$ which is not a proper subgraph of any other
biconnnected subgraph of $G$. The following proposition gives a necessary
condition for a graph to contain a biconnected graph as a minor.

######  Proposition 8.

Let $H$ be a biconnected graph and let $G$ be a graph which contains $H$ as a
minor. Then for any minimal minor model $\phi$ of $H$ in $G$, the graph
$G[\phi(V(H))]$ is biconnected. Furthermore, this graph is a minor of a
biconnected component.

###### Proof.

Suppose that $G$ contains $H$ as a minor and let $\phi$ be a minimal minor
model of $H$ in $G$. Assume towards a contradiction that $G[\phi(V(H))]$ is
not biconnected. Let $v\in\phi(V(H))$ be a vertex such that
$G[\phi(V(H))\setminus\\{v\\}]$ is not connected. Let $u\in V(H)$ be the
vertex such that $v\in\phi(u)$. Suppose that for some component $C$ of the
disconnected graph $G[\phi(V(H))\setminus\\{v\\}]$, its vertex set $V(C)$ is
included in $\phi(u)$. Observe that any edge of $G[\phi(V(H))]$ with precisely
one endpoint in $V(C)$ will have $v$ as its other endpoint, since $C$ is a
component of $G[\phi(V(H))\setminus\\{v\\}]$. It follows that any edge with at
least one endpoint in $C$ is entirely contained in $\phi(u)$ in
$G[\phi(V(H))]$. Now consider the minor model $\phi^{\prime}$ of $H$ in $G$,
defined by

$\phi^{\prime}(w)=\begin{cases}\phi(w)&\text{ if $w\neq u$,}\\\
\phi(w)\setminus V(C)&\text{ if $w=u$.}\\\ \end{cases}$

Then observe that $\phi^{\prime}(V(H))$ is still connected and for any edge
$xy$ in $H$, there still exists an edge between $\phi^{\prime}(x)$ and
$\phi^{\prime}(y)$ in $G[\phi^{\prime}(V(H))]$, since such an edge does not
contain an endpoint in $C$. It follows that $\phi$ is not a minimal minor
model of $H$ in $G$ in this case, so no component $C$ of
$G[\phi(V(H))\setminus\\{v\\}]$ is included in $\phi(u)$. We now claim that
$H-\\{u\\}$ is also not connected. To this end, we will consider the subgraph
of $G[\phi(V(H))]$ where not only $v$ is removed, but the entire set
$\phi(u)$. Observe that $G^{\prime}$ still contains multiple components, since
no component of $G[\phi(V(H))\setminus\\{v\\}]$ is contained in $\phi(u)$. Now
for each $x,y\in V(H)\setminus\\{u\\}$ for which $xy\not\in E(H)$, remove all
edges between a vertex in $\phi(x)$ and a vertex in $\phi(y)$, and contract
all edges between vertices in $\phi(x)$ for each $x\in V(H)\setminus\\{u\\}$.
By definition of a minor model, we obtain the graph $H-\\{u\\}$. However,
after contracting and removing edges in a disconnected graph, the remaining
graph is still disconnected. Thereby $H-\\{u\\}$ is disconnected, so $H$ was
not biconnected. We conclude that for any minimal minor model $\phi$ of $H$ in
$G$, the graph $G[\phi(V(H))]$ is biconnected. It follows directly that
$G[\phi(V(H))]$ is a subgraph (and thereby also a minor) of a biconnected
component of $G$: if it is not a proper subgraph of any biconnected component
of $G$, then it is not a proper subgraph of any biconnected subgraph of $G$.
But then, by definition, $G[\phi(V(H))]$ is a biconnected component of $G$
itself. ∎

Proposition 8 directly implies that if some graph $G$ contains a biconnected
graph $H$ as a minor, then some biconnected component of $G$ contains an
$H$-minor. This provides us with a useful tool for arguing that a necklace
does not contain some biconnected graph as a minor. To this end, observe that
we can characterize the biconnected components of a necklace in the following
way. Notice that we do not require the graphs in $\mathcal{F}$ to be
biconnected here.

Let $\mathcal{F}$ be a collection of connected graphs and let $G$ be an
$\mathcal{F}$-necklace. Then any biconnected component of $G$ with at least
three vertices is a subgraph of a bead.

The observation follows from the fact that for any pair of beads, we can
identify an edge that is used on any path connecting those two beads.
Proposition 8 and Observation 4.1 imply the following result.

######  Lemma 6.

Let $\mathcal{F}$ be a collection of connected graphs and let $G$ be an
$\mathcal{F}$-necklace. Let $\mathcal{H}$ be a collection of biconnected
graphs on at least three vertices. If no graph in $\mathcal{F}$ contains an
$\mathcal{H}$-minor, then $G$ contains no $\mathcal{H}$-minor.

###### Proof.

Assume towards a contradiction that $G$ contains an $H$-minor for some
$H\in\mathcal{H}$. Then by Proposition 8, $G$ has a biconnected component with
an $H$-minor. Since $H$ has at least three vertices, this biconnected
component must have at least three vertices as well. By Observation 4.1, such
a biconnected component is a subgraph of a bead of $G$. We conclude that $G$
has a bead containing an $H$-minor, contradicting that no graph in
$\mathcal{F}$ contains an $\mathcal{H}$-minor. ∎

Lemma 6 argues that it suffices to hit the $\mathcal{H}$-minors in each bead
of a necklace to ensure that a necklace has no $\mathcal{H}$-minors at all. We
will use these ideas when $\mathcal{F}$ is a collection of proper subgraphs of
graphs in $\mathcal{H}$. Lemma 6 also implies the following corollary.

######  Corollary 1.

Let $\mathcal{F}$ be a collection of planar graphs and let $G$ be an
$\mathcal{F}$-necklace. Then $G$ is also planar.

###### Proof.

By Kuratowski’s celebrated theorem, a graph is planar if and only if it
contains no $K_{5}$ and no $K_{3,3}$ minor. Observe that the set
$\mathcal{H}=\\{K_{5},K_{3,3}\\}$ is a set of biconnected graphs on at least
three vertices. Since no graph in $\mathcal{F}$ contains an
$\mathcal{H}$-minor by Kuratowski’s theorem, also $G$ contains no
$\mathcal{H}$-minor by Lemma 6. We conclude that $G$ is planar by Kuratowski’s
theorem. ∎

###  4.2 Proof setup

We repeat the lower bound we aim to prove here as stated in the introduction.

######  Theorem 2.

Let $\mathcal{G}$ be a minor-closed family of graphs and let $\mathcal{F}$ be
a finite set of biconnected planar graphs on at least three vertices. If
$\mathcal{G}$ has unbounded elimination distance to an $\mathcal{F}$-minor
free graph, then $\mathcal{F}$-Minor Free Deletion does not admit a polynomial
kernel in the size of a $\mathcal{G}$-modulator, unless
$\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$.

Notice that when we consider $\mathcal{F}$-Minor Free Deletion for some
collection of graphs $\mathcal{F}$, we can assume that there do not exist
distinct graphs $G,H\in\mathcal{F}$ such that $G$ is a minor of $H$. Our proof
consists of two parts. We first derive the following property, where we say
that a set contains arbitrarily long necklaces if there does not exist a
constant $c$ such that each necklace in the set has length at most $c$.

######  Lemma 7.

Let $\mathcal{F}$ be a finite collection of connected planar graphs. Any
minor-closed graph family $\mathcal{G}$ with unbounded elimination distance to
an $\mathcal{F}$-minor free graph contains arbitrarily long uniform
$\mathcal{F}$-necklaces.

Then we will prove the following lemma by giving a reduction from CNF
Satisfiability parameterized by the number of variables [19].

######  Lemma 8.

Let $\mathcal{F}$ be a finite set of biconnected planar graphs on at least
three vertices and let $\mathcal{G}$ be a minor-closed graph family. If
$\mathcal{G}$ contains arbitrarily long uniform $\mathcal{F}$-necklaces, then
$\mathcal{F}$-Minor Free Deletion does not admit a polynomial kernel in the
size of a $\mathcal{G}$-modulator, unless
$\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$.

Lemma 7 and Lemma 8 together directly imply Theorem 1.2.

###### Proof of Theorem 1.2.

By Lemma 7, graph family $\mathcal{G}$ contains arbitrarily long uniform
$\mathcal{F}$-necklaces. We can therefore apply Lemma 8 to conclude that
$\mathcal{F}$-Minor Free Deletion does not admit a polynomial kernel in the
size of a $\mathcal{G}$-modulator, assuming
$\mathrm{NP}\not\subseteq\mathrm{coNP}/\mathrm{poly}$. ∎

###  4.3 Characterizing graph families with unbounded elimination distance to
an $\mathcal{F}$-minor free graph

We will prove Lemma 7 here. Our proof follows the proof by Bougeret et al.
when they characterize graph families with unbounded bridge-depth [8]. Similar
to their work, we define ${\textnormal{{nm}}}_{\mathcal{F}}(G)$ to be the
length of the longest $\mathcal{F}$-necklace that a graph $G$ contains as a
minor for a family of connected graphs $\mathcal{F}$. Our goal is now to prove
the existence of a small set $X$ such that
${\textnormal{{nm}}}_{\mathcal{F}}(G-X)<{\textnormal{{nm}}}_{\mathcal{F}}(G)$
as described in Lemma 9.

######  Lemma 9.

Let $\mathcal{F}$ be a collection of connected planar graphs. Then there
exists a polynomial function $f_{\mathcal{F}}\colon\mathbb{N}\to\mathbb{N}$
such that for any connected graph $G$ with
${\textnormal{{nm}}}_{\mathcal{F}}(G)=t$, there exists a set $X\subseteq V(G)$
with $\lvert X\rvert\leq f_{\mathcal{F}}(t)$ such that
${\textnormal{{nm}}}_{\mathcal{F}}(G-X)<t$.

Bougeret et al. showed that one can derive a bounding function when the
considered structures satisfy the Erdős-Pósa property [8]. This also is the
case for $\mathcal{F}$-necklaces when the graphs in $\mathcal{F}$ are
connected and planar, so this approach would be suitable for our purposes as
well. To derive a polynomial bound on the size of $X$, we use a different
argument that uses treewidth and grid minors. We start with the following
property of planar graphs.

######  Proposition 9.

Any planar graph $G$ on $n$ vertices is a minor of the $4n\times 4n$ grid.

###### Proof.

We will first modify $G$ by splitting vertices of large degree. We do this to
ensure that each vertex in the modified graph has degree at most 4. For each
vertex $u\in V(G)$ with degree $d(u)>4$, we replace $u$ by a path of $\lfloor
d(u)/2\rfloor$ vertices. Then we connect each neighbor of $u$ to a vertex on
this path, such that the maximum degree of each vertex on this path is 4.
Observe that this is possible since both endpoints of the path can be
connected to three neighbors, while the other vertices can be connected to two
neighbors. Furthermore, notice that we can execute this procedure while
ensuring that the modified graph is planar as well. We let $G^{\prime}$ denote
the modified graph where each vertex has degree at most 4; observe that $G$ is
a minor of this graph.

As a planar graph on $n$ vertices has at most $3n$ edges, the total degree of
$G$ is bounded by $6n$. We can use this to bound the number of vertices in
$G^{\prime}$, since

$\lvert V(G^{\prime})\rvert\leq\sum_{\begin{subarray}{c}u\in V(G):\\\ d(u)\leq
4\end{subarray}}1+\sum_{\begin{subarray}{c}u\in V(G):\\\
d(u)>4\end{subarray}}\lfloor d(u)/2\rfloor\leq n+\sum_{u\in V(G)}d(u)/2\leq
4n.$

Any planar graph on $n$ vertices that each have degree at most 4 can be drawn
on an $n\times n$ grid such that the edges are non-intersecting grid paths
[3]. It follows that there exists such an embedding on a grid with side length
$4n$ for $G^{\prime}$. Notice that $G^{\prime}$ is also a minor of this grid,
so we conclude that also $G$ is a minor. ∎

Together with the Excluded Grid Theorem, this proposition leads to the
following treewidth bound.

######  Lemma 10.

Let $\mathcal{F}$ be a collection of connected planar graphs of at most $n$
vertices each. There exists a polynomial $f\colon\mathbb{N}\to\mathbb{N}$ with
$f(g)=\mathcal{O}(g^{19}\textnormal{poly}\log g)$ such that for any graph $G$
with ${\textnormal{{nm}}}_{\mathcal{F}}(G)=t$, it holds that
$\textnormal{{tw}}(G)<f(4n(t+1))$.

###### Proof.

Let $f$ be the function guaranteed by the Excluded Grid Theorem such that any
graph with treewidth at least $f(g)$ contains the ($g\times g$)-grid as a
minor [16]. Observe that $f(g)=\mathcal{O}(g^{19}\textnormal{poly}\log g)$.
Now suppose towards a contradiction that the treewidth of $G$ is at least
$f(4n(t+1))$. Then by the Excluded Grid Theorem, $G$ contains the grid with
side length $4(n(t+1))$ as a minor. Now observe that an $\mathcal{F}$-necklace
of length $t+1$ has at most $n(t+1)$ vertices when each graph in $\mathcal{F}$
has at most $n$ vertices and observe that, by Corollary 1,
$\mathcal{F}$-necklaces are planar when the graphs in $\mathcal{F}$ are
planar. By Proposition 9, such an $\mathcal{F}$-necklace is therefore a minor
of the grid with side length $4(n(t+1))$. As $G$ contains this grid as a
minor, $G$ also contains an $\mathcal{F}$-necklace of length $t+1$ as a minor,
contradicting that ${\textnormal{{nm}}}_{\mathcal{F}}(G)=t$. We conclude that
$\textnormal{{tw}}(G)<f(4n(t+1))$. ∎

To use this treewidth bound, we need a property similar to [8, Lemma 4.6].

(a) Two minor models of necklaces of length three.

(b) A minor model of a necklace of length four.

Figure 1: Figure 1(a) displays a connected graph where two disjoint minor
models of a $\\{K_{3}\\}$-necklace of length 3 are highlighted. Figure 1(b)
indicates how these necklaces can be combined into a necklace of length 4.

######  Proposition 10.

For any family of connected graphs $\mathcal{F}$ and connected graph $G$ with
${\textnormal{{nm}}}_{\mathcal{F}}(G)>0$, any pair of minor models of
$\mathcal{F}$-necklaces of length ${\textnormal{{nm}}}_{\mathcal{F}}(G)$ in
$G$ must intersect.

###### Proof.

Figure 1 illustrates the main idea of the proof. Define
$t\coloneqq{\textnormal{{nm}}}_{\mathcal{F}}(G)$. Assume towards a
contradiction that two disjoint minor models of an $\mathcal{F}$-necklace of
length $t$ exist. Then there exist pairwise disjoint sets $S_{1},\dots,S_{t}$,
$T_{1},\dots,T_{t}$, such that:

  * •

For each $i\in[t]$, $G[S_{i}]$ and $G[T_{i}]$ are connected and they both
contain an $\mathcal{F}$-minor.

  * •

For each $i\in[t-1]$, there exists an edge between $S_{i}$ and $S_{i+1}$, as
well as an edge between $T_{i}$ and $T_{i+1}$.

Figure 1 illustrates this setting and gives some intuition on how two of those
necklaces can be combined into a longer one. Define
$S\coloneqq\bigcup_{i\in[t]}S_{i}$, $\mathcal{S}=\\{S_{1},\dots,S_{t}\\}$ and
$T$ and $\mathcal{T}$ analogously. Since $G$ is connected, there exists a path
between $S$ and $T$. Consider such a minimal path $P$, so in particular only
its endpoints are in $S\cup T$. Let $S_{i}$ be the set in $\mathcal{S}$
containing the endpoint of $P$ in $S$ and let $T_{j}$ be the set in
$\mathcal{T}$ containing the endpoint of $P$ in $T$. We will now construct an
$\mathcal{F}$-necklace of length at least $t+1$, contradicting that
${\textnormal{{nm}}}_{\mathcal{F}}(G)=t$.

If $i\geq\frac{t+1}{2}$, then start the new $\mathcal{F}$-necklace minor model
with sets $S_{1},\dots,S_{i-1}$. Otherwise, start with $S_{t},\dots,S_{i+1}$.
Observe that also in the latter case, we select at least $t-(i+1)+1\geq
t-\frac{t+1}{2}=\frac{t-1}{2}$ sets. Now modify set $S_{i}$ into a set
$S_{i}^{\prime}$ by including all vertices in $P$ except the vertex in
$T_{j}$. We now include $S_{i}^{\prime}$ in the necklace. Then if
$j\geq\frac{t+1}{2}$, we conclude the $\mathcal{F}$-necklace with sets
$T_{j},\dots,T_{1}$; otherwise with $T_{j},\dots,T_{t}$. Observe that these
are at least $\frac{t+1}{2}$ additional sets. We will now argue that these
sets satisfy the properties of a necklace.

  * •

The sets are pairwise disjoint, since the sets in $\mathcal{S}\cup\mathcal{T}$
are pairwise disjoint and since only one set was modified by adding vertices
not occurring in $\mathcal{S}\cup\mathcal{T}$.

  * •

For each vertex set, the subgraph of $G$ induced by these vertices contains an
$\mathcal{F}$-minor and is connected, since each set is either in
$\mathcal{S}\cup\mathcal{T}$, or was in $\mathcal{S}\cup\mathcal{T}$ before
adding vertices on a path with an endpoint in the set.

  * •

Between any pair of consecutive sets, there exists an edge: the only non-
trivial pair of consecutive sets is formed by $S_{i}^{\prime}$ and set
$T_{j}$. By construction, there exists an edge in $P$ which has one endpoint
in $S_{i}^{\prime}$ and one in $T_{j}$, concluding this case as well.

We conclude that $G$ contains an $\mathcal{F}$-necklace of length at least
$\frac{t-1}{2}+1+\frac{t+1}{2}=t+1$ as a minor, contradicting that
${\textnormal{{nm}}}_{\mathcal{F}}(G)=t$. Therefore $G$ does not contain two
disjoint minor models of an $\mathcal{F}$-necklace of length
${\textnormal{{nm}}}_{\mathcal{F}}(G)$. ∎

Proposition 10 is a generalization of the idea that in any connected graph,
two paths of maximum length must intersect at a vertex. Given a graph $G$ with
a tree decomposition, we can use this property to identify a vertex in the
tree decomposition such that the removal of all vertices in its bag decreases
${\textnormal{{nm}}}_{\mathcal{F}}(G)$. This result is described in Lemma 11.

######  Lemma 11.

Let $\mathcal{F}$ be a collection of connected graphs. Let $G$ be a connected
graph with $\textnormal{{tw}}(G)=w$ and
${\textnormal{{nm}}}_{\mathcal{F}}(G)=t$. Then there exists a set $Z\subseteq
V(G)$ with $\lvert Z\rvert\leq w+1$ such that
${\textnormal{{nm}}}_{\mathcal{F}}(G-Z)<t$.

###### Proof.

Take a tree decomposition $\left(X,(B_{u})_{u\in V(X)}\right)$ of $G$ of width
$w$. Now consider a node $t$ of the decomposition such that $G_{t}$ contains
an $\mathcal{F}$-necklace of length $t$ as a minor, but for none of the
children $c$ of $t$ the graph $G_{c}$ contains such a minor. Observe that such
a node exists, because for the root node $r$, the graph $G_{r}$ contains such
a minor. We now claim that $B_{t}$ hits any minor model of an
$\mathcal{F}$-necklace of length $t$ in $G$. First, notice that by definition
of a tree decomposition, there cannot be an edge between a vertex $u$ in
$G_{t}-B_{t}$ and a vertex $v$ in $G-V(G_{t})$: if such an edge would exist,
then the subtree of the tree decomposition of all bags containing $u$ would
intersect the subtree of all bags containing $v$, implying that $B_{t}$
contains at least one of the vertices. It follows that any minor model of an
$\mathcal{F}$-necklace of length $t$ in $G-B_{t}$ must either be contained in
$G_{t}-B_{t}$ or $G-V(G_{t})$. The first set cannot contain such a minor model
by construction of node $t$. The second set cannot either, as this implies the
existence of two disjoint minor models of an $\mathcal{F}$-necklace of length
$t$ in $G$, while Proposition 10 proves that any two of these models must
intersect. We conclude that $B_{t}$ is a set of at most $w+1$ vertices hitting
all minor models of $\mathcal{F}$-necklaces of length $t$ in $G$. ∎

The proof of Lemma 9 follows directly by combining Lemma 10 and Lemma 11.

###### Proof of Lemma 9.

By Lemma 10, we know that there exists a polynomial $f$ such that
$\textnormal{{tw}}(G)<f(4n(t+1))$. Then by Lemma 11, there exists a set $X$
with $\lvert X\rvert\leq f(4n(t+1))$ where $n$ only depends on $\mathcal{F}$,
as it is the maximum number of vertices in a graph in $\mathcal{F}$. ∎

We are almost in position to prove Lemma 7 now. We will first prove the
following reformulation and then argue how it implies the lemma.

######  Lemma 12 (Cf. [8, Theorem 4.8]).

For any finite collection $\mathcal{F}$ of connected planar graphs, there
exists a polynomial function $g$ such that for any graph $G$,

$\textnormal{{ed}}_{\neg\mathcal{F}}(G)\leq
g({\textnormal{{nm}}}_{\mathcal{F}}(G)).$

###### Proof.

Let $\mathcal{F}$ be a finite collection of connected planar graphs. We will
prove the statement by induction on
${\textnormal{{nm}}}_{\mathcal{F}}(G)+\lvert V(G)\rvert$ for the function $g$
defined by

$g(t)=\sum_{i=1}^{t}f_{\mathcal{F}}(t),$

where $f_{\mathcal{F}}$ denotes the function guaranteed by Lemma 9.

If ${\textnormal{{nm}}}_{\mathcal{F}}(G)=0$, then $G$ does not contain any
$\mathcal{F}$-minor, so $\textnormal{{ed}}_{\neg\mathcal{F}}(G)=0=g(0)$.

Now suppose that ${\textnormal{{nm}}}_{\mathcal{F}}(G)=t>0$ and consider the
case where $G$ is connected. Then by Lemma 9, there exists a set $X\subseteq
V(G)$ with $\lvert X\rvert\leq f_{\mathcal{F}}(t)$ such that
${\textnormal{{nm}}}_{\mathcal{F}}(G-X)<t$. Then for each component
$C\in\textnormal{{cc}}(G-X)$, we know that $C$ is a connected graph with
${\textnormal{{nm}}}_{\mathcal{F}}(C)<t$ and $|V(C)|\leq|V(G)|$, so by
induction $\textnormal{{ed}}_{\neg\mathcal{F}}(C)\leq
g({\textnormal{{nm}}}_{\mathcal{F}}(C))\leq
g({\textnormal{{nm}}}_{\mathcal{F}}(G-X))\leq g(t-1)$. Since this holds for
each component of $G-X$, we obtain by definition that
$\textnormal{{ed}}_{\neg\mathcal{F}}(G-X)=\max_{C\in\textnormal{{cc}}(G-X)}\textnormal{{ed}}_{\neg
F}(C)\leq g(t-1)$. Now observe that
$\textnormal{{ed}}_{\neg\mathcal{F}}(G)\leq\lvert
X\rvert+\textnormal{{ed}}_{\neg\mathcal{F}}(G-X)$. This follows directly from
an inductive proof based on the definition of elimination distance, which
implies that there always exists a vertex whose removal decreases the
elimination distance. This implies that

$\textnormal{{ed}}_{\neg\mathcal{F}}(G)\leq\lvert
X\rvert+\textnormal{{ed}}_{\neg\mathcal{F}}(G-X)\leq
f_{\mathcal{F}}(t)+g(t-1)=g(t).$

The case where $G$ is disconnected is analogous: for each component
$C\in\textnormal{{cc}}(G)$ we have
${\textnormal{{nm}}}_{\mathcal{F}}(C)\leq{\textnormal{{nm}}}_{\mathcal{F}}(G)$
while $\lvert V(C)\rvert<\lvert V(G)\rvert$, so by induction we can bound the
elimination distance to an $\mathcal{F}$-minor free graph of $C$. As the
elimination distance to an $\mathcal{F}$-minor free graph of $G$ is the
maximum of the elimination distance of its connected components, we thereby
bound $\textnormal{{ed}}_{\neg\mathcal{F}}(G)$ as well. ∎

We can now prove Lemma 7. Recall that for a finite collection $\mathcal{F}$ of
connected planar graphs, Lemma 7 states that any minor-closed family of graphs
$\mathcal{G}$ with unbounded elimination distance to an $\mathcal{F}$-minor
free graph contains arbitrarily long uniform $\mathcal{F}$-necklaces. The
proof of this lemma is fairly straightforward now.

###### Proof of Lemma 7.

Let $\mathcal{G}$ be a minor-closed graph family containing graphs with
arbitrarily large elimination distance to an $\mathcal{F}$-minor free graph.
Suppose towards a contradiction that $\mathcal{G}$ contains no
$\mathcal{F}$-necklace of length at least $t$ for some $t$. Then no graph in
$\mathcal{G}$ contains an $\mathcal{F}$-necklace of length $t$ as a minor,
thereby bounding the elimination distance to an $\mathcal{F}$-minor free graph
of any graph in $\mathcal{G}$ by $g(t)$ by Lemma 12. We reach a contradiction
and obtain that $\mathcal{G}$ contains arbitrarily long
$\mathcal{F}$-necklaces, so by Proposition 7 we conclude that $\mathcal{G}$
also contains arbitrarily long uniform $\mathcal{F}$-necklaces. ∎

###  4.4 Lower bound reduction

Our reduction is based on the following theorem on $d$-CNF Satisfiability,
where each clause has at most $d$ literals [19]. This theorem uses the notion
of an _oracle communication protocol_. In such a protocol, there is a player
with an input for a decision problem who has to answer the decision problem in
time polynomial in the input size. Besides the player, there is an oracle with
unbounded resources, but the oracle does not know the input at the start of
the protocol. The goal is to develop a protocol for communication between the
player and oracle, such that the player can solve any instance in polynomial
time. A trivial protocol sends the entire instance to the oracle and then
sends the solution back, but we are interested in protocols that require less
communication. Theorem 4.1 provides a lower bound on the number of bits of
communication for such a protocol for $d$-CNF.

######  Theorem 4.1 (Cf. [19, Theorem 1]).

Let $d\geq 3$ be an integer and $\epsilon>0$. Then there is no oracle
communication protocol taking $\mathcal{O}(n^{d-\epsilon})$ bits of
communication that can decide for any $d$-CNF formula $F$ whether $F$ is
satisfiable, unless $\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$.

Observe that a protocol sending the entire instance to the oracle takes
$\mathcal{O}(n^{d})$ bits of communication. The theorem implies the following
theorem on CNF Satisfiability, where clauses can have arbitrarily many
variables. This theorem is also described in [30].

######  Theorem 4.2.

There is no polynomial time algorithm that, given a CNF formula $F$ on $n$
variables, constructs an instance $I$ of a fixed decision problem $Q$ such
that

  1. 1.

$F$ is satisfiable if and only if $I$ is a Yes-instance of $Q$,

  2. 2.

$\lvert I\rvert=\mathcal{O}(n^{c})$ for some constant $c$,

unless $\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$.

###### Proof.

Assume towards a contradiction that such a polynomial-time kernelization
algorithm would exist and that the kernel has size $\mathcal{O}(n^{c})$ for
some constant $c$. Without loss of generality, take $c\geq 2$. We can then
construct an oracle communication protocol contradicting Theorem 4.1. Consider
$(c+1)$-CNF, where each clause has at most $c+1$ variables. Using this
kernelization algorithm, the player can first reduce the instance to an
instance of size $\mathcal{O}(n^{c})$. The protocol is concluded by
communicating this instance to the oracle and letting the oracle solve the
problem. Observe that this protocol took only $\mathcal{O}(n^{c})$ bits of
communication. This directly contradicts Theorem 4.1 which stated the non-
existence of any $\mathcal{O}(n^{c+1-\epsilon})$ communication protocol for
any $\epsilon>0$ assuming
$\mathrm{NP}\not\subseteq\mathrm{coNP}/\mathrm{poly}$. Therefore, such a
kernelization algorithm does not exist under these complexity assumptions. ∎

Theorem 4.2 implies that, under common hardness assumptions, there does not
exist a kernelization algorithm for the CNF Satisfiability problem that
outputs a polynomial kernel in the number of variables. We can use this
theorem to prove the non-existence of a kernelization algorithm for
$\mathcal{F}$-Minor Free Deletion with as parameter the size of a modulator to
a graph with constant elimination distance to an $\mathcal{F}$-minor free
graph. Our reduction will use the following graphs. An example is illustrated
in Figure 2.

######  Definition 9 ($J_{H,v,x,y}$).

Let $H$ be a graph, $v,x,y\in V(H)$ with $x\neq y$ and let $c=\lvert
V(H)\rvert$. Define $J_{H,v,x,y}$ to be the graph which can be constructed
with the following two steps.

  * •

We create $c-1$ vertices $x_{1},\dots,x_{c-1}$ for which we define the set
$X\coloneqq\\{x_{1},\dots,x_{c-1}\\}$. We then add precisely those edges such
that $J_{H,v,x,y}[X]$ is isomorphic to $H-\\{v\\}$. We repeat this
construction for a set of vertices $Y\coloneqq\\{y_{1},\dots,y_{c-1}\\}$ such
that $J_{H,v,x,y}[Y]$ is isomorphic to $H-\\{v\\}$.

  * •

Then for any pair of $x_{i}\in X$ and $y_{j}\in Y$, we add $c-2$ extra
vertices to the graph and let $D_{i,j}$ be the set containing these vertices.
We then add edges to the graph such that
$J_{H,v,x,y}[D_{i,j}\cup\\{x_{i},y_{j}\\}]$ is isomorphic to $H$. In
particular, there exists an isomorphism where $x_{i}$ is the image of $x$ and
$y_{j}$ is the image of $y$.

In total, the graph will have $2(c-1)+(c-1)^{2}(c-2)$ vertices.

Figure 2: Illustration of $J_{H,v,x,y}$ with $H={K_{3}}$ and $v,x,y\in V(H)$.
Observe that the subgraph induced by $X$ is indeed isomorphic to
$K_{3}-\\{v\\}$.

The choice of vertices $v,x$ and $y$ will not be important, but they ensure
that the graph is uniquely defined. The constructed graph has some useful
properties.

######  Lemma 13.

Let $H$ be a biconnected graph on at least three vertices and let $v,x,y\in
V(H)$ with $x\neq y$. Let $J_{H,v,x,y}$ be the graph defined in Definition 9
with $X$, $Y$ and $c$ defined accordingly. Let $Z\subseteq V(J_{H,v,x,y})$ be
a vertex set with $\lvert Z\rvert\leq c-1$. If $J_{H,v,x,y}-Z$ contains no
$H$-minor, then $Z$ is equal to $X$ or $Y$.

###### Proof.

Assume towards a contradiction that $Z$ is not equal to $X$ or $Y$. We
distinguish a few cases.

  * •

If $Z$ does not intersect $X\cup Y$, then $Z$ cannot hit all $H$-minors which
we added for each pair of vertices $x\in X$ and $y\in Y$: there are
$(c-1)^{2}$ such pairs, giving a set of $(c-1)^{2}$ $H$-minors that only
intersect each other in $X\cup Y$. As $(c-1)^{2}>c-1$ for $c\geq 3$, the graph
$J_{H,v,x,y}-Z$ contains an $H$-minor in this case.

  * •

Suppose $Z$ is included in $X\cup Y$. Since $Z$ is not equal to $X$ and not
equal to $Y$, there exist vertices $x_{i}\in X$ and $y_{j}\in Y$ such that
$x_{i},y_{j}\not\in Z$. As $Z$ contains no vertices outside $X\cup Y$, it
cannot hit the $H$-minor that was constructed for this pair, so
$J_{H,v,x,y}-Z$ contains an $H$-minor here as well.

  * •

Now assume neither of those cases apply. Let $k=\lvert Z\cap X\rvert$ and
$\ell=\lvert Z\cap Y\rvert$ and observe that $k+\ell\leq c-2$. Then the number
of vertices in $X\setminus Z$ equals $c-1-k$ and the size of $Y\setminus Z$
equals $c-1-\ell$. It follows that the number of pairs of a vertex in
$X\setminus Z$ and one in $Y\setminus Z$ equals

$\displaystyle(c-1-k)(c-1-\ell)$ $\displaystyle=(c-1)^{2}-(c-1)(k+\ell)+k\ell$
$\displaystyle\geq(c-1)^{2}-(c-1)(c-2)$ $\displaystyle=c-1.$

We now obtained at least $c-1$ $H$-minors where any pair of them can only
intersect in a vertex in $(X\cup Y)\setminus Z$. Therefore, if these minors
are all hit by $Z$, then $Z$ needs to contain at least $c-1$ vertices outside
$X\cup Y$. However, at least one vertex of $Z$ is in $X\cup Y$, contradicting
that $\lvert Z\rvert\leq c-1$.

We conclude that if $Z$ is not $X$ or $Y$, then $J_{H,v,x,y}$ contains an
$H$-minor, thereby concluding the proof. ∎

The implication in Lemma 13 is actually an equivalence. For the other
direction, we will prove a slightly stronger statement.

######  Lemma 14.

Let $H$ be a biconnected graph on at least three vertices and let $v,x,y\in
V(H)$ with $x\neq y$. Let $J_{H,v,x,y}$ be the graph defined in Definition 9
with $X$, $Y$ and $c$ defined accordingly. If $Z\subseteq V(J_{H,v,x,y})$ is
equal to $X$ or $Y$, then any biconnected graph that $J_{H,v,x,y}-Z$ contains
as a minor is a proper minor of $H$.

###### Proof.

Assume without loss of generality that $Z=Y$. Now assume towards a
contradiction that $J_{H,v,x,y}-Y$ contains an $H^{\prime}$-minor for some
biconnected $H^{\prime}$ that is not a proper minor of $H$ Observe that by
Proposition 8, a biconnected component of $J_{H,v,x,y}-Y$ must contain an
$H^{\prime}$-minor. However, the only biconnected components of
$J_{H,v,x,y}-Y$ are the induced subgraphs by the vertices
$D_{i,j}\cup\\{x_{i}\\}$ for $i\in[c-1]$. These subgraphs are minors of $H$,
so they cannot contain an $H^{\prime}$-minor when $H^{\prime}$ is a proper
minor of $H$. ∎

We can now give the reduction.

######  Lemma 15.

Let $\mathcal{F}$ be a finite collection of biconnected graphs on at least
three vertices. Let $H\in\mathcal{F}$, let $x,y\in V(H)$ and consider the
uniform necklace structure $(H,x,y)$. There exists a polynomial time algorithm
that, given a CNF formula on $n$ variables $x_{1},\dots,x_{n}$, outputs a
graph $G$ together with a set $X\subseteq V(G)$ of size
$k=\mathcal{O}_{\mathcal{F}}(n)$ and an integer $t$, such that

  1. 1.

$F$ is satisfiable if and only if $G$ has a solution to $\mathcal{F}$-Minor
Free Deletion of size at most $t$,

  2. 2.

Each connected component of $G-X$ is a minor of a uniform necklace with
structure $(H,x,y)$.

###### Proof.

We will also assume that for any $H\in\mathcal{F}$, no proper minor of $H$ is
contained in $\mathcal{F}$. Otherwise, we can remove $H$ from $\mathcal{F}$ in
the context of $\mathcal{F}$-Minor Free Deletion, as the deletion of all
$H$-minors follows from the deletion of the proper minors of $H$.

We will start our construction of $G$ by picking vertices $v,x,y\in V(H)$ with
$x\neq y$ and let $c=\lvert V(H)\rvert=\mathcal{O}_{\mathcal{F}}(1)$. Given a
CNF formula $F$ on variables $x_{1},\dots,x_{n}$, the algorithm executes the
following three steps which are illustrated by Figure 3:

  1. 1.

For each variable $x_{i}$, we add a variable gadget $J_{i}$ to $G$ which is a
copy of the graph $J_{H,v,x,y}$. Instead of using $X$ and $Y$ for the two
subsets of $V(J_{i})$ defined earlier, we use the names
$V_{x_{i}}=\\{v_{x_{i},1},\dots,v_{x_{i},c-1}\\}$ and $V_{\neg
x_{i}}=\\{v_{\neg x_{i},1},\dots,v_{\neg x_{i},c}\\}$. Notice the direct
correspondence between literals and these sets.

  2. 2.

For each clause in $F$, we are going to add a necklace to $G$. For an integer
$t$, we let $N_{t}$ denote the uniform necklace with structure $(H,x,y)$ of
length $t$. For each clause in $F$ with length $m$, we add a copy of $N_{m}$
to the graph. Each literal in this clause corresponds to a bead in the
necklace. For $i\in[m]$, we let $\ell_{i}$ be the $i$th literal in this
clause. We are now going to connect the $i$th bead to the vertices in
$V_{\ell_{i}}$ for each $i\in[m]$. To do this, we pick a vertex $u$ in the
$i$th bead that is not adjacent to the other beads. As $H$ has at least three
vertices, such a vertex exists. We then connect $u$ to $V_{\ell_{i}}$, such
that the subgraph induced by $V_{\ell_{i}}\cup\\{u\\}$ is isomorphic to $H$.
By definition of $J_{H,v,x,y}$, we can ensure this by only adding edges
between $u$ and $V_{\ell_{i}}$.

  3. 3.

It remains to add one extra copy of $H$ to $G$, whose vertex set we denote
with $S_{0}$. We remove one edge from this copy of $H$, say with endpoints $a$
and $b$. Then for every necklace that we added, we add an edge between $a$ and
the first bead, and an edge between $b$ and the last bead of the necklace. We
make sure that the endpoints in the necklace are not connected to a variable
gadget.

Observe that, for fixed $\mathcal{F}$, the entire procedure can be executed in
time polynomial in the size of $F$.

Figure 3: Illustration of the reduction in the proof of Lemma 15 for a clause
$(x_{a}\vee x_{b}\vee\neg x_{c})$. Let $\ell_{i}$ denote the $i$th literal of
this clause. We pick $H=K_{3}$ and we pick distinct $x,y\in V(H)$, so the
uniform necklace structure becomes $(K_{3},x,y)$. We add such a uniform
necklace of length $3$. The first and last bead are connected to $S_{0}$. We
then connect each bead to a variable gadget. For the $i$th bead, we pick a
vertex $u$ in this bead which is not adjacent to the next or previous bead,
and neither to $S_{0}$. We then ensure that the subgraph induced by $u$ and
$V_{\ell_{i}}$ equals $K_{3}$. Observe that, since the last literal of the
clause is a negated variable, the last bead is connected to $V_{\neg x_{c}}$.

Let $X\coloneqq\left(\bigcup_{i\in[n]}(V_{x_{i}}\cup V_{\neg
x_{i}})\right)\cup S_{0}$. Observe that $\lvert
X\rvert=2n(c-1)+c=\mathcal{O}_{\mathcal{F}}(n)$. We are now interested in the
structure of the connected components of $G-X$. For each clause in $F$, we
added a uniform necklace with structure $(H,x,y)$ in the second step. Since
the neighbors of this necklace in $G$ are all in $X$, these necklaces are
connected components of $G-X$. The other connected components of $G-X$ are
contained in the variable gadgets which were added in the first step. Each of
these is a copy of $H$ where two vertices are removed, so these components are
minors of $H$. Therefore, each connected component of $G-X$ is a minor of a
uniform necklace with structure $(H,x,y)$.

Let $w$ be the total number of occurrences of literals in $F$, i.e.

$w\coloneqq\sum_{\text{clause $C$ in $F$}}\text{\\#literals in $C$}$

We claim that $F$ is satisfiable if and only if $G$ has a solution to
$\mathcal{F}$-Minor Free Deletion of size at most $w+(c-1)n$. We will first
prove the ‘only if’ direction.

######  Claim.

If $F$ is satisfiable, then $G$ has a solution to $\mathcal{F}$-Minor Free
Deletion of size at most $w+(c-1)n$.

###### Proof.

Suppose that $F$ has a satisfying truth assignment. Based on this truth
assignment, we will construct a solution $Z$ for $\mathcal{F}$-Minor Free
Deletion of size $w+(c-1)n$ in the corresponding graph $G$. For every variable
$x_{i}$ that is set to True, we add the $c-1$ vertices in $V_{x_{i}}$ to $Z$.
For every variable set to False, we add $V_{\neg x_{i}}$ to $Z$. These
vertices are in the variable gadgets added in the first step. Now, $Z$
contains $(c-1)n$ vertices.

Then for each clause in $F$, we consider each literal $\ell_{i}$ in this
clause and consider the necklace in $G$ corresponding to this clause. If
$\ell_{i}$ evaluates to True according to the truth assignment, we add a
vertex from the $i$th bead to $Z$ that is adjacent to the previous or next
bead. Otherwise, we add the vertex in this bead adjacent to $V_{\ell_{i}}$.
This procedure adds another $w$ vertices to $Z$, ensuring that $Z$ has size
$w+(c-1)n$.

We will now prove that $G-Z$ contains no $\mathcal{F}$-minors. The graph $G-Z$
contains multiple connected components. We will argue that none of these
components contains an $\mathcal{F}$-minor, as it implies directly that $G-Z$
has no $\mathcal{F}$-minors.

Consider a variable gadget $J_{i}$ corresponding to some variable $x_{i}$, and
assume without loss of generality (by symmetry) that $x_{i}$ evaluates to True
in the given truth assignment. The only vertices in $J_{i}$ that were
connected to other vertices in $G$ are those in $V_{x_{i}}$ and those in
$V_{\neg x_{i}}$. The first set is removed. For the second set, observe that
these vertices are only connected to beads in necklaces where the
corresponding literal is $\neg x_{i}$, and that precisely these vertices in
those beads are removed as $\neg x_{i}$ evaluates to False. It follows that
$J_{i}-V_{x_{i}}$ is a connected component in $G-Z$. By Lemma 14, any
biconnected minor of $J_{i}-V_{x_{i}}$ is a proper minor of $H$. By
assumption, for each pair of graphs $H_{1},H_{2}\in\mathcal{F}$, $H_{1}$ is
not a minor of $H_{2}$ and $H_{2}$ is not a minor of $H_{1}$. Since all graphs
in $\mathcal{F}$ are biconnected, it follows that the connected component
$J_{i}-V_{x_{i}}$ contains no $\mathcal{F}$-minors.

After analyzing the connected components containing vertices of variable
gadgets, it remains to analyze the other connected components of $G-Z$. Define
the set $\mathcal{F}^{\prime}$ to be the set of all graphs that can be
obtained by either removing a vertex or by removing an edge from a graph in
$\mathcal{F}$. Observe that $(G-Z)[S_{0}]\in\mathcal{F}^{\prime}$, and
similarly the subgraph induced by what remains of a bead of a necklace is in
$\mathcal{F}^{\prime}$. Besides, since at least one literal evaluates to True
in each clause, we always remove at least one edge between some pair of
consecutive beads in a necklace. Hence, each necklace in $G$ is now broken
into at least two $\mathcal{F}^{\prime}$-necklaces in $G-Z$. This also implies
that in each necklace there does not exist a path through the necklace from
the first to the last bead. Therefore, there exists at most one edge between
each of those $\mathcal{F}^{\prime}$-necklaces and vertex set $S_{0}$. Now
consider the connected component that includes $S_{0}$. It follows that each
biconnected component of at least three vertices of this component is either
included in a bead or in $S_{0}$. In both cases, it is a minor of a graph in
$\mathcal{F}^{\prime}$. Observe that no graph in $\mathcal{F}^{\prime}$
contains an $\mathcal{F}$-minor: then this graph would be a proper minor of
$H$ since $\mathcal{F}^{\prime}$ contains only proper subgraphs of $H$. It
follows that no biconnected component on at least three vertices contains an
$\mathcal{F}$-minor, so this component contains no $\mathcal{F}$-minor by
Proposition 8. It remains to observe that all other components of $G-Z$ are
$\mathcal{F}^{\prime}$-necklaces which are not connected to any other
vertices. By Lemma 6, these components contain no $\mathcal{F}$-minors either.
Since no component of $G-Z$ contains an $\mathcal{F}$-minor, $G-Z$ has no
$F$-minors. ∎

It remains to prove the opposite implication.

######  Claim.

If $G$ has a solution to $\mathcal{F}$-Minor Free Deletion of size at most
$w+(c-1)n$, then $F$ is satisfiable.

###### Proof.

To this end, we will first observe that there are $w+(c-1)n$ pairwise disjoint
$\mathcal{F}$-minors in $G$. Each literal contributes such an $H$-minor in the
bead in the corresponding $\\{H\\}$-necklace, giving $w$ pairwise disjoint
$\mathcal{F}$-minors. Now consider a variable gadget $J_{i}$ corresponding to
variable $x_{i}$. It contains the vertex sets
$V_{x_{i}}=\\{v_{x_{i},1},\dots,v_{x_{c-1}}\\}$ and $V_{\neg x_{i}}=\\{v_{\neg
x_{i},1},\dots,v_{\neg x_{c-1}}\\}$. For each pair of a vertex in $V_{x_{i}}$
and a vertex in $V_{\neg x_{i}}$, we created an $H$-minor in this gadget. We
can identify $c-1$ pairwise disjoint $H$-minors in $G$ by considering for each
$j\in[c-1]$ the $H$-minor created for the pair of $v_{x_{i},j}$ and $v_{\neg
x_{i},j}$. Observe that these minors are pairwise disjoint and contained in
$J_{i}$. Therefore each variable gadget contributes $c-1$ $H$-minors, giving a
total of $w+(c-1)n$ $H$-minors which are all pairwise disjoint.

Now consider a variable gadget $J_{i}$ for variable $x_{i}$. If there exists a
solution to $\mathcal{F}$-Minor Free Deletion within this variable gadget of
at most $c-1$ vertices, then by Lemma 13 the solution is equal to $V_{x_{i}}$
or $V_{\neg x_{i}}$.

Now consider a solution $Z$ for $\mathcal{F}$-minor deletion in $G$ of at most
$w+(c-1)n$ vertices. Since we can identify $w+(c-1)n$ pairwise disjoint
$H$-minors, $Z$ contains one vertex from each of the identified $H$-minors in
$G$. It follows that $Z$ contains $c-1$ vertices from each variable gadget.
Then for a variable $x_{i}$, the intersection of $Z$ with $V(J_{i})$ equals
precisely $V_{x_{i}}$ or $V_{\neg x_{i}}$ by Lemma 13.

We can now construct a truth assignment for $F$. For each variable $x_{i}$, we
verify which vertices $Z$ contains from $J_{i}$. If $V_{x_{i}}$ is included
(and therefore $V_{\neg x_{i}}$ is disjoint from $Z$), we set $x_{i}$ to True,
and if $V_{\neg x_{i}}$ is included we set $x_{i}$ to False. It remains to
prove that this yields a valid truth assignment.

To this end, we first consider an $\mathcal{F}$-necklace corresponding to a
clause. Observe that $Z$ contains precisely one vertex from each bead, as each
bead contains one of the $w+(c-1)n$ pairwise disjoint $H$-minors. Suppose
towards a contradiction that in each bead, $Z$ contains the vertex which we
connected to a variable gadget. Since this vertex is not adjacent to other
beads by construction and since $H$ is biconnected, it follows that there
still exists a path from $a\in S_{0}$ through this necklace to $b\in S_{0}$.
By contracting this path to a single edge, we obtain a copy of the graph $H$
on vertex set $S_{0}$, contradicting that $Z$ hits all $H$-minors. It follows
that in each necklace corresponding to a clause, we can identify a bead where
the vertex connected to the corresponding variable gadget is not in $Z$. Let
this vertex be $u$ in a bead corresponding to literal $\ell$. We now claim
that $\ell$ evaluates to True, implying that such a literal exists in every
clause and thereby proving that $F$ is satisfiable. Assume towards a
contradiction that $\ell$ evaluates to False, then in the corresponding
variable gadget, none of the vertices of $V_{\ell}$ were included in $Z$.
However, recall that we created an $H$-subgraph on vertex set
$V_{\ell}\cup\\{v\\}$. As none of these vertices is in $Z$, this subgraph
contradicts $Z$ being a solution to $\mathcal{F}$-Minor Free Deletion. It
follows that $\ell$ evaluates to True, so every clause in $F$ contains a
literal that evaluates to True. This concludes the claim that $F$ is
satisfiable. ∎

These claims prove the correctness of our reduction and conclude the proof of
Lemma 15. ∎

We are finally able to prove Lemma 8. We formalize this lemma with the
following theorem and prove the theorem.

######  Theorem 4.3 (Formalization of Lemma 8).

Let $\mathcal{F}$ be a finite collection of biconnected graphs on at least
three vertices. Let $\mathcal{G}$ be a minor-closed graph family containing
arbitrarily long uniform $\mathcal{F}$-necklaces. There is no polynomial time
algorithm that, given a graph $G$, integer $t$ and vertex set $X$ of size $k$
such that $G-X$ is in $\mathcal{G}$, constructs an instance $I$ of a fixed
decision problem $Q$ such that

  1. 1.

$G$ has a solution to $\mathcal{F}$-Minor Free Deletion of size at most $t$ if
and only if $I$ is a Yes-instance of $Q$,

  2. 2.

$\lvert I\rvert=\mathcal{O}(k^{c})$ for some constant $c$,

unless $\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$.

###### Proof.

We will prove this theorem by contradiction: if such an algorithm would exist,
we can use it to give a kernel for the CNF Satisfiability problem which would
contradict Theorem 4.2. This can be achieved by reducing a provided CNF
formula to an instance of $\mathcal{F}$-Minor Free Deletion.

Let $F$ be a CNF formula on $n$ variables. By Proposition 7, there exists a
uniform necklace structure $(H,x,y)$ with $H\in\mathcal{F}$ and $x,y\in V(H)$
such that all uniform necklaces with this structure are contained in
$\mathcal{G}$. For this uniform necklace structure $(H,x,y)$, let $G$ be the
graph obtained by Lemma 15 with a set $X$ of size
$k=\mathcal{O}_{\mathcal{F}}(n)$ such that all connected components of $G-X$
are minors of uniform necklaces with this structure. Then observe that $G-X$
itself is also a minor of a sufficiently long uniform necklace with the same
structure. Let $t$ be the integer such that $F$ is satisfiable if and only if
$G$ has a solution to $\mathcal{F}$-Minor Free Deletion of size at most $t$.

If such an algorithm would exist, we can now construct an instance $I$ of a
fixed decision problem $Q$ such that $G$ has a solution to $\mathcal{F}$-Minor
Free Deletion of size at most $t$ if and only if $I$ is a Yes-instance of $Q$,
while $\lvert I\rvert=\mathcal{O}(k^{c})$. Since
$k=\mathcal{O}_{\mathcal{F}}(n)$, the bound on the size of $I$ becomes $\lvert
I\rvert=\mathcal{O}(n^{c})$ when $\mathcal{F}$ is a finite collection of
graphs. However, since $G$ has a solution to $\mathcal{F}$-Minor Free Deletion
of size at most $t$ if and only if $F$ is satisfiable, we obtain a
contradiction with Theorem 4.2. Therefore such an algorithm cannot exist,
concluding the proof of Theorem 4.3. ∎

###  4.5 Proof of Theorem 1.1

By combining our previous results, we can now prove Theorem 1.1.

######  Theorem 1.

Let $\mathcal{G}$ be a minor-closed graph family. Then Feedback Vertex Set
admits a polynomial kernel in the size of a $\mathcal{G}$-modulator if and
only if $\mathcal{G}$ has bounded elimination distance to a forest, assuming
that $\mathrm{NP}\not\subseteq\mathrm{coNP}/\mathrm{poly}$.

###### Proof.

Let $\mathcal{G}_{\eta}$ be the set of graphs with elimination distance to a
forest at most $\eta$. Then by Theorem 3.1, Feedback Vertex Set admits a
polynomial kernel in the size of a $\mathcal{G}_{\eta}$-modulator $X$. Now let
$\mathcal{H}$ be a family of graphs where each graph has elimination distance
to a forest at most $\eta$. Then Theorem 3.1 implies directly that Feedback
Vertex Set also admits a polynomial kernel in an $\mathcal{H}$-modulator,
since such a modulator is always also an $\mathcal{G}_{\eta}$-modulator since
$\mathcal{H}\subseteq\mathcal{G}_{\eta}$.

Regarding the lower bound, Theorem 1.2 states that for any minor-closed graph
family $\mathcal{G}$ and any finite set $\mathcal{F}$ of biconnected planar
graphs on at least three vertices, $\mathcal{F}$-Minor Free Deletion does not
admit a polynomial kernel in the size of a $\mathcal{G}$-modulator, unless
$\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$. By taking
$\mathcal{F}=\\{K_{3}\\}$, we obtain the stated lower bound. ∎

##  5 Conclusion and discussion

We conclude that the elimination distance to a forest characterizes the
Feedback Vertex Set problem in terms of polynomial kernelization. For a minor-
closed graph family $\mathcal{G}$, the problem admits a polynomial kernel in
the size of a $\mathcal{G}$-modulator if and only if $\mathcal{G}$ has bounded
elimination distance to a forest, assuming
$\mathrm{NP}\not\subseteq\mathrm{coNP}/\mathrm{poly}$. In particular, this
implies that Feedback Vertex Set does not admit a polynomial kernel in the
deletion distance to a graph of constant bridge-depth under the mentioned
hardness assumption. We also generalize the lower bound to other
$\mathcal{F}$-Minor Free Deletion problems where $\mathcal{F}$ contains only
biconnected planar graphs on at least three vertices. It remains unknown
whether such a lower bound also generalizes to collections of graphs
$\mathcal{F}$ that contain non-planar graphs.

An interesting open problem is whether similar polynomial kernels can be
obtained for other $\mathcal{F}$-Minor Free Deletion problems. Regarding the
field of fixed parameter tractable algorithms, it was recently shown [32] that
for any set $\mathcal{F}$ of connected graphs, $\mathcal{F}$-Minor Free
Deletion admits an FPT algorithm when parameterized by the elimination
distance to an $\mathcal{F}$-minor free graph (or even $\mathcal{H}$-treewidth
when $\mathcal{H}$ is the class of $\mathcal{F}$-minor free graphs). This
generalizes known FPT algorithms for the natural parameterization by solution
size. Regarding polynomial kernels, $\mathcal{F}$-Minor Free Deletion problems
admit a polynomial kernel in the solution size when $\mathcal{F}$ contains a
planar graph [23]. Do polynomial kernels exist when the problem is
parameterized by a modulator to a graph of constant elimination distance to
being $\mathcal{F}$-minor free?

## References

  * [1] Abu-Khzam, F.N., Fellows, M.R., Langston, M.A., Suters, W.H.: Crown structures for vertex cover kernelization. Theory Comput. Syst. 41(3), 411–430 (2007). https://doi.org/10.1007/s00224-007-1328-0
  * [2] Bergougnoux, B., Papadopoulos, C., Telle, J.A.: Node multiway cut and subset feedback vertex set on graphs of bounded mim-width. In: Adler, I., Müller, H. (eds.) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers. Lecture Notes in Computer Science, vol. 12301, pp. 388–400. Springer (2020). https://doi.org/10.1007/978-3-030-60440-0_31
  * [3] Biedl, T., Kant, G.: A better heuristic for orthogonal graph drawings. Computational Geometry 9(3), 159–180 (1998). https://doi.org/https://doi.org/10.1016/S0925-7721(97)00026-6
  * [4] Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996). https://doi.org/10.1137/S0097539793251219
  * [5] Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers. Lecture Notes in Computer Science, vol. 5917, pp. 17–37. Springer (2009). https://doi.org/10.1007/978-3-642-11269-0_2
  * [6] Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86–111 (2015). https://doi.org/10.1016/j.ic.2014.12.008
  * [7] Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst. 46(3), 566–597 (2010). https://doi.org/10.1007/s00224-009-9234-2
  * [8] Bougeret, M., Jansen, B.M.P., Sau, I.: Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference). LIPIcs, vol. 168, pp. 16:1–16:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.ICALP.2020.16
  * [9] Bougeret, M., Sau, I.: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? Algorithmica 81(10), 4043–4068 (2019). https://doi.org/10.1007/s00453-018-0468-8
  * [10] Bui-Xuan, B., Telle, J.A., Vatshelle, M.: Feedback vertex set on graphs of low cliquewidth. In: Fiala, J., Kratochvíl, J., Miller, M. (eds.) Combinatorial Algorithms, 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28-July 2, 2009, Revised Selected Papers. Lecture Notes in Computer Science, vol. 5874, pp. 113–124. Springer (2009). https://doi.org/10.1007/978-3-642-10217-2_14
  * [11] Bulian, J., Dawar, A.: Fixed-parameter tractable distances to sparse graph classes. Algorithmica 79(1), 139–158 (2017). https://doi.org/10.1007/s00453-016-0235-7
  * [12] Burrage, K., Estivill-Castro, V., Fellows, M.R., Langston, M.A., Mac, S., Rosamond, F.A.: The undirected feedback vertex set problem has a poly(_k_) kernel. In: Bodlaender, H.L., Langston, M.A. (eds.) Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings. Lecture Notes in Computer Science, vol. 4169, pp. 192–202. Springer (2006). https://doi.org/10.1007/11847250_18
  * [13] Chen, J., Kanj, I.A., Jia, W.: Vertex cover: Further observations and further improvements. J. Algorithms 41(2), 280–301 (2001). https://doi.org/10.1006/jagm.2001.1186
  * [14] Chlebík, M., Chlebíková, J.: Crown reductions for the minimum weighted vertex cover problem. Discret. Appl. Math. 156(3), 292–312 (2008). https://doi.org/10.1016/j.dam.2007.03.026
  * [15] Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save k colors in o(n${}^{\mbox{2}}$) steps. In: Hromkovic, J., Nagl, M., Westfechtel, B. (eds.) Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers. Lecture Notes in Computer Science, vol. 3353, pp. 257–269. Springer (2004). https://doi.org/10.1007/978-3-540-30559-0_22
  * [16] Chuzhoy, J.: Improved bounds for the excluded grid theorem. CoRR abs/1602.02629 (2016), http://arxiv.org/abs/1602.02629
  * [17] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015). https://doi.org/10.1007/978-3-319-21275-3
  * [18] Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011. pp. 150–159. IEEE Computer Society (2011). https://doi.org/10.1109/FOCS.2011.23
  * [19] Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1–23:27 (2014). https://doi.org/10.1145/2629620
  * [20] Donkers, H., Jansen, B.M.P.: Preprocessing to reduce the search space: Antler structures for feedback vertex set. In: Kowalik, L., Pilipczuk, M., Rzazewski, P. (eds.) Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers. Lecture Notes in Computer Science, vol. 12911, pp. 1–14. Springer (2021). https://doi.org/10.1007/978-3-030-86838-3_1
  * [21] Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A., Saurabh, S.: The complexity ecology of parameters: An illustration using bounded max leaf number. Theory Comput. Syst. 45(4), 822–848 (2009). https://doi.org/10.1007/s00224-009-9167-9
  * [22] Fomin, F.V., Lokshtanov, D., Misra, N., Philip, G., Saurabh, S.: Hitting forbidden minors: Approximation and kernelization. SIAM J. Discret. Math. 30(1), 383–410 (2016). https://doi.org/10.1137/140997889
  * [23] Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar $\mathcal{F}$-Deletion: Approximation, kernelization and optimal FPT algorithms. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012. pp. 470–479. IEEE Computer Society (2012). https://doi.org/10.1109/FOCS.2012.62