University of Bremen, Germanylinderal@uni-
bremen.dehttps://orcid.org/0000-0001-6714-5034 University of Bremen,
Germanysiebertz@uni-bremen.dehttps://orcid.org/0000-0002-6347-1198 University
of Bremen, Germanyvigny@uni-bremen.dehttps://orcid.org/0000-0002-4298-8876
Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny <ccs2012> <concept>
<concept_id>10003752.10003809.10003635</concept_id> <concept_desc>Theory of
computation Graph algorithms analysis</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003809.10010052.10010053</concept_id>
<concept_desc>Theory of computation Fixed parameter
tractability</concept_desc> <concept_significance>500</concept_significance>
</concept> </ccs2012> [500]Theory of computation Graph algorithms analysis
[500]Theory of computation Fixed parameter tractability Javier Esparza and
Daniel Král’ 2 45th International Symposium on Mathematical Foundations of
Computer Science (MFCS 2020) MFCS 2020 MFCS 2020 August 24–28, 2020 Prague,
Czech Republic 170 83

# Elimination distance to bounded degree
on planar graphs

Alexander Lindermayr  Sebastian Siebertz  Alexandre Vigny

###### Abstract

We study the graph parameter _elimination distance to bounded degree_ , which
was introduced by Bulian and Dawar in their study of the parameterized
complexity of the graph isomorphism problem. We prove that the problem is
fixed-parameter tractable on planar graphs, that is, there exists an algorithm
that given a planar graph $G$ and integers $d$ and $k$ decides in time
$f(k,d)\cdot n^{c}$ for a computable function $f$ and constant $c$ whether the
elimination distance of $G$ to the class of degree $d$ graphs is at most $k$.

###### keywords:

Elimination distance, parameterized complexity, structural graph theory.

###### category:

##  1 Introduction

Structural graph theory offers a wealth of parameters that measure the
complexity of graphs or graph classes. Among the most prominent parameters are
_treedepth_ and _treewidth_ , which intuitively measure the resemblance of
graphs with stars and trees, respectively. Other commonly studied structurally
restricted graph classes are the class of _planar graphs_ , classes that
exclude a fixed graph as a _minor_ or _topological minor_ , classes of
_bounded expansion_ and _nowhere dense_ classes.

Once we have gained a good understanding of a graph class $\mathscr{C}$, it is
natural to study classes whose members are _close_ to graphs in $\mathscr{C}$.
One of the simplest measures of distance to a graph class $\mathscr{C}$ is the
number of vertices or edges that one must delete (or add) to a graph $G$ to
obtain a graph from $\mathscr{C}$. Guo et al. [11] formalized this concept
under the name _distance from triviality_. For example, the size of a minimum
vertex cover is the distance to the class of edgeless graphs and the size of a
minimum feedback vertex set is the distance to the class of forests. More
generally, for a graph $G$, a vertex set $X$ is called a _$c$ -treewidth
modulator_ if the treewidth of $G-X$ is at most $c$, hence, the size of a
$c$-treewidth modulator corresponds to the distance to the class of graphs of
treewidth at most $c$. This concept was introduced and studied by Gajarksý et
al. in [9].

The _elimination distance_ to a class $\mathscr{C}$ of graphs measures the
number of recursive deletions of vertices needed for a graph $G$ to become a
member of $\mathscr{C}$. More precisely, a graph $G$ has elimination distance
$0$ to $\mathscr{C}$ if $G\in\mathscr{C}$, and otherwise elimination distance
$k+1$, if in every connected component of $G$ we can delete a vertex such that
the resulting graph has elimination distance $k$ to $\mathscr{C}$. Elimination
distance was introduced by Bulian and Dawar [3] in their study of the
parameterized complexity of the graph isomorphism problem.

Elimination distance naturally generalizes the concept of treedepth, which
corresponds to the elimination distance to the class $\mathscr{C}_{0}$ of
edgeless graphs. The parameter also has very nice algorithmic applications. On
the one hand, small elimination distance to a class $\mathscr{C}$ on which
efficient algorithms for certain problems are known to exist, may allow to
lift the applicability of these algorithms to a larger class of graphs. For
example, Bulian and Dawar [3] showed that the graph isomorphism problem is
fixed-parameter tractable when parameterized by the elimination distance to
the class $\mathscr{C}_{d}$ of graphs with maximum degree bounded by $d$, for
any fixed integer $d$. Recently, Hols et al. [12] proved the existence of
polynomial kernels for the vertex cover problem parameterized by the size of a
deletion set to graphs of bounded elimination distance to different classes of
graphs.

On the other hand, it is an interesting algorithmic question by itself to
determine the elimination distance of a given graph $G$ to a class
$\mathscr{C}$ of graphs. It is well known (see e.g. [1, 14, 15]) that
computing treedepth, i.e. elimination distance to $\mathscr{C}_{0}$, is fixed-
parameter tractable. More precisely, we can decide in time $f(k)\cdot n$
whether an $n$-vertex graph $G$ has treedepth at most $k$. Bulian and Dawar
proved in [4] that computing the elimination distance to any minor-closed
class $\mathscr{C}$ is fixed-parameter tractable when parameterized by the
elimination distance. They also raised the question whether computing the
elimination distance to the class $\mathscr{C}_{d}$ of graphs with maximum
degree at most $d$ is fixed-parameter tractable when parameterized by the
elimination distance and $d$. Note that this question is not answered by their
result for minor-closed classes, since $\mathscr{C}_{d}$ is not closed under
taking minors.

For $k,d\in\mathbb{N}$, we denote by $\mathscr{C}_{k,d}$ the class of all
graphs that have elimination distance at most $k$ to $\mathscr{C}_{d}$. It is
easy to see that for every fixed $k$ and $d$ we can formulate the property
that a graph is in $\mathscr{C}_{k,d}$ by a sentence in monadic second-order
logic (MSO). By the famous theorem of Courcelle [6] we can test every MSO-
property $\varphi$ in time $f(|\varphi|,t)\cdot n$ on every $n$-vertex graph
of treewidth $t$ for some computable function $f$. Hence, we can decide for
every $n$-vertex graph $G$ of treewidth $t$ whether $G\in\mathscr{C}_{k,d}$ in
time $f(k,d,t)\cdot n$ for some computable function $f$. However, for $d\geq
3$ already the class $\mathscr{C}_{d}$ has unbounded treewidth, and so the
same holds for $\mathscr{C}_{k,d}$ for all values of $k$. Thus, Courcelle’s
Theorem cannot be applied to derive fixed-parameter tractability of the
problem in full generality.

On the other hand, it is easy to see that the graphs in $\mathscr{C}_{k,d}$
exclude the complete graph $K_{k+d+2}$ as a topological minor, and hence, for
every fixed $k$ and $d$, the class $\mathscr{C}_{k,d}$ in particular has
bounded expansion and is nowhere dense. We can efficiently test first-order
(FO) properties on bounded expansion and nowhere dense classes [8, 10],
however, first-order logic is too weak to express the elimination distance
problem. This follows from the fact that first-order logic is too weak to
express even connectivity of a graph or to define connected components.

While we are unable to resolve the question of Bulian and Dawar in full
generality, in this work we initiate the quest of determining the
parameterized complexity of elimination distance to bounded degree graphs for
restricted classes of inputs. We prove that for every $n$-vertex graph $G$
that excludes $K_{5}$ as a minor (in particular for every planar graph) we can
test whether $G\in\mathscr{C}_{k,d}$ in time $f(k,d)\cdot n^{c}$ for a
computable function $f$ and constant $c$. Hence, the problem is fixed-
parameter tractable with parameters $k$ and $d$ when restricted to
$K_{5}$-minor-free graphs.

######  Theorem 1.1 (Main result).

There is an algorithm that for a $K_{5}$-minor-free input graph $G$ with $n$
vertices and integers $k$ and $d$, decides in time $f(k,d)\cdot n^{c}$ whether
$G$ belongs to $\mathscr{C}_{k,d}$, where $f$ is a computable function and $c$
is a constant.

Observe that the result is not implied by the result of Bulian and Dawar for
minor-closed classes, as the $K_{5}$-minor-free subclass of $\mathscr{C}_{d}$
is not minor-closed. It is natural to consider as a next step classes that
exclude some fixed graph as a minor or as a topological minor, and finally to
resolve the problem in full generality.

To solve the problem on $K_{5}$-minor-free graphs we combine multiple
techniques from parameterized complexity theory and structural graph theory.
First, we use the fact that the property of having elimination distance at
most $k$ for fixed $k$ is MSO definable, and hence efficiently solvable by
Courcelle’s Theorem on graphs of bounded treewidth. If the input graph $G$ has
small treewidth, we can hence solve the instance by Courcelle’s Theorem.

If $G$ has large treewidth, we distinguish two cases. In the first case, there
exist no vertices of degree greater than $k+d$. In this case, we use the fact
that $G$ has large treewidth to conclude that it contains a large grid minor
[16]. This in turn enables us to find an irrelevant vertex, that is, a vertex
whose deletion does not change containment in $\mathscr{C}_{k,d}$. By
iteratively removing irrelevant vertices until this is no longer possible we
arrive at an instance of small treewidth. The irrelevant vertex technique was
introduced in [17] and is by now a standard technique in parameterized
algorithms, see [18] for a survey.

In the second case, there exist vertices of degree larger than $k+d$. Denote
by $R$ the set of all these vertices. We show that by contracting all
components of $G-R$ we get a graph of bounded treedepth (and hence of bounded
treewidth). We furthermore show that for each of the contracted components we
can compute a _connectivity pattern_ from a finite list of possible
connectivity patterns that describes what happens if vertices from the
component are (recursively) deleted. To compute the connectivity pattern, we
again apply an irrelevant vertex argument inside the components. This part of
the reasoning is technically quite involved. Once all connectivity patterns
are computed, we can formulate containment in $\mathscr{C}_{k,d}$ over a
colored graph of bounded treedepth in MSO, which can again be efficiently
evaluated by Courcelle’s Theorem. After fixing our notation in Section 2, we
provide the details of the proofs in Section 3 and Section 4.

##  2 Preliminaries

A _graph_ $G$ consists of a set of vertices $V(G)$ and a set of edges $E(G)$.
We assume that graphs are finite, simple and undirected, and we write
$\\{u,v\\}$ for an edge between the vertices $u$ and $v$. For a set of
vertices $S\subseteq V(G)$, we denote the subgraph of $G$ induced by the
vertices $V(G)\setminus S$ by $G-S$. If $S=\\{a\\}$, we write $G-a$.

A _partial order_ on a set $V$ is a binary relation $\leq$ on $V$ that is
reflexive, anti-symmetric and transitive. A set $W\subseteq V$ is a _chain_ if
it is totally ordered by $\leq$. If $\leq$ is a partial order on $V$, and for
every element $v\in V$ the set $V_{\leq v}\coloneqq\\{u\in V\mid u\leq v\\}$
is a chain, then $\leq$ is a _tree order_. Note that the covering relation of
a tree order is not necessarily a tree, but may be a forest. An _elimination
order_ on a graph $G$ is a tree order $\leq$ on $V(G)$ such that for every
edge $\\{u,v\\}\in E(G)$ we have either $u\leq v$ or $v\leq u$. The _depth_ of
a vertex $v$ in an order $\leq$ is the size of the set $V_{<v}\coloneqq\\{u\in
V\mid u<v\\}$. The _depth_ of an order $\leq$ is maximal depth among all
vertices.

The _treedepth_ of a graph $G$ is defined recursively as follows.

$\mathrm{td}(G)=\begin{cases}0&\text{if $G$ is edgeless,}\\\
1+\min\\{\mathrm{td}(G-v)\mid v\in V(G)\\}&\text{if $G$ is connected and not
edgeless,}\\\ \max\\{\mathrm{td}(H)\mid\text{$H$ connected component of
$G$}\\}&\text{otherwise}.\end{cases}$

A graph $G$ has treedepth at most $k$ if and only if there exists an
elimination order on $G$ of depth at most $k$. If the longest path in $G$ has
length $k$, then its treedepth is bounded by $k$ and an elimination order of
at most this depth can be found in linear time by a depth-first-search.

Elimination distance to a class $\mathscr{C}$ naturally generalizes the
concept of treedepth. Let $\mathscr{C}$ be a class of graphs. The _elimination
distance_ of $G$ to $\mathscr{C}$ is defined recursively as

$\mathrm{ed}_{\mathscr{C}}(G)=\begin{cases}0&\text{if $G\in\mathscr{C}$,}\\\
1+\min\\{\mathrm{ed}_{\mathscr{C}}(G-v)\mid v\in V(G)\\}&\text{if
$G\not\in\mathscr{C}$ and $G$ is connected,}\\\
\max\\{\mathrm{ed}_{\mathscr{C}}(H)\mid\text{$H$ connected component of
$G$}\\}&\text{otherwise}.\end{cases}$

We denote by $\mathscr{C}_{d}$ the class of all graphs of maximum degree at
most $d$ and by $\mathscr{C}_{k,d}$ the class of all graphs with elimination
distance at most $k$ to $\mathscr{C}_{d}$. Note for instance that
$\mathrm{td}(G)=k$ if and only if $G\in\mathscr{C}_{k,0}$. We write
$\mathrm{ed}_{d}(G)$ for $\mathrm{ed}_{\mathscr{C}_{d}}(G)$.

######  Definition 2.1 (Definition 4.2 of [3]).

A tree order $\leq$ on G is an elimination order to degree $d$ for $G$ if for
every $v\in V(G)$ the set $S_{v}\coloneqq\\{u\in G\mid\\{u,v\\}\in
E(G),u\not\leq v$ and $v\not\leq u\\}$ satisfies either:

  1. $\bullet$

$S_{v}=\emptyset$ or

  2. $\bullet$

$v$ is $\leq$-maximal, $|S_{v}|\leq d$, and for all $u\in S_{v}$, we have
$\\{w\mid w<u\\}=\\{w\mid w<v\\}$.

A more general notion of elimination order to a class $\mathscr{C}$ was given
in the dissertation thesis of Bulian [2], which is however not needed in this
generality for our purpose.

######  Proposition 2.2 (Proposition 4.3 in [3]).

A graph $G$ satisfies $\mathrm{ed}_{d}(G)\leq k$ if, and only if, there exists
an elimination order to degree $d$ of depth $k$ for $G$.

The following lemma is easily proved by induction on $k$.

######  Lemma 2.3.

For every graph $G$ and elimination order $\leq$ to degree $d$ for $G$, we can
compute in polynomial time an elimination order $\preceq$ to degree $d$ for
$G$, with depth not larger than the depth of $\leq$, and with the additional
property that for every $v\in V(G)$, if $C,C^{\prime}$ are distinct connected
components of $G-V_{\preceq v}$ (or of $G$), then the vertices of $C$ and
$C^{\prime}$ are incomparable with respect to $\preceq$.

Let $G$ be a graph. A graph $H$ with vertex set $\\{v_{1},\ldots,v_{n}\\}$ is
a _minor_ of $G$, written $H\preceq G$, if there are connected and pairwise
vertex disjoint subgraphs $H_{1},\ldots,H_{n}\subseteq G$ such that if
$\\{v_{i},v_{j}\\}\in E(H)$, then there are $w_{i}\in V(H_{i})$ and $w_{j}\in
V(H_{j})$ such that $\\{w_{i},w_{j}\\}\in E(G)$. We call the subgraph $H_{i}$
the _branch set_ of the vertex $v_{i}$ in $G$. If $G$ is a graph and
$\mathcal{H}=\\{H_{1},\ldots,H_{n}\\}$ is a set of pairwise vertex disjoint
subgraphs of $G$, then the graph $H$ with vertex set
$\\{v_{1},\ldots,v_{n}\\}$ and edges $\\{v_{i},v_{j}\\}\in E(H)$ if and only
if there is an edge between a vertex of $H_{i}$ and a vertex of $H_{j}$ in
$G$, the _minor induced by $\mathcal{H}$_. If $\bigcup_{1\leq i\leq
n}V(H_{i})=V(G)$, then we call $\mathcal{H}$ a _minor model of $H$_ that
_subsumes all vertices_ of $G$.

We denote by $K_{t}$ the complete graph on $t$ vertices. We denote by
$G_{m,n}$ the grid with $m$ rows and $n$ columns, that is, the graph with
vertex set $\\{v_{i,j}\mid 1\leq i\leq m,1\leq j\leq n\\}$ and edges
$\\{v_{i,j},v_{i^{\prime},j^{\prime}}\\}$ for
$|i-i^{\prime}|+|j-j^{\prime}|=1$.

For our purpose we do not have to define the notion of treewidth formally. It
is sufficient to note that if a graph $G$ contains an $n\times n$ grid as a
minor, then $G$ has treewidth at least $n$ and vice versa, that large
treewidth forces a large grid minor, as stated in the next theorem.

######  Theorem 2.4 (Excluded Grid Theorem).

There exists a function $g$ such that for every integer $n\geq 1$, every graph
of treewidth at least $g(n)$ contains the $n\times n$ grid as a minor.
Furthermore, such a grid minor can be computed in polynomial time.

The theorem was first proved by Robertson and Seymour in [16]. Improved bounds
and corresponding efficient algorithms were subsequently obtained. We refer to
the work of Chuzhoy and Tan [5] for the currently best known bounds on the
function $g$ and further pointers to the literature concerning efficient
algorithms.

The second black-box we use is Courcelle’s Theorem, stating that we can test
MSO properties efficiently on graphs of bounded treewidth. We use standard
notation from logic and refer to the literature for all undefined notation,
see e.g. [13].

######  Theorem 2.5 (Coucelle’s Theorem [6]).

There exists a function $f$ such that for every MSO-sentence $\varphi$ and
every $n$-vertex graph $G$ of treewidth $t$ we can test whether
$G\models\varphi$ in time $f(|\varphi|,t)\cdot n$.

##  3 $K_{5}$-minor-free graphs of small degree.

In this section we show how to handle the case of $K_{5}$-minor free graphs of
small degree. We prove the following theorem.

######  Theorem 3.1.

There exists a computable function $f$ and constant $c$ such that for all
integers $k$ and $d$ and every $K_{5}$-minor-free $n$-vertex graph $G$ of
maximum degree at most $d+k$, we can test whether $G\in\mathscr{C}_{k,d}$ in
time $f(k,d)\cdot n^{c}$.

######  Definition 3.2.

Let $G$ be a $K_{5}$-minor-free graph and let $k,d\in\mathbb{N}$. Assume there
exists a minor model $\mathcal{G}_{m,m}=\\{H_{i,j}\mid 1\leq i,j\leq m\\}$
(for $m\geq 4k+5$) that subsumes all vertices of $G$ and that induces a
supergraph of the grid $G_{m,m}$. We call the branch set $H_{i,j}$ _$(k,d)$
-safe_ if $2k+3\leq i,j\leq m-2k-3$ and if $H_{i^{\prime},j^{\prime}}$
contains no vertex of degree at least $d+1$ (in $G$) for
$|i-i^{\prime}|,|j-j^{\prime}|\leq 2k+2$.

######  Lemma 3.3.

Let $G$ be a $K_{5}$-minor-free graph and let $k,d\in\mathbb{N}$. Assume there
exists a minor model $\mathcal{G}_{m,m}=\\{H_{i,j}\mid 1\leq i,j\leq m\\}$
(for $m\geq 4k+5$) that subsumes all vertices of $G$ and that induces a
supergraph of the grid $G_{m,m}$. Assume $H_{i,j}$ is $(k,d)$-safe. Let $a\in
V(H_{i,j})$, let $B\subseteq V(G)\setminus\\{a\\}$ with $|B|\leq k$ and let
$x,y\in V(G)\setminus(B\cup\\{a\\})$ be of degree at least $d+1$. Then $x$ and
$y$ are connected in $G-B$ if and only if $x$ and $y$ are connected in
$G-B-a$.

######  Proof 3.4.

Assume that $x$ and $y$ are connected in $G-B$ and let $P$ be a path
witnessing this. Assume that this path contains the vertex $a$.

We define sets $X_{\ell}$ for $0\leq\ell\leq k+1$ of branch sets as follows.
Let $X_{0}$ be the set consisting only of $H_{i,j}$ and for $\ell\geq 1$ let
$X_{\ell}$ be the set of all $H_{i^{\prime},j^{\prime}}$ with
$2\ell-1\leq|i-i^{\prime}|,|j-j^{\prime}|\leq 2\ell$ that do not already
belong to $X_{\ell-1}$. The sets $X_{\ell}$ are the borders (of thickness $2$)
of the $(4\ell+1)\times(4\ell+1)$-subgrid around $H_{i,j}$. Observe that the
vertices $x$ and $y$ do not belong to any of the $X_{\ell}$, as $H_{i,j}$ is
$(k,d)$-safe by assumption. For $0\leq\ell\leq k+1$ let $Y_{\ell}$ be the
subgraph of $G$ induced by the vertices of $X_{\ell}$.

We claim that for $1\leq\ell\leq k+1$, the sets $Y_{\ell}$ are connected sets
that separate $a$ from $x$ and analogously $a$ from $y$. Clearly, the
$Y_{\ell}$ are connected. Now observe that there is no edge between a vertex
of $\bigcup_{0\leq i\leq\ell-1}Y_{i}$ and a vertex of $G-\bigcup_{0\leq
i\leq\ell}Y_{i}$. The existence of such a connection would create a $K_{5}$
minor, see [7, Figure 7.10] or Figure 1. Hence, any path between $a$ and $x$
(or $y$) must pass through $Y_{\ell}$.

As $|B|\leq k$, there is one $Y_{\ell}$ with $1\leq\ell\leq k+1$ that does not
intersect $B$. Let $u$ be the first vertex that $P$ visits on $Y_{\ell}$ on
its way from $x$ to $a$ and let $v$ be the last vertex that $P$ visits on
$Y_{\ell}$ on its way from $a$ to $y$. As $Y_{\ell}$ is connected, we can
reroute the subpath between $u$ and $v$ through $Y_{\ell}$ and thereby
construct a path between $x$ and $y$ in $G-B-a$.

$H_{1}$$H_{2}$ Figure 1: Construction of a $K_{5}$ minor as soon as a branch
set (here $H_{1}$) connected to a branch set (here $H_{2}$) that is at
distance more than 2 in the grid [7, Figure 7.10]. The blue part marks the
“outer part” of the border of thickness $2$, the “inner part” decomposes into
a green, yellow and gray part.

Note that in the proof it is important that all vertices belong to some branch
set. Otherwise, we could have a vertex $x$ in $G$ that does not belong to any
branch set while being adjacent to $H_{i,j}$ and the whole argumentation would
fail.

######  Corollary 3.5.

Let $G$ be a $K_{5}$-minor-free graph and let $k,d\in\mathbb{N}$. Assume there
exists a minor model $\mathcal{G}_{m,m}=\\{H_{i,j}\mid 1\leq i,j\leq m\\}$
(for $m\geq 4k+5$) that subsumes all vertices of $G$ and that induces a
supergraph of the grid $G_{m,m}$. Assume $H_{i,j}$ is $(k,d)$-safe. Then every
vertex $a\in H_{i,j}$ is irrelevant, i.e., $G-a\in\mathscr{C}_{k,d}$ if and
only if $G\in\mathscr{C}_{k,d}$.

######  Proof 3.6.

Let $H\coloneqq G-a$. We have to prove that $H\in\mathscr{C}_{k,d}$ implies
$G\in\mathscr{C}_{k,d}$. Hence, assume $H\in\mathscr{C}_{k,d}$. Let $\leq_{H}$
be an elimination order to degree $d$ of height $k$ for $H$. We also assume
that $\leq_{H}$ satisfies the property of Lemma 2.3, that is, for every $v\in
V(G)$, if $C,C^{\prime}$ are distinct connected components of
$G-V_{\leq_{H}v}$, then the vertices of $C$ and $C^{\prime}$ are incomparable
with respect to $\leq_{H}$. Let $A_{0}$ be the connected component of $G$
containing $a$. Note that $A_{0}$ may break into multiple connected components
in $H=G-a$.

For $1\leq i\leq k$, we define inductively:

  * •

$m_{i}$ as the unique $\leq_{H}$-minimal element of $A_{i-1}\setminus\\{a\\}$
(if it exists) such that there exists a vertex $v$ with $m_{i}\leq_{H}v$ and
of degree at least $d+1$ in $H[A_{i-1}\setminus\\{a\\}]$. If there is no such
element $m_{i}$, the process stops.

Let us prove that there is at most one candidate for $m_{i}$. Assume that
there are incomparable $m$ and $m^{\prime}$ satisfying these conditions. This
means that there are vertices $v$ and $v^{\prime}$ of degree at least $d+1$ in
$A_{i-1}\setminus\\{a\\}$ (hence of degree at least $d+1$ in $G$) with
$m\leq_{H}v$ and $m^{\prime}\leq_{H}v^{\prime}$. Note that we have
$m\not\leq_{H}v^{\prime}$ because $\leq_{H}$ is a tree order. By Lemma 2.3, we
have that $v,v^{\prime}$ are both in $A_{i-1}\setminus\\{a\\}$, i.e. in the
connected component of $a$ in $G-\\{m_{1},\ldots,m_{i-1}\\}$ (it follows also
by induction that $\\{m_{1},\ldots,m_{i-1}\\}=V_{\leq_{H}m_{i-1}}$, hence we
may apply the lemma). Hence, $v$ and $v^{\prime}$ are connected in
$G-\\{m_{1},\ldots,m_{i-1}\\}$. With Lemma 3.3, we also have that $v$ and
$v^{\prime}$ are connected in $G-\\{a,m_{1},\ldots,m_{i-1}\\}$.

We take a witness path from $v$ to $v^{\prime}$. Since $m\leq_{H}v$ and
$m\not\leq_{H}v^{\prime}$, this path must contain two adjacent vertices $w$,
$w^{\prime}$ with $m\leq_{H}w$ and $m\not\leq_{H}w^{\prime}$. This contradicts
the fact that $\leq_{H}$ is an elimination order satisfying the property of
Lemma 2.3. Therefore, there is at most one possible such $m_{i}$.

We define

  * •

$T_{i}:=\\{v\in A_{i-1}\leavevmode\nobreak\ :\leavevmode\nobreak\
m_{i}\not\leq_{H}v\\}$

and

  * •

$A_{i}$ as the connected component of $a$ in $G-\\{m_{1},\ldots,m_{i}\\}$.
Note that again, $A_{i}-\\{a\\}$ may be a union of connected components in
$H-\\{m_{1},\ldots,m_{i}\\}$.

The processes stops after at most $k$ rounds. When the process stops, we have
defined $m_{i}$, $T_{i}$ and $A_{i}$ up to $i=\omega$, with $\omega\leq k$ and
every element in $A_{\omega}$ has degree at most $d$ in $H[A_{\omega}]$.

We then define the new order $\leq_{G}$ as follows:

  * •

for all $x,y$ other than $a$ and that are not in any of the $T_{i}$ nor in
$A_{\omega}$, we have $x\leq_{G}y$ if and only if $x\leq_{H}y$,

  * •

for all $x$ in $A_{\omega}\cup\bigcup\limits_{i\leq\omega}T_{i}$, we have
$m_{i}\leq_{G}x$ for all $i\leq\omega$, and

  * •

we set $m_{i}\leq_{G}a$ for all $i\leq\omega$.

Note that all the elements in $A_{\omega}$, and the $T_{i}$’s, together with
$a$ are $\leq_{G}$-maximal.

We now prove that this new order is indeed an elimination order to degree $d$
of depth $k$ for $G$. We have that $\leq_{G}$ is a tree order and that it has
height at most $k$. Let us now take a vertex $b$ and study $S_{b}$. Recall the
definition of $S_{b}$ from Definition 2.1. As we have two orders, we distinct
$S^{G}_{b}$ from $S^{H}_{b}$.

First, note that for $b=m_{i}$, we have
$S^{G}_{m_{i}}=S^{H}_{m_{i}}=\emptyset$. So we don’t have to check anything.

Then consider the case where $b$ is $a$, or a neighbor of $a$ different than
$m_{i}$ for all $i\leq\omega$. Then, by definition of the
$(A_{i})_{i\leq\omega}$, we have that $b\in A_{\omega}$. We also have that
there is no vertex in $A_{\omega}$ of degree at least $d+1$ in
$H[A_{\omega}]$. Hence $|S^{G}_{b}|\leq d$ and for any $v\in S^{G}_{b}$, we
have $\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w<_{G}v\\}=\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w<_{G}b\\}=(m_{i})_{i\leq\omega}$.

We continue with the case where $b$ is in one of the $T_{i}$. The uniqueness
of $m_{i}$ implies that $b$ has degree at most $d$ in $H[A_{i}]$. Hence
$|S^{G}_{b}|\leq d$ and for any $v\in S^{G}_{b}$, $v$ also belongs to $T_{i}$,
we then have that $\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w<_{G}v\\}=\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w<_{G}b\\}=(m_{i})_{i<\omega}$.

Finally, we look at the case where $b$ is not in $A_{\omega}$, is not $m_{i}$
nor in $T_{i}$ for any $i\leq\omega$. In this case, we have that $b$ cannot
have neighbors in $A_{\omega}$ nor any of the $T_{i}$ for $i\leq\omega$. To
see this, assume that there is a $v\in T_{i}$ neighbor to $b$. This implies
that $b$ is in $A_{i-1}$, as it is connected to $v$, the latter being in
$A_{i-1}$, which is the connected component of $a$ in
$G-\\{m_{1},\ldots,m_{i-1}\\}$. As $b\not\in T_{i}$, we have $m_{i}\leq_{H}b$
and $m_{i}\not\leq_{H}v$ which contradict that $\leq_{H}$ is an elimination
order. This contradiction also holds if $b$ has a neighbor in $A_{\omega}$ as
this would imply that $b\in A_{\omega}$.

Therefore, in this final case, $S^{G}_{b}=S^{H}_{b}$. This also holds for any
neighbor of $b$. Hence for any vertex $v$ in $S^{G}_{b}$ we have that
$\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w<_{G}b\\}=\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w<_{H}b\\}=\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w<_{H}v\\}=\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\ w<_{G}v\\}$.

To conclude, we have that $\leq_{G}$ is indeed an elimination order to degree
$d$ of height $k$ for $G$. This ends the proof that $a$ is irrelevant.

We can now prove the main theorem of this section.

######  Proof 3.7 (Proof of Theorem 3.1).

Let $k,d$ be two integers and $G$ be a connected $K_{5}$-minor free graph of
maximum degree at most $k+d$. We set
$h(k,d):=(4k+5)^{2}\cdot(k+d)^{2(k+d)}+4k+5$. Let $g$ be the function from
Theorem 2.4.

Case 1.

There are more than $(k+d)^{2(k+d)}$ vertices of degree at least $d+1$. We can
conclude that $G\not\in\mathscr{C}_{k,d}$. This is because the deletion of any
vertex $v$ can create at most $k+d$ connected components, and in each of them
there are at most $k+d$ vertices whose degree can decrease by the deletion of
$v$. Therefore by performing $k$ elimination rounds, there will still be a
vertex of degree at least $d+1$.

Case 2.

The treewidth of $G$ is bounded by $g(h(k,d))$. We use Courcelle’s Theorem
(Theorem 2.5) to decide whether $G\in\mathscr{C}_{k,d}$.

Case 3.

We are neither in case C1) nor in case C2). Since we are not in C2), we can
compute in polynomial time a grid minor of size $h(k,d)$. Furthermore we make
sure that the set of branch sets subsumes all vertices. As we are not in C1),
there are at most $(k+d)^{2(k+d)}$ vertices of degree at least $d+1$, and
therefore, at most $(4k+5)^{2}\cdot(k+d)^{2(k+d)}$ branch sets that are at
distance at most $2k+3$ to a vertex of degree at least $d+1$. As $h(k,d)$ is
large enough, there is a $(k,d)$-safe branch set which, by Corollary 3.5,
implies the existence of an irrelevant vertex. We iteratively eliminate
irrelevant vertices until we are in one of C1) or C2).

We now do a quick complexity analysis of the algorithm. Case 1 can be solved
in linear time. Case 2 requires time $f^{\prime}(k,g(h(k,d)))\cdot n$, where
$f^{\prime}$ is derived from the function of Theorem 2.5 and the MSO formula
defining membership in $\mathscr{C}_{k,d}$. The running time in Case 3 is
governed by the cost to compute a grid minor and takes time polynomial in $n$.
Therefore, the overall complexity is $f(k,d)\cdot n^{c}$ for a computable
function $f$ and constant $c$.

##  4 Computing elimination distance for $K_{5}$-minor free graphs

This section is devoted to the proof of our main result: Theorem 1.1. We fix
an instance $(G,k)$, where $G$ is $K_{5}$-minor-free.

We call a vertex $v\in V(G)$ with $d(v)\leq d$ a _blue_ vertex, a vertex $v\in
V(G)$ with $d<d(v)\leq k+d$ a _white_ vertex and a vertex $v\in V(G)$ with
$d(v)>k+d$ a _red_ vertex. We denote the set of red vertices by $R$, the set
of white vertices by $W$ and the set of blue vertices by $B$. All red vertices
have to be deleted in the elimination process, if this is not possible, then
$(G,k)$ is a negative instance. For all white vertices we have a choice of
whether we want to delete the vertex itself or some of its neighbors. Blue
vertices already satisfy the degree condition and will be only deleted if
their deletion creates useful components.

######  Lemma 4.1.

If $G\in\mathscr{C}_{k,d}$, then every path in $G$ contains at most $2^{k}-1$
red vertices.

######  Proof 4.2.

By deleting a red vertex we can only split the path into half. Hence, the
number of red vertices on a path is bounded by the function that is
recursively defined by $f(1)=1$ and $f(k+1)=2f(k)+1$. This defines the
function $f(k)=2^{k}-1$.

######  Lemma 4.3.

Let $C$ be a component of $G-R$. If $G\in\mathscr{C}_{k,d}$, then there are at
most $(k+d)^{k}$ red vertices that are neighbors of a vertex of $C$ in $G$.

######  Proof 4.4.

By induction on $k$, using the fact that the deletion of a white or blue
vertex can create at most $k+d$ components in $G$ and all red vertices have to
be deleted.

Having these two lemmas, we can now develop our algorithm. We first merge
every component $C$ of $G-R$ into a single vertex $v_{C}$ to obtain a new
graph $G^{\prime}$. If one of the new vertices $v_{C}$ has degree larger than
$(k+d)^{k}$, then we may reject the instance due to Lemma 4.3. We then compute
a depth-first-search of $G^{\prime}$. Observe that no two vertices $v_{C}$ and
$v_{C^{\prime}}$ for distinct components $C,C^{\prime}$ of $G-R$ are adjacent
in $G^{\prime}$, as otherwise $C$ and $C^{\prime}$ would not be separate
components. Hence, the search outputs and elimination order of $G^{\prime}$ of
depth at most $2^{k+1}-1$, or we may reject the instance due to Lemma 4.1. We
may hence assume in the following that $G^{\prime}$ has treedepth at most
$2^{k+1}-1$.

We can therefore test whether $G^{\prime}$ belongs to $\mathscr{C}_{k,d}$ via
the evaluation of an $\mathrm{MSO}$ sentence. However, since this graph has
been obtained by merging components of $G-R$, the deletion of a node $v_{C}$
in $G^{\prime}$ might require the deletion of the entire component $C$ of
$G-R$, which can have an arbitrary size. Fortunately, we do not have to delete
the entire component but only to “separate” its red neighbors and to “fix”
vertices of degree between $d+1$ and $d+k$ inside the component.

To do that, every non-red vertex $v_{C}$ of $G^{\prime}$ will be associated
with a type that describes the internal “connectivity pattern” of the $G-R$
component $C$ it corresponds to. This is possible thanks to Lemma 4.3, which
will help to bound the number of possible _connectivity patterns_ with the
rest of the graph. Testing whether a $G-R$ component satisfies some
connectivity pattern will be performed via an algorithm that resembles the one
that proves Theorem 3.1.

Let us now make this informal argumentation more concrete.

######  Definition 4.5.

Let $k$ and $d$ be two integers, and let $p\coloneqq(k+d)^{k}$. By a
partition, we mean a partition of the set $\\{1,\ldots,p\\}$.

A partition $P=(A_{i})_{i\leq\ell}$ _refines_ another partition
$P^{\prime}=(A^{\prime}_{i})_{i\leq\ell^{\prime}}$ if and only if for every
$i\leq\ell$ there is a $j\leq\ell^{\prime}$ such that $A_{i}\subseteq
A^{\prime}_{j}$.

For a pair of integers $(j,j^{\prime})$, we write $(j,j^{\prime})\in P$ if
there is a set $A_{i}$ that contains both $j$ and $j^{\prime}$. We refer to
such a pair of integers as being grouped in $P$, as opposed to being split or
separated in $P$. An integer $j$ that is not grouped with any other integer is
_isolated_ in $P$.

######  Definition 4.6.

Let $k$ and $d$ be two integers, and let $p\coloneqq(k+d)^{k}$. A
$(k,d)$-sequence is a sequence $(P_{i},L_{i},D_{i})_{i\leq\ell}$ for $\ell\leq
k$, where $P_{i}$ and $L_{i}$ are partitions of $\\{1,\ldots,p\\}$ and $D_{i}$
is a subset of $\\{1,\ldots,p\\}$.

Note in particular that there are a bounded number of $(k,d)$-sequences. Let
us write $H$ for some component of $G-R$, which according to Lemma 4.3 has at
most $p\coloneqq(k+d)^{k}$ red neighbors. We use $p$ unary predicates
$C_{1},\ldots,C_{p}$ to mark the vertices of $H$ that are neighbors of a red
vertex (the red vertices are not vertices of $H$). A $(k,d)$-sequence for $H$
will describe the elimination process from the point of view of $H$. The
partition $P_{i}$ will represent how the different unary predicates are linked
inside of $H$ at depth $i$ of the elimination process. The partition $L_{i}$
will represent how the unary predicates are connected outside of $H$ and the
subset $D_{i}$ is the list of predicates that correspond to red vertices that
have been deleted.

######  Definition 4.7.

Given integers $k,d$, $p\coloneqq(k+d)^{k}$, and a graph $H$ with maximum
degree $k+d$ with $p$ unary predicates $C_{1},\ldots C_{p}$, we say that $H$
satisfies a $(k,d)$-sequence $S=(P_{i},L_{i},D_{i})_{i\leq\ell}$, for some
$\ell\leq k$ if there is an elimination order $\leq_{o}$ to degree $d$ of
depth $\ell$ for $H$ that satisfies:

  * •

For every $1<i\leq\ell$ we have that $P_{i}$ (resp. $L_{i}$) refines $P_{i-1}$
(resp. $L_{i-1}$).

  * •

For every $1<i\leq\ell$ we have $D_{i-1}\subseteq D_{i}$.

  * •

For every $i\leq\ell$ and every $j\in D_{i}$, $j$ is isolated in $L_{i}$.

  * •

If two vertices $b,b^{\prime}$ satisfy $b,b^{\prime}\in C_{j}$ for some $j\leq
p$ and $b,b^{\prime}$ are incomparable in $\leq_{o}$, then either $b$ and
$b^{\prime}$ are $\leq_{o}$-maximal and $\\{w\mid w\leq_{o}b\\}=\\{w\mid
w\leq_{o}b^{\prime}\\}$, or there is no vertex $v$ and integer $i$ such that
$v\leq_{o}b$, $v\not\leq_{o}b^{\prime}$, and $v$ is at depth at most $i-1$,
where $j\not\in D_{i}$.

  * •

If two vertices $b,b^{\prime}$ satisfy $b\in C_{j_{1}}$, $b^{\prime}\in
C_{j_{2}}$ for some $j_{1},j_{2}\leq p$ and $b,b^{\prime}$ are incomparable in
$\leq_{o}$, then either $b$ and $b^{\prime}$ are $\leq_{o}$-maximal and
$\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w\leq_{o}b\\}=\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w\leq_{o}b^{\prime}\\}$, or there is no vertex $v$ and integer $i$ such that
$v\leq_{o}b$, $v\not\leq_{o}b^{\prime}$, $v$ is at depth at most $i-1$ and
$(j_{1},j_{2})\in L_{i}$.

  * •

For every $i\leq\ell$, two integers $(j_{1},j_{2})\in P_{i}$ if and only if
there is a path in $H$ from a vertex satisfying $C_{j_{1}}$ to a vertex
satisfying $C_{j_{2}}$ using only maximal vertices, and vertices at depth at
least $i$.

######  Example 4.8.

For example, fix $d=2$, $k>4$ and a component with only $3$ unary predicates
as depicted in Figure 2.

Figure 2: Example of graph and elimination orders to degree
$2$$1$$2$$c$$a$$3$$d$$b$$H$$C_{1}$$C_{2}$$C_{3}$$a$$b$$c$$d$$\leq_{1}$$a$$b$$c$$d$$\leq_{2}$

Consider now the sequences:
$S_{1}:=\bigg{(}\\{1,2,3\\};\\{1,2,3\\};\emptyset\bigg{)};\bigg{(}\big{(}\\{1\\},\\{2\\},\\{3\\}\big{)};\\{1,2,3\\};\emptyset\bigg{)};$
.
$\bigg{(}\big{(}\\{1\\},\\{2\\},\\{3\\}\big{)};\\{1,2,3\\};\emptyset\bigg{)};\bigg{(}\big{(}\\{1\\},\\{2\\},\\{3\\}\big{)};\\{1,2,3\\};\emptyset\bigg{)};$
$S_{2}:=\bigg{(}\\{1,2,3\\};\\{1,2,3\\};\emptyset\bigg{)};\bigg{(}\big{(}\\{1\\},\\{2\\},\\{3\\}\big{)};\\{1,2,3\\};\emptyset\bigg{)};\bigg{(}\big{(}\\{1\\},\\{2\\},\\{3\\}\big{)};\\{1,2,3\\};\emptyset\bigg{)};$
$S_{3}:=\bigg{(}\\{1,2,3\\};\\{1,2,3\\};\emptyset\bigg{)};\bigg{(}\big{(}\\{1\\},\\{2\\},\\{3\\}\big{)};\\{1,2,3\\};\emptyset\bigg{)};\Bigg{(}\big{(}\\{1\\},\\{2\\},\\{3\\}\big{)};\big{(}\\{1,2\\},\\{3\\}\big{)};\\{3\\}\bigg{)}$

Consider the graph in Figure 2. Sequence $S_{1}$ can be satisfied if at depth
$2$, we are left with no internal path between the different predicates
($1,2,3$ are split in $P_{2}$). This is achievable by removing $a$ and then
$b$. Also, the order has to be an elimination order to degree $2$ of depth at
most $4$. It is achieved by also removing $c$ and $d$. This corresponds to the
order $\leq_{1}$, which witnesses that $H$ satisfies sequence $S_{1}$.

Sequence $S_{2}$ also asks for the deletion of all paths between the different
predicates. However, we also need the order to be an elimination order to
degree $2$ of depth $3$. So in one round something must be done to $c$ and
$d$. This is impossible because $(2,3)$ are still grouped in $L_{3}$. For
example, the order $\leq_{2}$ is not a witness because there are vertices
$v\in C_{2}$, $u\in C_{3}$ with $c\leq_{2}v$, $c\not\leq_{2}u$, while $(2,3)$
are still grouped in $L_{3}$, and $c$ is at depth $2$, strictly less than $3$.

The third sequence is satisfied by $H$, as witness by $\leq_{2}$. This time,
$(2,3)$ are split in $L_{3}$.

######  Lemma 4.9.

For all integers $k,d$ and $(k,d)$-sequence $S$, there is an $\mathrm{MSO}$
formula $\Phi_{S}$ that expresses the fact that a graph $H$ satisfies $S$.

We simply have to redefine the notion of connectivity according to the
$(k,d)$-sequence $S$. Two vertices are considered adjacent at depth $i$ if
they share an edge, or if they are both in some unary predicate $C_{j}$ for
some $j$ that is not in $D_{i}$, or if they are respectively in some $C_{j}$,
$C_{j^{\prime}}$ with $j,j^{\prime}$ grouped in $L_{i}$. With this modified
notion of adjacency, which is expressible by MSO, also connectivity can easily
be expressed by an MSO formula. The precise $\mathrm{MSO}$ formula can be
found in Section A.1.

######  Lemma 4.10.

There is an algorithm that, given two integers $k,d$, a $(k,d)$-sequence $S$
and a $K_{5}$-minor-free $n$-vertex graph $H$ of degree at most $k+d$ with
$p\coloneqq(k+d)^{k}$ many unary predicates, tests whether $H$ satisfies $S$
in time $f(k,d)\cdot n^{c}$ for some computable function $f$ and constant $c$.

The proof of this lemma technical, however, the mains ideas and techniques are
already present in the proof of Theorem 3.1. The proof of the lemma can be
found in Section A.2.

######  Lemma 4.11.

Let $G$ be a graph and let $G^{\prime}$ be the graph obtained by merging all
components of $G-R$ into single vertices, which are labeled by the set of
$(k,d)$-sequences they satisfy. Then there exists an MSO-formula that is
satisfied in $G^{\prime}$ if and only if $G\in\mathscr{C}_{k,d}$.

Note that we assume that $G^{\prime}$ as already been computed, including all
of the labels. Note also that at this point we do not require $G$ to be
$K_{5}$-minor-free. To prove Lemma 4.11 we again define an appropriate notion
of connectivity, using for every non red vertex the different $P_{i}$ in the
$(k,d)$-sequences that this component satisfies. We then end up with a formula
that resembles the one witnessing that $\mathscr{C}_{k,d}$ is $\mathrm{MSO}$
definable. Details and formulas are presented in Section A.3.

We are now ready to prove the main result.

######  Proof 4.12 (Proof of Theorem 1.1).

Given integers $k,d$, and a $K_{5}$-minor free graph $G$, we replace it with a
graph $G^{\prime}$, with unary predicates. More precisely, we define one unary
predicate $\tau_{S}$ per $(k,d)$-sequence $S$. Every component of $G-R$ is
replaced in $G^{\prime}$ by a unique node that satisfies the predicate
$\tau_{S}$ for every sequence $S$ satisfied by this component.

By Lemma 4.10, we can test with an FPT algorithm whether a component satisfies
a given sequence $S$. We can therefore compute $G^{\prime}$ with an FPT
algorithm. By Lemma 4.1, $G^{\prime}$ has tree-depth at most $2^{k+1}-1$. By
Lemma 4.11, testing whether $G$ is in $\mathscr{C}_{k,d}$ can be tested with
an $\mathrm{MSO}$ formula on $G^{\prime}$, which is therefore computed by an
FPT algorithm.

##  5 Conclusion

Our proofs show that all difficulties for elimination distance to bounded
degree arise already in bounded degree graphs. We were not able to solve these
difficulties in general, but rely on the additional assumption that the input
graphs exclude $K_{5}$ as a minor. Hence the following problem remains open.

######  Open Problem 5.1.

Is there an algorithm that, on input integers $k,d,\Delta$ and an $n$-vertex
graph graph $G$ of maximum degree at most $\Delta$, tests whether $G$ belongs
to $\mathscr{C}_{k,d}$ in time $f(k,d,\Delta)\cdot n^{c}$ for some computable
function and constant $c$?

We conjecture that if such algorithm exists, it will also be possible to test
whether a graph $G$ satisfies some $(k,d)$-sequence. Hence we would be able to
remove assumption of excluding $K_{5}$ as a minor from Lemma 4.10. If this can
be done, then our proof of Theorem 1.1 follows. This yields the following
conjecture:

######  Conjecture 5.2.

The membership problem of $\mathscr{C}_{k,d}$ is FPT if and only if it is FPT
when restricted to classes of graphs with bounded degree.

## References

  * [1] Hans L Bodlaender, Jitender S Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, and Zsolt Tuza.  Rankings of graphs.  SIAM Journal on Discrete Mathematics, 11(1):168–181, 1998.

  * [2] Jannis Bulian.  Parameterized complexity of distances to sparse graph classes.  Technical report, University of Cambridge, Computer Laboratory, 2017.
  * [3] Jannis Bulian and Anuj Dawar.  Graph isomorphism parameterized by elimination distance to bounded degree.  Algorithmica, 75(2):363–382, 2016.
  * [4] Jannis Bulian and Anuj Dawar.  Fixed-parameter tractable distances to sparse graph classes.  Algorithmica, 79(1):139–158, 2017.
  * [5] Julia Chuzhoy and Zihan Tan.  Towards tight (er) bounds for the excluded grid theorem.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1445–1464. SIAM, 2019.
  * [6] Bruno Courcelle.  The monadic second-order logic of graphs. I. recognizable sets of finite graphs.  Information and computation, 85(1):12–75, 1990.
  * [7] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [8] Zdeněk Dvořák, Daniel Král, and Robin Thomas.  Testing first-order properties for subclasses of sparse graphs.  Journal of the ACM (JACM), 60(5):36, 2013.
  * [9] Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar.  Kernelization using structural parameters on sparse graph classes.  Journal of Computer and System Sciences, 84:219–242, 2017.
  * [10] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz.  Deciding first-order properties of nowhere dense graphs.  Journal of the ACM (JACM), 64(3):17, 2017.
  * [11] Jiong Guo, Falk Hüffner, and Rolf Niedermeier.  A structural view on parameterizing problems: Distance from triviality.  In International Workshop on Parameterized and Exact Computation, pages 162–173. Springer, 2004.
  * [12] Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse.  Elimination distances, blocking sets, and kernels for vertex cover.  In STACS, 2020.
  * [13] Leonid Libkin.  Elements of finite model theory.  Springer Science & Business Media, 2013.
  * [14] Jaroslav Nešetřil and Patrice Ossona De Mendez.  Sparsity: graphs, structures, and algorithms, volume 28.  Springer Science & Business Media, 2012.
  * [15] Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar.  A faster parameterized algorithm for treedepth.  In International Colloquium on Automata, Languages, and Programming, pages 931–942. Springer, 2014.
  * [16] Neil Robertson and Paul D Seymour.  Graph minors. V. excluding a planar graph.  Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986.
  * [17] Neil Robertson and PD Seymour.  Graph minors. XIII. the disjoint paths problem.  J. Combin. Theory Ser. B, 63:65–110, 1995.
  * [18] Dimitrios M Thilikos.  Graph minors and parameterized algorithm design.  In The Multivariate Algorithmic Revolution and Beyond, pages 228–256. Springer, 2012.

##  Appendix A Omitted proofs from Section 4

###  A.1 Proof of Lemma 4.9

Fix $k,d$ and a $(k,d)$-sequence $S=(P_{i},L_{i},D_{i})_{i\leq\ell}$. We write
$(j,j^{\prime})\in P_{i}$ (resp. in $L_{i}$) for a pair of integers if in the
partition $P_{i}$ (resp. $L_{i}$), we have that $j$ and $j^{\prime}$ are
grouped.

For every $0\leq i<\ell$, we define in $\mathrm{MSO}$ predicates
$\mathrm{Conn}_{S,i-1}$ or arity at least $2$ as follows:

$\displaystyle\mathrm{Conn}_{S,i-1}(x,y,\bar{z})=\;$ $\displaystyle\forall
X\Bigg{(}\bigwedge\limits_{z\in\bar{z}}\neg X(z)\wedge\forall w_{1}\forall
w_{2},\,X(w_{1})\wedge$ $\displaystyle\Big{(}\bigvee\limits_{(j,j^{\prime})\in
L_{i}}\big{(}C_{j}(w_{1})\wedge C_{j^{\prime}}(w_{2})\big{)}\vee$
$\displaystyle\bigvee\limits_{j\not\in D_{i}}\big{(}C_{j}(w_{1})\wedge
C_{j}(w_{2})\big{)}\vee E(w_{1},w_{2})\Big{)}\longrightarrow w_{2}\in
X\Bigg{)}$ $\displaystyle\longrightarrow(x\in X\longrightarrow y\in X)$

This means that $y$ is in the connected component of $x$ in $G-\\{\bar{z}\\}$,
where two vertices are considered adjacent if they share an edge, or if they
are both in some unary predicate $C_{j}$ for some $j$ that is not in $D_{i}$,
or if they are respectively in some $C_{j}$, $C_{j^{\prime}}$ with
$j,j^{\prime}$ grouped in $L_{i}$.

Then we have $\Phi_{S}=\Phi_{S,0}()$, where for every $i<\ell$ we have:

$\displaystyle\Phi_{S,i}(x_{1},\ldots,x_{i},$ $\displaystyle y_{1},\ldots
y_{i})=$ $\displaystyle\forall x_{i+1}\Bigg{(}\big{(}x_{i+1}\neq
y_{i}\wedge\mathrm{Conn}_{S,i-1}(x_{i+1},x_{i},y_{1},\ldots,y_{i-1})\big{)}\longrightarrow\exists
y_{i+1}\bigg{(}$ $\displaystyle\bigwedge\limits_{(j,j^{\prime})\not\in
P_{i+1}}\neg\Big{(}\exists vv^{\prime}\;C_{j}(v)\wedge
C_{j^{\prime}}(v^{\prime})\wedge\mathrm{Conn}_{S,i-1}(x_{i+1},v,y_{1},\ldots,y_{i-1})$
$\displaystyle\wedge\mathrm{Conn}_{S,i-1}(x_{i+1},v^{\prime},y_{1},\ldots,y_{i-1})\wedge\mathrm{Conn}_{i}(v,v^{\prime},y_{1},\ldots,y_{i})\Big{)}$
$\displaystyle\wedge\Phi_{i+1}(x_{1},\ldots,x_{i},x_{i+1},y_{1},\ldots
y_{i},y_{i+1})\bigg{)}\Bigg{)}$

Remember that $\mathrm{Conn}_{i}(v,v^{\prime},y_{1},\ldots,y_{i})$ means that
$v,v^{\prime}$ are connected (using only edges) in
$G-\\{y_{1},\ldots,y_{i}\\}$. We then conclude with:

$\displaystyle\Phi_{\ell}(x_{1},\ldots,x_{\ell},y_{1},\ldots y_{\ell})=\;$
$\displaystyle\forall w\bigg{(}\Big{(}w\neq
y_{\ell}\wedge\mathrm{Conn}_{S,\ell-1}(w,x_{\ell},y_{1},\ldots,y_{\ell-1})\Big{)}\longrightarrow$
$\displaystyle d^{G-\\{\bar{y}\\}}(w)\leq d\bigg{)}$

As we did not define $\mathrm{Conn}_{S,-1}(x)$, we make clear that:
$\Phi_{\ell}()=\forall v\,d^{G}(v)\leq d$ when $\ell=0$,

$\displaystyle\Phi_{0}()=\quad$ $\displaystyle\forall x_{1}\exists
y_{1}\Big{(}\bigwedge\limits_{(j,j^{\prime})\not\in P_{1}}\neg\big{(}\exists
vv^{\prime}\;C_{j}(v)\wedge
C_{j^{\prime}}(v^{\prime})\wedge\mathrm{Conn}_{S,0}(x_{1},v)$
$\displaystyle\wedge\mathrm{Conn}_{S,0}(x_{1},v^{\prime})\wedge\mathrm{Conn}_{1}(v,v^{\prime},y_{1})\big{)}\wedge\Phi_{1}(x_{1},y_{1})\Big{)}$

when $\ell>0$.

###  A.2 Proof of Lemma 4.10

The whole section is devoted to the proof of Lemma 4.10. Fix integers $k,d$, a
graph $G$ of degree at most $k+d$ and a $(k,d)$-sequence $S$. Let
$C_{1},\ldots,C_{p}$ be the unary predicates. Let
$h(k,d):=\big{(}(k+d)^{2(k+d)}+pk^{2}\big{)}(8k+5)^{2}$. Let $g$ be the
function from Theorem 2.4.

Case 1. There are more than $(k+d)^{2(k+d)}$ vertices of degree at least
$d+1$.

We can conclude that $G\not\in\mathscr{C}_{k,d}$ and therefore that $G$ does
not satisfy $S$. This is because the deletion of a node can create at most
$k+d$ connected components, and in each of them there are at most $k+d$ nodes
whose degree has decreased. Therefore by performing $k$ elimination rounds,
there will still be a node of degree at least $d+1$.

Case 2. The treewidth of $G$ is bounded by $g(h(k,d))$.

By Lemma 4.9, there is an $\mathrm{MSO}$ formula expressing that $G$ satisfies
$S$. We then use Courcelle’s Theorem (Theorem 2.5) to decide whether $G$
satisfies $S$.

Case 3. We are not in Case 1 and not in Case 2.

Since we are not in Case 2, we can compute in polynomial time a minor model
$\mathcal{G}_{m,m}=\\{H_{i,j}\mid 1\leq i,j\leq m\\}$ (for $m\geq h(k,d)$)
that subsumes all vertices of $G$ and that induces a supergraph of the grid
$G_{m,m}$.

As we are not in Case 1, there are at most $(k+d)^{2(k+d)}$ nodes of degree at
least $d+1$. We now make a disjunction on the number of branch sets that
contain a given unary predicate.

Case 3.1. Every predicate appears in at most $k^{2}$ branch sets.

We call the branch set $H_{i,j}$ _$(k,d)$ -semi-safe_ if $2k+3\leq i,j\leq
m-2k-3$ and if $H_{i^{\prime},j^{\prime}}$ contains no vertex of degree at
least $d+1$ (in $G$) nor a vertex satisfying any of the unary predicates for
$|i-i^{\prime}|,|j-j^{\prime}|\leq 2k+2$.

As there are only $(k+d)^{2(k+d)}$ branch sets that contain a vertex of degree
greater than $d+1$, only $p$ unary predicates, each of them appearing in at
most $k^{2}$ branch sets, there are at most
$\big{(}(k+d)^{2(k+d)}+pk^{2}\big{)}(4k+5)^{2}$ branch sets $H_{i,j}$ with
$2k+3\leq i,j\leq m-2k-3$ that are not safe. Since $h(k,d)$ is big enough,
there is a $(k,d)$-semi-safe branch set. We claim that any vertex in such
branch set is irrelevant.

This case is a straightforward adaptation of Lemma 3.3 and Corollary 3.5.

Case 3.2. There are two predicates $C_{j^{\prime}},C_{j}$ that both appear in
more than $k^{2}$ branch sets and that are separated in $P_{\ell}$. Remember
that we have a sequence $S:=(P_{i},L_{i},D_{i})_{i\leq\ell}$.

In this case, $G$ does not satisfy $S$. More precisely, after $k$ elimination
rounds, there is still a path from a vertex in $C_{j^{\prime}}$ to a vertex in
$C_{j}$ in $G$. It is because in $k$ rounds, there are $k$ lines and $k$
columns that contain all of the deletions. Since $C_{j}$ (resp.
$C_{j^{\prime}}$) appears in at least $k^{2}+1$ branch sets, there is a branch
set $B$ (resp. $B^{\prime}$) that contains a vertex of $C_{j}$ (resp.
$C_{j^{\prime}}$) and that is either in an untouched line, or an untouched
column. We can then create a path from $B$ to $B^{\prime}$.

Case 3.3. We are not in any of the cases above.

This means that all unary predicates that appear in more than $k^{2}$ branch
sets are grouped in $P_{\ell}$. We denote by $J$ the set of indices of these
unary predicates. In this case, we loosen the condition of safe branch set in
order to find an irrelevant vertex that might be close to a $C_{j}$ for $j\in
J$.

We call the branch set $H_{i_{1},i_{2}}$ _$(k,d)$ -semi-safe_ if $4k+3\leq
i_{1},i_{2}\leq m-4k-3$ and if $H_{i_{1}^{\prime},i_{2}^{\prime}}$ contains no
vertex of degree at least $d+1$ (in $G$) nor vertex satisfying the predicate
$C_{j}$ for $|i_{1}-i_{1}^{\prime}|,|i_{2}-i_{2}^{\prime}|\leq 4k+2$ and
$j\not\in J$.

As there are only $(k+d)^{2(k+d)}$ branch sets that contains a vertex of
degree greater than $d+1$, only $p-|J|$ unary predicates are concerned, each
of them appearing in at most $k^{2}$ branch sets, there are at most
$\big{(}(k+d)^{2(k+d)}+pk^{2}\big{)}(8k+5)^{2}$ branch sets $H_{i_{1},i_{2}}$
satisfying $4k+3\leq i_{1},i_{2}\leq m-4k-3$ that are not semi-safe. Since
$h(k,d)$ is big enough, there is a $(k,d)$-semi-safe branch set. We claim that
any vertex in such branch set is irrelevant.

In this case, we also have to adapt Lemma 3.3 and Corollary 3.5. This case is
however a little bit trickier than Case 3.1. All of what remains of this
section is devoted to this specific case 3.3.

######  Lemma A.1.

[Adaptation of Lemma 3.3]

Let $G$ be a $K_{5}$-minor-free graph, let $k,d\in\mathbb{N}$ and $S$ a
$(k,d)$-sequence. Assume there exists a minor model
$\mathcal{G}_{m,m}=\\{H_{i_{1},i_{2}}\mid 1\leq i_{1},i_{2}\leq m\\}$ (for
$m\geq 8k+7$) that subsumes all vertices of $G$ and that induces a supergraph
of the grid $G_{m,m}$. Assume $H_{i_{1},i_{2}}$ is $(k,d)$-semi-safe.

Let $a\in V(H_{i_{1},i_{2}})$, let $\bar{b}\subseteq V(G)\setminus\\{a\\}$
with $|\bar{b}|\leq k$, let $j_{1},j_{2}\leq p$ with $(j_{1},j_{2})\not\in
P_{\ell}$ and $j_{1}\not\in J$, and let $x,y\in V(G)\setminus(B\cup\\{a\\})$
with $x\in C_{j_{1}}$ and $y\in C_{j_{2}}$.

If $G\models\mathrm{Conn}_{k}(x,y,\bar{b})$, then there is a vertex
$y^{\prime}\in C_{j_{2}}$ such that
$G\models\mathrm{Conn}_{k+1}(x,y^{\prime},\bar{b},a)$.

Furthermore, for any two vertices $x$, $y$ of degree at least $d+1$, if
$G\models\mathrm{Conn}_{k}(x,y,\bar{b})$ then
$G\models\mathrm{Conn}_{k+1}(x,y,\bar{b},a)$.

######  Proof A.2.

We only prove the first part of Lemma A.1, the second part being exactly Lemma
3.3. To prove the first part, we distinguish two casses.

First, if $j_{2}\not\in J$. In this case, both $x$ and $y$ are at distance at
least $4k+3$ from $a$. We then use the same proof as for Lemma 3.3.

The second case, is when $j_{2}\in J$. In this case, it is possible that $y$
is close to $a$. It might even be possible that $a$ is the only neighbor of
$y$ and that therefore $x$ and $y$ are no longer connected in
$G-\\{\bar{b},a\\}$. Fortunately, we can find another $y^{\prime}\in
C_{j_{2}}$ that is unaffected by the deletion of $\bar{b}$ and $a$.

More formally, we define sets $X_{s}$ for $0\leq s\leq 2k+1$ of branch sets as
follows. Let $X_{0}$ be the set consisting only of $H_{i_{1},i_{2}}$ and for
$s\geq 1$ let $X_{s}$ be the set of all $H_{i-1^{\prime},i_{2}^{\prime}}$ with
$2s-1\leq|i_{1}-i_{1}^{\prime}|,|i_{2}-i_{2}^{\prime}|\leq 2s$. For
$0\leq\ell\leq k+1$ let $Y_{\ell}$ be the subgraph of $G$ induced by the
vertices of $X_{\ell}$.

Similarly to the proof of Lemma 3.3, we have that each $Y_{i}$ is a connected
separator of $a$ and $x$. Furthermore, for every $s>k$, there is a branch set
$B_{s}\in X_{s}$ that is in a column of the grid where no branch set
intersects $\bar{b}$. We then pick a vertex $y^{\prime}$ in $C_{j_{2}}$ that
is either in an column or a line of the grid where no branch set intersects
$\bar{b}$. This is possible as there are at least $k^{2}+1$ branch sets that
contains a vertex of $C_{j_{2}}$. There is a path from $y^{\prime}$ to any
vertex of any $B_{s}$ if $s>k$.

Finally, there is an $s$ with $k<s\leq 2k+1$ such that $Y_{s}$ does not
intersect $\bar{b}$. As $Y_{s}$ separates $x$ from $a$, the path from $x$ to
$a$ must go through $X_{s}$. Let $u$ be the first vertex of that path in
$Y_{s}$ and let $v$ a vertex of $B_{S}$.

As $y^{\prime}$ can reach $B_{s}$, and since $Y_{s}$ is connected, we can
reroute the subpath between $u$ and $v$ through $Y_{\ell}$ and thereby
construct a path between $x$ and $y$ in $G-B-a$. Therefore,
$G\models\mathrm{Conn}_{k+1}(x,y^{\prime},\bar{b},a)$.

######  Corollary A.3.

[Adaptation of Corollary 3.5] Let $G$ be $K_{5}$-minor free graph, $k,d$, be
integers, and $S$ a $(k,d)$-sequence. Assume there exists a minor model
$\mathcal{G}_{m,m}=\\{H_{i_{1},i_{2}}\mid 1\leq i_{1},i_{2}\leq m\\}$ (for
$m\geq 8k+7$) that subsumes all vertices of $G$ and that induces a supergraph
of the grid $G_{m,m}$. Assume $H_{i_{1},i_{2}}$ is $(k,d)$-semi-safe. Then any
vertex $a$ from $H_{i_{1},i_{2}}$ is irrelevant, meaning that $G-a$ satisfies
$S$ iff $G$ satisfies $S$.

######  Proof A.4.

Fix $k,d$, $S$, $G$ and an minor model $\mathcal{G}_{m,m}$ of $G$. Let $J$ the
set of $j\leq p$ such that $C_{j}$ appears in at least $k^{2}+1$ branch sets.
Let $a$ be a vertex from a $(k,d)$-semi-safe branch set and $H:=G-\\{a\\}$. We
only prove that if $H$ satisfies $S$ then $G$ satisfies $S$, the other
implication being trivial. Assume that $H$ satisfies $S$ and take $\leq_{H}$,
an elimination order to degree $d$ of height $k$ for $H$.

Let $A_{0}:=\\{b\in V\leavevmode\nobreak\ :\leavevmode\nobreak\
G\models\mathrm{Conn}_{S,0}(a,b)\\}$ the extended connected component of $a$
in $G$. Note that $A_{0}-\\{a\\}$ is a union of connected components in $H$
(using only the edge relation). Therefore by Lemma 2.3, $A_{0}$ is upward
closed, i.e. for every $b\in A_{0}-\\{a\\}$ and $b\leq_{H}c$, we have $c\in
A_{0}$. Then for every $1\leq i\leq k$, we define:

  * •

$m_{i}$ as the only $\leq_{H}$-minimal element of $A_{i-1}$ such that there
exists either a vertex $v$ with $m_{i}\leq_{H}v$ and $v$ has degree at least
$d+1$ in $H[A_{i-1}]$ or if there are $(j_{1},j_{2})\not\in P_{\ell}$ and two
vertices $v_{1}\in C_{j_{1}}$, $v_{2}\in C_{j_{2}}$ with $m_{i}\leq_{H}v_{1}$,
and $m_{i}\leq_{H}v_{2}$ (note that this implies that either $j_{1}$ or
$j_{2}$ is not in $J$). If there is no such element $m_{i}$, the process
stops.

Let us prove that there is at most one candidate for $m_{i}$. Assume that
there are incomparable $m$ and $m^{\prime}$ satisfying the conditions. It
means that there is a vertex $v$ (resp. $v^{\prime}$) either of degree at
least $d+1$ in $H[A_{i-1}]$ (hence of degree at least $d+1$ in $G$) or in
$C_{j}$ (resp. $C_{j^{\prime}}$) with $j\not\in J$ (resp. $j^{\prime}\not\in
J$), and with $m\leq_{H}v$ (resp. $m^{\prime}\leq_{H}v^{\prime}$). Note that
we have $m\not\leq_{H}v^{\prime}$ because $\leq_{H}$ is a tree order. As
$v,v^{\prime}$ are both in $A_{i-1}$, we have
$G\models\mathrm{Conn}_{i}(v,v^{\prime},m_{1},\ldots,m_{i-1})$ Hence with
Lemma A.1, we also have that
$G\models\mathrm{Conn}_{i}(v,v^{\prime},m_{1},\ldots,m_{i-1},a)$.

We take a witness string $(u_{0},\ldots,u_{\omega})$ with $v=u_{0}$,
$v^{\prime}=u_{\omega}$, and such that $(u_{i},u_{i+1})$ are either connected
by an edge, or both in some $C_{j}$ with $j\not\in D_{i}$, or respectively in
$C_{j},C_{j}^{\prime}$ with $j,j^{\prime}\in L_{i}$. Since $m\leq_{H}v$ and
$m\not\leq_{H}v^{\prime}$, there must be an $\alpha$ with
$m\leq_{H}u_{\alpha}$ and $m\not\leq_{H}u_{\alpha+1}$. As
$(u_{\alpha},u_{\alpha+1})$ are either adjacent in $G$, both in some $C_{j}$
with $j\not\in D_{i}$, or respectively in $C_{j},C_{j}^{\prime}$ with
$(j,j^{\prime})\in L_{i}$, this contradict the fact that $\leq_{H}$ witness
the fact that $H$ satisfies $S$.

Therefore, there is at most one possible such $m_{i}$.

  * •

$T_{i}:=\\{v\in A_{i-1}\leavevmode\nobreak\ :\leavevmode\nobreak\
m_{i}\not\leq_{H}v\\}$.

  * •

$A_{i}:=\\{b\in A_{i-1}\leavevmode\nobreak\ :\leavevmode\nobreak\
G\models\mathrm{Conn}_{S,i}(a,b,m_{1},\ldots,m_{i})\\}$. Note that again,
$A_{i}-\\{a\\}$ is a union of connected components in
$H-\\{m_{1},\ldots,m_{i}\\}$. Therefore by Lemma 2.3, we still have that for
every $b\in A_{i}-\\{a\\}$ and $b\leq_{H}c$, we have $c\in A_{0}$.

The processes stops after at most $\ell$ rounds.

When the process stops, we have then defined $m_{i}$, $T_{i}$ and $A_{i}$ up
to $i=\omega$, with $\omega\leq\ell$ and every element in $A_{\omega}$ has
degree at most $d$ in $H[A_{\omega}]$.

We then define the new order $\leq_{G}$ as follows:

  * •

for all $x,y$ other than $a$ and that are not in any of the $T_{i}$ nor in
$A_{\omega}$, we have $x\leq_{G}y$ iff $x\leq_{H}y$,

  * •

for all $x$ in $A_{\omega}\cup\bigcup\limits_{i\leq\omega}T_{i}$, we have
$m_{i}\leq_{G}x$ for all $i\leq\omega$, and

  * •

we set $m_{i}\leq_{G}a$ for all $i\leq\omega$.

Note that all the elements in the $T_{i}$’s together with $a$ are
$\leq_{G}$-maximal.

We now prove that this new order witnesses that $G$ satisfies $S$. Similarly
to the proof of Corollary 3.5. The order is still an elimination order of
height $\ell$ to degree $d$. We now look at the other rules from Definition
4.7 that makes $\leq_{G}$ a witness order. The two firsts rules do not depends
on $G$, so they are satisfied. We move to the next ones.

Rule 3: If two vertices $b,b^{\prime}$ satisfy $b\in C_{j}$, $b^{\prime}\in
C_{j}$ for some $j\leq h$ and $b,b^{\prime}$ are incomparable in $\leq_{o}$;
then either $b$ and $b^{\prime}$ are $\leq_{o}$ -maximal and
$\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w\leq_{o}b\\}=\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w\leq_{o}b^{\prime}\\}$, or there are no vertex $v$ and integer $i$ such that
$v\leq_{o}b$, $v\not\leq_{o}b^{\prime}$, and $v$ is at depth less than $i-1$
where $j\not\in D_{i}$.

Take two such $b,b^{\prime}$. If non of those are in $A_{\omega}$ nor in one
of the $T$, then neither their maximality status nor their predecessors in the
order have been impacted. If both are in $A_{\omega}$ or in one of the $T$,
the they are both maximal and have the same predecessors. Finally, if $b$ is
in $A_{\omega}$ or in one of the $T$ and not $b^{\prime}$. We distinguish two
case:

First, if $v\leq_{G}b$, $v\not\leq_{G}b^{\prime}$ and $v$ is at depth $i-1$.
Note that also $v\not\leq_{H}b^{\prime}$ and that $v=m_{i}$. Then if $b$ is in
$A_{\omega}$ or in one of the $T_{i^{\prime}}$ with $i^{\prime}>i$, then
already $v\leq_{H}b$ which contradicts that $\leq_{H}$ witnesses that $H$
satisfies $S$. The other possibility is that $b\in T_{i^{\prime}}$ with
$i^{\prime}\leq i$. This implies that $b\in A_{i^{\prime}-1}$ which also
implies that $b^{\prime}\in A_{i^{\prime}-1}$, since $i^{\prime}-1<i$ and
$j\not\in D_{i}$ (remember the definition of $\mathrm{Conn}_{S,i}$). As $b\in
T_{i^{\prime}}$, $m_{i^{\prime}}\not\leq_{H}b$ and since $b^{\prime}\not\in
T_{i^{\prime}}$, $m_{i^{\prime}}\leq_{H}b^{\prime}$. This again contradict
that $\leq_{H}$ witnesses that $H$ satisfies $S$.

Second case, $v\not\leq_{G}b$, $v\leq_{G}b^{\prime}$ and $v$ is at depth
$i-1$. This implies that $m_{i}\not\leq_{G}b^{\prime}$ as you can only be
bigger than one vertex of some fixed depth. We the conclude with the proof of
the first case.

Rule 4: Tf two vertices $b,b^{\prime}$ satisfy $b\in C{j_{1}}$, $b\in
C{j_{2}}$ for some $j_{1},j_{2}\leq h$ and $b,b^{\prime}$ are incomparable in
$\leq_{o}$; then either $b$ and $b^{\prime}$ are $\leq_{o}$-maximal and
$\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w\leq_{o}b\\}=\\{w\leavevmode\nobreak\ :\leavevmode\nobreak\
w\leq_{o}b^{\prime}\\}$, or there are no vertex $v$ and integer $i$ such that
$v\leq_{o}b,v\not\leq_{o}b^{\prime}$, and $v$ is at depth less than $i-1$,
where $(j_{1},j_{2})\not\in L_{i}$.

The proof that this rule is met in $\leq_{G}$ is the exact same than the one
for Rule 3. The only slight difference, is that when we say $b\in
A_{i^{\prime}-1}$ implies $b^{\prime}\in A_{i^{\prime}-1}$, we use another
property of $\mathrm{Conn}_{S,i}$ (the second line in the definition instead
of the third).

Rule 5: For every $i\leq\ell$, two integers $(j_{1},j_{2})\in P_{i}$ if and
only if there is a path in $G$ from a vertex satisfying $C_{j_{1}}$ to a
vertex satisfying $C_{j_{2}}$ using only maximal vertices, and vertices at
depth at least $i$.

Fix $i$, $j_{1},j_{2}$, such that there is a path from a vertex $x\in
C_{j_{1}}$ to a vertex $y\in C_{j_{2}}$, using only maximal vertices and
vertices at depth at least $i$. Therefore this path does not intersect
$\\{m_{1},\ldots m_{i}\\}$. Additionally, for any $T_{i^{\prime}}$ with
$i^{\prime}\leq i$, for two adjacent vertices $(v,v^{\prime})$ if $v\in
T_{i^{\prime}}$ and $v^{\prime}\not\in T_{i^{\prime}}$, then $v^{\prime}$ is
in $\\{m_{1},\ldots m_{i^{\prime}}\\}$. Furthermore, by definition of
$m_{i^{\prime}}$, it is not possible for both $x$ and $y$ to be in
$T_{i^{\prime}}$. Therefore the path does not intersect any of the
$T_{i^{\prime}}$ with $i^{\prime}\leq i$. If the path does not intersect
$A_{\omega}$, then this path already contradicts that $\leq_{H}$ witnesses
that $H$ satisfies $S$.

We can therefore assume that the path is included in $A_{i}$. We then apply
Lemma A.1, which tels us that there is a $y^{\prime}\in C_{j_{2}}$ such that
there is a path from $x$ to $y^{\prime}$ that does not contains $a$. We then
conclude that this path is also included in $A_{i}$, and contradicts that
$\leq_{H}$ witnesses that $H$ satisfies $S$.

This ends the prof that $a$ is irrelevant.

###  A.3 Proof of Lemma 4.11

In Lemma 4.11, we already assume that $G^{\prime}$ as been computed, including
all of the labels. Note that we do note require $G$ to be $K_{5}$-minor-free
anymore. The proof of this lemma is quite technical although rather simple on
a conceptual level. We simply need to carefully define the notion of connected
component in $G^{\prime}$ by looking at the type of the non red vertices
(sometimes called white-blue component vertices)

For every set $\\{S_{1},\ldots,S_{i}\\}$ where $S_{j}$ is either a
$k,d$-sequence, or the predicate $R$, we define a predicate
$\mathrm{NEXT}{i,S_{1}\ldots,S_{i}}(X_{1},X_{2},y_{1},\ldots,y_{i})$. It tests
whether a set $X_{2}$ suitably follows a set $X_{1}$, which intuitively means
that $X_{2}$ is a connected component in $X_{1}$.

More formally, we need that the following statements hold:

  * •

For every $y_{j}\in\\{y_{1},\ldots,y_{i}\\}$, $G\models\tau_{S_{j}}(y_{j})$ if
$S_{j}$ is a $(k,d)$-sequence.

  * •

For every $y_{j}\in\\{y_{1},\ldots,y_{i}\\}$, $G\models R(y_{j})$ if $S_{j}$
is the predicate $R$.

  * •

For every $j,j^{\prime}$, if $y_{j}=y_{j^{\prime}}$, then
$S_{j}=S_{j^{\prime}}$.

  * •

$X_{2}$ is connected.

  * •

$X_{2}\subseteq X_{1}$.

  * •

If $S_{j}$ is the predicate $R$, then $y_{j}\not\in X_{2}$.

Additionally, we also want that either:

  * •

$X_{2}$ is empty, or

  * •

$X_{2}$ is a singleton that only contains a white-blue component vertex, or

  * •

$X_{2}$ contain a red vertex and is the minimal set closed under the following
operation:

    * –

If $x,x^{\prime}$ are both red, adjacent, $x$ is in $X_{2}$, and $x^{\prime}$
is not in $\\{y_{1},\ldots,y_{i}\\}$ then we add $x^{\prime}$ to $X_{2}$.

    * –

If $x,x^{\prime}$ are adjacent, and $x$ only is red, we then add $x^{\prime}$
to $X_{2}$.

    * –

If $x,x^{\prime}$ are adjacent, $x$ is not red, is in $X_{2}$, and is not in
$\\{y_{1},\ldots,y_{i}\\}$, we then add $x^{\prime}$ to $X_{2}$.

    * –

If $x,x^{\prime}$ are adjacent, $x$ is not red, is in $X_{2}$, and is
$\\{y_{1},\ldots,y_{i}\\}$. We then let $s$ be the number of $y$ that are
equal to $x$. We then look at the sequence $S$ that correspond to such $y$,
and more precisely at it’s $s$th tuple: $(P_{s},L_{s},D_{s})$. Then if there
are $(j,j^{\prime})$ that are grouped in $P_{s}$, and if there is a vertex $w$
in $X_{2}$, such that $w$ is the $j$th red neighbor of $x$, and $x^{\prime}$
is the $j^{\prime}$th red neighbor of $x^{\prime}$, we then add $x^{\prime}$
to $X_{2}$.

The last operation checks within the white-blue component represented by $x$
in order to know which red neighbor are actually connected once $s$ many
elimination rounds have been performed within white-blue the component.

This is the end of the definition of
$\mathrm{NEXT}_{i,S_{1}\ldots,S_{i}}(X_{1},X_{2},y_{1},\ldots,y_{i})$, which
can be written in $\mathrm{MSO}$, but would hardly be human readable. We now
define the last $\mathrm{MSO}$ formulas, that actually express over $H$, that
$G$ is in $\mathscr{C}_{k,d}$. We define for every $0\leq i<k$ and set
$\\{S_{1},\ldots,S_{i}\\}$ the formulas
$\Psi_{i,S_{1},\ldots,S_{i}}(X,y_{1},\ldots,y_{i})$. It expresses that in
$G[X]$ as elimination distance at most $k-i$ to degree $d$, after picking
$y_{1},\ldots,y_{i}$ in the firsts $i$th rounds.

More formally, we want that for every $X_{2}$ such that
$G\models\mathrm{NEXT}_{i,S_{1}\ldots,S_{i}}(X,X_{2},y_{1},\ldots,y_{i})$,
either $X_{2}$ is empty, or contains a vertex $y_{i+1}$ such that:

  * •

$\Psi_{i+1,S_{1},\ldots,S_{i},S_{i+1}}(X_{2},y_{1},\ldots,y_{i},y_{i+1})$,
where $S_{i+1}$ is $R$ if $y_{i+1}$ is a red vertex.

  * •

$\Psi_{i+1,S_{1},\ldots,S_{i},S_{i+1}}(X_{2},y_{1},\ldots,y_{i},y_{i+1})$,
where $S_{i+1}=S_{j}$ if $y_{i+1}=y_{j}$.

  * •

$\bigvee\limits_{\\{S\leavevmode\nobreak\ :\leavevmode\nobreak\
G\models\tau_{S}(y_{i+1})\\}}\Psi_{i+1,S_{1},\ldots,S_{i},S}(X_{2},y_{1},\ldots,y_{i},y_{i+1})$
otherwise.

In addition, in the second ant third case we have the constraints that follow.

Let $S$ be the $(k,d)$-sequence associated to $y_{i+1}$, let $s$ be the number
of appearances of $y_{i+1}$ in $\\{y_{1},\ldots,y_{i+1}\\}$ (at least one).
And we look at the $s$th tuple $(P_{s},L_{s},D_{s})$ of $S$. (Or the last
tuple if $s$ exceed the length of $S$.) We check that:

  * •

$j\not\in D_{s}$ implies that the $j$th red neighbors of $y_{i+1}$ is not in
$X_{2}$.

  * •

$(j,j^{\prime})\not\in L_{s}$ implies that either the $j$th or the
$j^{\prime}$th red neighbors of $y_{i+1}$ is not in $X_{2}$; or that there are
no path in $X_{2}-\\{y_{i+1}\\}$ between these two red neighbors.

This ends the definition of
$\Psi_{i,S_{1},\ldots,S_{i}}(X,y_{1},\ldots,y_{i})$.

We conclude with $\Psi_{k,S_{1},\ldots,S_{k}}(X,y_{1},\ldots,y_{k})$ that
express that the only $X_{2}$ such that
$G\models\mathrm{NEXT}_{k,S_{1}\ldots,S_{k}}(X,X_{2},y_{1},\ldots,y_{k})$ is
either the empty set, or a singleton $\\{y\\}$, where $y$ is not a red vertex,
and $y$ appears at least $\ell$ many times in $\\{y_{1},\ldots,y_{k}\\}$,
where $\ell$ is the length of the sequence $S_{i}$ for $y=y_{i}$.

This concludes the proof of Lemma 4.11.