pair of $G \setminus B$ whose $\mathfrak{R}_5$-compass has treewidth at most $r_1$. Thus, since $r_3 = f_5(r_4, a_F - 1, a, d)$, the algorithm can apply Homogeneous of Proposition 3.5 with input $(r_4, a_F - 1, a, d, r_1, G, B, W_3, \mathfrak{R}_3)$ to obtain a flatness pair $(W_4, \mathfrak{R}_4)$ of $G \setminus B$ of height $r_4$ that is $d$-homogeneous with respect to $(\mathbb{B}_{<a_F})$ and is a $W^*$-tilt of $(W_3, \mathfrak{R}_3)$ for some subwall $W^*$ of $W_3$. According to Observation 5.3, $(W_4, \mathfrak{R}_4)$ is regular.

Let $S'$ be a $k$-elimination set of $G$ for $\text{exc}(\mathcal{F})$. Lemma 5.9 implies that there is a set $X_{S'} \supseteq S'$ such that $G \setminus X_{S'} \in \text{exc}(\mathcal{F})$ and $\text{bid}_{G\setminus A, W_2}(X_{S'}) \leq k(k+1)/2$.

Since $r_2 \geq f_9(a_F, s_F, k(k+1)/2)$, every subset of $B$ of size $a_F$ intersects $X_{S'}$ according to Proposition 3.7. Hence, $|B \setminus X_{S'}| \leq a_F - 1$.

Moreover, note that $(W_3, \mathfrak{R}_3)$ is a $W^i$-tilt of $(W_2, \mathfrak{R}_2)$, $(W_4, \mathfrak{R}_4)$ is a $W^*$-tilt of $(W_3, \mathfrak{R}_3)$, and $(W_4, \mathfrak{R}_4)$ is a flatness pair of $G \setminus B$ with $B \subseteq A$. Thus, given a $W_4$-canonical partition $Q_1$ of $G \setminus B$, there is a $W_2$-canonical partition $Q_2$ of $G \setminus A$ such that each internal bag of $Q_1$ is an internal bag of $Q_2$. Thus, $\text{bid}_{G\setminus B, W_4}(X_{S'}) \leq \text{bid}_{G\setminus A, W_2}(X_{S'})$.

Hence, the algorithm can apply Find-Irrelevant-Vertex of Proposition 3.6 with input $(k(k+1)/2, a_F - 1, G, B, W_4, \mathfrak{R}_4)$ and obtain a vertex $v$ such that, for any $k$-elimination set $S'$ of $G$ for $\text{exc}(\mathcal{F})$, $G \setminus X_{S'} \in \text{exc}(\mathcal{F})$ if and only if $G \setminus (X_{S'} \setminus v) \in \text{exc}(\mathcal{F})$. Thus, there is a $k$-elimination set of $G$ for $\text{exc}(\mathcal{F})$ if and only if there is a $k$-elimination set of $G \setminus v$ for $\text{exc}(\mathcal{F})$. It follows that $(G, k)$ and $(G \setminus v, k)$ are equivalent instances of $\mathcal{F}$-M-ELIMINATION DISTANCE.

Suppose now that $(G, k)$ is a no-instance. Note that as long as Proposition 3.4 outputs a flatness pair $(W_2, \mathfrak{R}_2)$, what follows in the proof of correctness works even if $(G, k)$ is a no-instance. Therefore, we will find an irrelevant vertex. Otherwise, we would have declared a no-instance beforehand. Thus, Theorem 8.1 follows.

**9. Elimination distance when excluding an apex-graph**

In the case where $\mathcal{F}$ contains an apex-graph, we obtain an alternative algorithm whose complexity is single-exponential in $k$ and cubic in $n$. The following theorem is a restatement of Theorem 1.3.

**THEOREM 9.1.** For every finite collection of graphs $\mathcal{F}$ that contains an apex-graph, there exists an algorithm that, given a graph $G$ and an integer $k$, decides whether $\text{ed}_{\text{exc}(\mathcal{F})}(G) \leq k$ in time $2^{k^{O(\ell_{\mathcal{F}}^{(1)})}} \cdot n^3$.

Contrary to the previous section, since $a_F = 1$, any vertex fulfilling the criteria of Proposition 3.7 belongs to every $k$-elimination set $S$ of the input graph for $\text{exc}(\mathcal{F})$. In the case where $\mathcal{F}$ contains an apex-graph in [70], a Step 3 similar to the one of Section 6 can be applied, where a vertex belonging to every $k$-apex set can be found. Hence, after running Step 3 $k$ times, a $k$-apex set is found and the algorithm stops. However, a $k$-elimination set may have size $\Omega(n)$,
so we may run Step 3 $\Omega(n)$ times. Since our Step 3 below runs in quadratic time, this gives the cubic dependence of this algorithm. Fortunately, since we apply Step 3, just like in Section 6 and contrary to Section 8, we manage to find a flatness pair along with an apex set whose size does not depend on $k$. Hence, when applying Proposition 3.5, we do not get a triple-exponential dependence on $k$ anymore for the size of the wall we need to find originally.

In order to remember the vertices that are found to belong to every $k$-elimination set, since they do not decrease $k$ like in Section 6, we need to distinguish them in the input. Hence, we actually give here an algorithm to solve a more general problem with annotations described in Subsection 9.1.

## 9.1 Generalization to annotated elimination distance

Contrary to the previous section, since $a_F = 1$, when applying Proposition 3.7, we find a vertex that belongs to every $k$-elimination set $S$. Such vertices are taken into account by considering the following generalization of $F$-M-ELIMINATION DISTANCE.

**ANNOTATED $F$-M-ELIMINATION DISTANCE**

**Input:** A graph $G$, a set $S_0 \subseteq V(G)$, and a non-negative integer $k$.

**Objective:** Find, if it exists, a $k$-elimination set $S$ of $G$ for the class $\text{exc}(\mathcal{F})$ such that $S_0 \subseteq S$.

$S_0$ is a set of annotated vertices that corresponds to the vertices identified as vertices of every $k$-elimination set $S$ while running the algorithm. Clearly, $F$-M-ELIMINATION DISTANCE is the particular case of ANNOTATED $F$-M-ELIMINATION DISTANCE when $S_0$ is empty.

In the following lemma, we generalize Theorem 7.1 to its “annotated” version. More precisely, we present a simple trick to reduce the above problem to its “unannotated” version while not changing the treewidth of the input graph so much.

**LEMMA 9.2.** Let $\mathcal{F}$ be a finite collection of graphs. There is an algorithm that, given a graph $G$, a set $S_0 \subseteq V(G)$, and two integers $k$ and $\text{tw}$ such that the treewidth of $G$ is bounded by $\text{tw}$, decides whether $(G, S_0, k)$ is a yes-instance of ANNOTATED $\mathcal{F}$-M-ELIMINATION DISTANCE in time $2^{O_{\ell_F}(\text{tw} \cdot k + \text{tw} \log \text{tw})} \cdot n$.

**PROOF.** Given a minor-closed graph class $\mathcal{G}$, let $C(\mathcal{G}) := \{G \mid \forall C \in \text{cc}(G), C \in \mathcal{G}\}$. Bulian and Dawar [16] showed that if $H \in \text{obs}(\mathcal{G})$ has $l$ connected components, then each graph $\bar{H}$ obtained from $H$ by adding $l-1$ edges to obtain a connected graph belongs to $\text{obs}(C(\mathcal{G}))$. Thus, let $H_F \in \text{obs}(C\text{exc}(\mathcal{F}))$ obtained in such a way. As said above, $H_F$ is connected.

Let $G$ be a graph of treewidth at most $\text{tw}$ and $S_0$ be a subset of $V(G)$. Let $G'$ be a graph obtained from $G$ by gluing a graph $H_v$ isomorphic to $H_F$ to each vertex $v$ of $S_0$, where $v$ is identified with an arbitrarily chosen vertex of $H_v$.
Let us show that (G, S₀, k) is a yes-instance of ANNOTATED *F*-M-ELIMINATION DISTANCE if and only if (G', k) is a yes-instance of obs(Cexc(*F*)))-M-ELIMINATION DISTANCE. If S₀ = ∅, the proof is trivial, so we suppose S₀ ≠ ∅.

Let (F', χ', R') be a Cexc(*F*))-elimination forest of *G'* of height at most *k* with associated *k*-elimination set *S'*. For each *v* ∈ S₀, the fact that *H*<sub>v</sub> ∉ Cexc(*F*)) implies that *V*(*H*<sub>v</sub>) ∩ *S'* ≠ ∅. Let *y* ∈ *V*(*F'* ) be the least common ancestor of χ'<sup>-1</sup>(*H*<sub>v</sub>) in *F'*. Since *H*<sub>v</sub> is connected, according to Lemma 4.1, *y* exists and belongs to χ'<sup>-1</sup>(*H*<sub>v</sub>). Moreover, since *V*(*H*<sub>v</sub>) ∩ *S'* ≠ ∅, *y* ∈ Int(*F'* , *R'* ).

Let (F'', χ'', R'') be the F-elimination forest of G obtained from (F', χ', R') as follows. For every v ∈ S₀ and every t ∈ χ''^{-1}(H_v \ v) if t ∈ Int(F', R'), remove t from F'' and add edges between the parent and the children of t and if t ∈ Leaf(F', R'), remove H_v \ v from χ''(t). If G[χ''(t)] is not connected, then we update F'' by replacing t by |cc(G[χ''(t)])| nodes, each one associated with a connected component of G[χ''(t)].

Thus, we have an $\mathcal{F}$-elimination forest of $G$ associated with a $k$-elimination set $S$ with $S_0 \subseteq S$ and with height at most $k$, implying that $(G, S_0, k)$ is a yes-instance of ANNOTATED $\mathcal{F}$-M-ELIMINATION DISTANCE.

Conversely, given an $\mathcal{F}$-elimination forest $(F, \chi, R)$ of $G$ of height at most $k$, and $S_0 \subseteq S := \chi(\mathrm{Int}(F, R))$, we can obtain a $\mathrm{obs}(C\mathrm{exc}(\mathcal{F}))$-elimination forest $(F', \chi', R')$ of $G'$ of height at most $k$ by adding to each node $\chi^{-1}(v)$ for $v \in S_0 \subseteq S$ a leaf associated with $H_v \setminus v \in C\mathrm{exc}(\mathcal{F})$. The height of $(F', \chi', R')$ is indeed still at most $k$. Therefore, $(G, S_0, k)$ is a yes-instance for ANNOTATED $\mathcal{F}$-M-ELIMINATION DISTANCE if and only if $(G', k)$ is a yes-instance for $\mathrm{obs}(C\mathrm{exc}(\mathcal{F}))$-M-ELIMINATION DISTANCE.

Thus, if we apply the algorithm of Theorem 7.1 to (G', k) to solve obs(Cexc(F)))-M-ELIMINATION DISTANCE, we solve ANNOTATED *F*-M-ELIMINATION DISTANCE on instance (G, S₀, k) in time 2<sup>O<sub>ℓ<sub>F</sub></sub>(tw(G')·k+tw(G') log tw(G'))</sup> ·|V(G')|.

Given a tree decomposition $\mathcal{T} = (\mathcal{T}, \beta)$ of $G$ of width $t$, we can obtain a tree decomposition $\mathcal{T}'$ of $G'$ of width at most $t + |V(H_{\mathcal{T}})|$ by adding a node $x_v$ for each $v \in S_0$ such that $\beta(v) = V(H_v)$, adjacent to a node $y$ of $\mathcal{T}$ such that $v \in \beta(y)$. Thus, $\mathrm{tw}(G') \le \mathrm{tw}(G) + |V(H_{\mathcal{T}})| = \mathrm{tw}(G) + O_{\ell_{\mathcal{T}}}(1)$. Moreover, $|V(G')| = |V(G)| + (|V(H_{\mathcal{T}})| - 1) \cdot |S_0| = O_{\ell_{\mathcal{T}}}(|V(G)|)$. Therefore, we can solve ANNOTATED *F*-M-ELIMINATION DISTANCE on instance $(G, S_0, k)$ in time $2^{O_{\ell_{\mathcal{T}}}(\mathrm{tw}\cdot k+\mathrm{tw}\log\mathrm{tw})} \cdot n$, and the lemma follows. $\blacksquare$

9.2 Description of the algorithm for F-M-ELIMINATION DISTANCE when a<sub>F</sub> = 1

We now describe the algorithm to solve ANNOTATED *F*-M-ELIMINATION DISTANCE, and hence *F*-M-ELIMINATION DISTANCE, when $a_F = 1$, i.e., when *F* contains an apex-graph. Note that, similarly to this algorithm, the one from Section 8 in the general case can also very easily be generalized to its “annotated” version. We stress that the reason for the better parametric dependence of this algorithm compared to the algorithm of Theorem 1.2 is that we pursue homogeneous flat walls where homogeneity is asked for subsets of size *not* depending on *k*.
We define the following constants.

$$
\begin{align*}
a &= f_3(s_F), & q &= f_{10}(1, s_F, k(k+1)/2), \\
p &= f_{11}(1, s_F, k(k+1)/2), & l &= (q-1) \cdot (k+a), \\
d &= f_8(a, l_F) & r_4 &= f_7(a, l_F, 3, k(k+1)/2), \\
r_3 &= f_5(r_4, a, a, d), & t &= f_4(s_F) \cdot r_3, \\
r_2 &= \text{odd}(t+3), & r'_2 &= \text{odd}(\max\{f_9(1, s_F, k(k+1)/2), f_{13}(l+1, r_2, p)\}), \\
r'_1 &= \text{odd}(f_2(s_F) \cdot r'_2), & r_1 &= \text{odd}(r'_1 + k).
\end{align*}
$$

Note that $r_4 = O_{\ell_F}(k^2)$, $r_3, r_2 = O_{\ell_F}(k^{2c})$, and $r'_2, r'_1, r_1 = O_{\ell_F}(k^{2c+7/2})$, where $c = f_6(a, a, d) = O_{\ell_F}(1)$. Recall from Subsection 2.2 that we assume that $G$ has $O_{s_F}(k\sqrt{\log k} \cdot n)$ edges.

The input of this algorithm is a graph $G$, a set $S_0 \subseteq V(G)$, and an integer $k$.

**Step 1.** Run the algorithm Find-Wall-Ed from Proposition 3.1 with input $(G \setminus S_0, r_1, k)$ and, in time $2^{O_{\ell_F}(r_1^2+k^2)} \cdot n = 2^{O_{\ell_F}(k^{4c+7})} \cdot n$,

— either report a no-instance, or

— conclude that $\text{tw}(G \setminus S_0) \le f_1(s_F) \cdot r_1 + k$ and solve ANNOTATED $F$-M-ELIMINATION DISTANCE with input $(G, S_0, f_1(s_F) \cdot r_1 + 2k, k)$ in time $2^{O_{\ell_F}((r_1+k) \cdot k+(r_1+k) \log(r_1+k)))} \cdot n = 2^{O_{\ell_F}(k^{2c+9/2})} \cdot n$ using the algorithm of Lemma 9.2, or

— obtain an $r_1$-wall $W_1$ of $G$.

If the output of Proposition 3.1 is a wall $W_1$, consider all the $(r_1 \choose r_2)^2 = 2^{O_{\ell_F}(k^{2c} \log k)} r_2$-subwalls of $W_1$ and for each one of them, say $W_2$, let $W_2^*$ be the central $(r_2 - 2)$-subwall of $W_2$ and let $D_{W_2}$ be the graph obtained from $G \setminus S_0$ after removing the perimeter of $W_2$ and taking the connected component containing $W_2^*$. Run the algorithm Clique-or-twFlat of Proposition 3.4 with input $(D_{W_2}, r_3, s_F)$. This takes time $2^{O_{\ell_F}(r_3^2)} \cdot n = 2^{O_{\ell_F}(k^{4c})} \cdot n$. If for one of these subwalls the result is a set $A$ of size at most $a$ and a regular flatness pair $(W_3, \mathfrak{R}_3)$ of $D_{W_2} \setminus A$ of height $r_3$ whose $\mathfrak{R}_3$-compass has treewidth at most $t$, then we proceed to Step 2, otherwise proceed to Step 3.

**Step 2.** We obtain a 7-tuple $\mathfrak{R}'_3$ by adding all vertices of $G \setminus (S_0 \cup V(\text{Compass}_{\mathfrak{R}_3}(W_3)))$ to the set in the first coordinate of $\mathfrak{R}_3$, such that $(W_3, \mathfrak{R}'_3)$ is a regular flatness pair of $G \setminus (S_0 \cup A)$.

We first apply the algorithm Homogeneous of Proposition 3.5 with input $(r_4, a, a, d, t, G \setminus S_0, A, W_3, \mathfrak{R}'_3)$, which outputs, in time $2^{O_{\ell_F}(r_4 \log r_4+t \log t)} \cdot (n+m) = 2^{O_{\ell_F}(k^{2c} \log k)} \cdot n$ a flatness pair $(W_4, \mathfrak{R}_4)$ of $G \setminus (S_0 \cup A)$ of height $r_4$ that is $d$-homogeneous with respect to $2^A$ and is a $W^*$-tilt of $(W_3, \mathfrak{R}'_3)$ for some subwall $W'$ of $W$. At this point, we stress that the reason for the better parametric dependence of this algorithm compared to the previous one comes from the fact that the third input parameter $a$ in Homogeneous does not depend of $k$. We apply the algorithm Find-Irrelevant-Vertex of Proposition 3.6 with input $(k(k+1)/2, a, G \setminus S_0, A, W_4, \mathfrak{R}_4)$, which outputs, in time $O_{s_F}(k\sqrt{\log k} \cdot n)$, a vertex $v$ such that $(G, S_0, k)$ and $(G \setminus v, S_0, k)$ are equivalent
instances of ANNOTATED *F*-M-ELIMINATION DISTANCE. Then the algorithm runs recursively on the equivalent instance (G \ v, S₀, k).

**Step 3.** Consider all the $r'_2$-subwalls of $W_1$, which are $(\binom{r_1}{r'_2})^2 = 2^{O_{\ell_F}(k^{2c+7/2} \log k)}$ many, and for each of them, say $W'_2$, compute its canonical partition $Q$. Then, contract each bag $Q$ of $Q$ to a single vertex $v_Q$, remove the vertices $v_Q$ where $Q$ is not a *p*-internal bag of $Q$, and add a new vertex $v_{\text{all}}$ and make it adjacent to all remaining $v_Q$'s. In the resulting graph $G'$, for every vertex $y$ of $(G \setminus S_0) \setminus V(W'_2)$, check, in time $O(q \cdot m) = O_{\ell_F}(k^7 \sqrt{\log k} \cdot n)$, using a flow augmentation algorithm [20], whether there are *q* internally vertex-disjoint paths from $v_{\text{all}}$ to $y$. Let $\tilde{A}$ be the set of such *y*'s.

If $\tilde{A} = \emptyset$, then report a no-instance.

If $1 \le |\tilde{A}| \le k + a$, then each vertex of $\tilde{A}$ should intersect every $k$-elimination set $S$ of $G$ for $\text{exc}(\mathcal{F})$. The algorithm runs recursively on $(G, S_0 \cup \tilde{A}, k)$.

If, for every wall, $|\tilde{A}| > k + a$, then report that $(G, S_0, k)$ is a no-instance of ANNOTATED *F*-M-ELIMINATION DISTANCE.

After Step 2, the size of $G$ decreases by one, so Step 2 can be applied at most $n$ times. After Step 3, the size of $S_0$ increases by at least one, so Step 3 can also be applied at most $n$ times. Note that, if $S_0 = V(G)$, then $\text{tw}(G \setminus S_0) = 0$, so the algorithm stops. Thus, the algorithm finishes. Notice also that Step 3, when applied, takes time $2^{O_{\ell_F}(k^{2c+7/2} \log k)} \cdot n^2$, because we apply a flow algorithm for each of the $2^{O_{\ell_F}(k^{2c+7/2} \log k)} r'_2$-subwalls and for each vertex of $G$. Since Step 1 and Step 2 run in time $2^{O_{\ell_F}(k^{4c+7})} \cdot n$ and $2^{O_{\ell_F}(k^{2c} \log k)} \cdot n$, respectively, and both may be applied at most $n$ times, the claimed time complexity follows: the algorithm runs in time $2^{O_{\ell_F}(k^{4c+7})} \cdot n^3$.

## 9.3 Correctness of the algorithm

Let $(G, S_0, k)$ be a yes-instance and let $S$ be a $k$-elimination set of $G$ for $\text{exc}(\mathcal{F})$ with $S_0 \subseteq S$. By running Proposition 3.1 with input $(G \setminus S_0, r_1, k)$, the algorithm should either get a report that $\text{tw}(G \setminus S_0) \le f_1(s_F) \cdot r_1 + k$ or find an $r_1$-wall.

If $\text{tw}(G \setminus S_0) \le f_1(s_F) \cdot r_1 + k$, then since $S_0 \subseteq S$, $\text{tw}(G \setminus S) \le f_1(s_F) \cdot r_1 + k$. Hence, according to Lemma 4.6, $\text{tw}(G) \le f_1(s_F) \cdot r_1 + 2k$.

Otherwise, let $W_1$ be an $r_1$-wall of $G \setminus S_0$. According to Lemma 5.8, since $r_1 \ge r'_1 + k$, there is an $r'_1$-subwall $W'_1$ of $W_1$ that is a subwall of $G \setminus S$. Let $H$ be the connected component of $G \setminus S$ containing $W_2$. The fact that $H$ belongs to $\text{exc}(\mathcal{F})$ implies that it has no $K_{S_F}$-minor. Therefore, by Proposition 3.3, since $r'_1 \ge f_2(s_F) \cdot r'_2$, there is a set $B \subseteq V(H)$, with $|B| \le a$, and a flatness pair $(W'_2, \mathfrak{R}'_2)$ of $H \setminus B$ of height $r'_2$.

Let $Q$ be the canonical partition of $W'_2$. Let $G'$ be the graph obtained after contracting every bag $Q$ of $Q$ to a single vertex $v_Q$, removing the vertices $v_Q$ where $Q$ is not a $p$-internal bag of $Q$,
and adding a new vertex $v_{\text{all}}$ and making it adjacent to all remaining $v_Q$'s. Let $\tilde{A}$ be the set of vertices $y$ of $G \setminus V(W'_2)$ such that there are $q$ internally vertex-disjoint paths from $v_{\text{all}}$ to $y$ in $G'$. Since $S$ is a $k$-elimination set of $G$ for $\text{exc}(\mathcal{F})$, there is a set $P \subseteq S$ of size at most $k$ so that $(L, R) := (V(G) \setminus V(H), V(H) \cup P)$ is a separation of $G$ with $P = L \cap R$.

Note that $\tilde{A} \subseteq P \cup B$. To show this, we first prove that, for every $y \notin P \cup B$, the maximum number of internally vertex-disjoint paths from $v_{\text{all}}$ to $y$ in $G'$ is less than $q$. Indeed, if $y$ is a vertex in $(V(G) \setminus V(H)) \setminus P$, then every path from $y$ to a vertex of $W'_2$ intersects $P$. Therefore, there are at most $k < q$ internally vertex-disjoint paths from $v_{\text{all}}$ to such a $y \in (V(G) \setminus V(H)) \setminus P$ in $G'$. If $y \in V(H) \setminus B$, then we distinguish two cases. First, if $y$ is a vertex in the $\mathcal{R}'_2$-compass of $W'_2$, there are at most $k+a$ such paths that intersect the set $P \cup B$ and at most four paths that do not intersect $P \cup B$ (in the graph $G' \setminus (P \cup B)$) due to the flatness of $W'_2$. If $y$ is in $V(H)$ but not a vertex in the $\mathcal{R}'_2$-compass of $W'_2$, then, since by the definition of flatness pairs the perimeter of $W'_2$ together with the set $P \cup B$ separate $y$ from the $\mathcal{R}'_2$-compass of $W'_2$, every collection of internally vertex-disjoint paths from $v_{\text{all}}$ to $y$ in $G'$ should intersect the set $\{v_{Q_{\text{ext}}}\} \cup P \cup B$, where $Q_{\text{ext}}$ is the external bag of $Q$. Therefore, in all cases, if $y \notin P \cup B$, the maximum number of internally vertex-disjoint paths from $v_{\text{all}}$ to $y$ in $G'$ is at most $k+a+4 < q$. Therefore, $y \notin \tilde{A}$. Hence, $|\tilde{A}| \le k+a$.

Let $\mathcal{R}''_2$ be the 7-tuple obtained by adding all vertices of $((G \setminus S_0) \setminus P) \setminus H$ to the set in the first coordinate of $\mathcal{R}'_2$. Notice that since every path between $G \setminus H$ and $H$ intersects $P$, $(W'_2, \mathcal{R}''_2)$ is a flatness pair of $G \setminus (P \cup B)$.

If $\tilde{A} = \emptyset$, then let $\tilde{Q}$ be an enhancement of $Q$ on $G \setminus (P \cup B)$. No vertex of $(P \cup B) \setminus S_0$ is adjacent to vertices of at least $q$ $p$-internal bags of $\tilde{Q}$. This means that the $p$-internal bags of $\tilde{Q}$ that contain vertices adjacent to some vertex of $P \cup B$ are at most $(q-1) \cdot (k+a) = l$.

Consider a family $\mathcal{W} = \{W^1, \dots, W^{l+1}\}$ of $l+1$ $r_2$-subwalls of $W'_2$ such that for every $i \in [l+1]$, $\bigcup \text{influence}_{\mathcal{R}''_2}(W^i)$ is a subgraph of $\bigcup \{Q \mid Q \text{ is a } p\text{-internal bag of } \tilde{Q}\}$ and for every $i, j \in [l+1]$, with $i \neq j$, there is no internal bag of $\tilde{Q}$ that contains vertices of both $V(\bigcup \text{influence}_{\mathcal{R}''_2}(W^i))$ and $V(\bigcup \text{influence}_{\mathcal{R}''_2}(W^j))$. The existence of $\mathcal{W}$ follows from Proposition 5.6 and the fact that $r'_2 \ge f_{13}(l+1, r_2, p)$.

The fact that the $p$-internal bags of $\tilde{Q}$ that contain vertices adjacent to some vertex of $(P \cup B) \setminus S_0$ are at most $l$ implies that there exists an $i \in [l+1]$ such that no vertex of $V(\bigcup \text{influence}_{\mathcal{R}''_2}(W^i))$ is adjacent, in $G$, to a vertex in $(P \cup B) \setminus S_0$.

Let $W_2 := W^i$, let $W_2^*$ be the central $(r_2-2)$-subwall of $W_2$, and let $D_{W_2}$ be the graph obtained from $G \setminus S_0$ after removing the perimeter of $W_2$ and taking the connected component containing $W_2^*$. Any path going from a vertex in $H$ to a vertex in $G \setminus H$ intersects $P$. Thus, $D_{W_2} \subseteq H$ and therefore, $K_{S_{\mathcal{F}}}$ is not a minor of $D_{W_2}$. Moreover, $W_2^*$ is a wall of $D_{W_2}$ of height $r_2 - 2 \ge t+1$, so $\text{tw}(D_{W_2}) > t = f_4(S_{\mathcal{F}}) \cdot r_3$. Therefore, since, if the algorithm runs Clique-or-twFlat of Proposition 3.4 with input $(D_{W_2}, r_3, S_{\mathcal{F}})$, it should obtain a set $A$ of size at most $a$ and a regular
flatness pair ($W_3$, $\mathbb{R}_3$) of $D_{W_2} \setminus A$ of height $r_3$ whose $\mathbb{R}_3$-compass has treewidth at most $t$. Hence, the algorithm then runs Step 2.

If $\tilde{A} \neq \emptyset$, then recall that for every $y \in \tilde{A}$, $y$ has $q$ internally vertex-disjoint paths $P_1, \dots, P_q$ to different $p$-internal bags $Q_1, \dots, Q_q$ of $Q$ in $G$. Hence, there is an enhancement $\tilde{Q}_y$ of $Q$ on $G \setminus (P \cup B)$ such that $P_i$ belongs to the bag $\tilde{Q}_i$ that extends $Q_i$ for $i \in [q]$. Therefore, $y$ is adjacent to vertices of at least $q$ $p$-internal bags of $\tilde{Q}_y$. Let $S'$ be a $k$-elimination set of $G$ for $\text{exc}(\mathcal{F})$. According to Lemma 5.9, there is a set $X_{S'} \subseteq V(G)$ such that $G \setminus X_{S'} \in \text{exc}(\mathcal{F})$ and $\text{bid}_{G \setminus (P \cup B), W'_2}(X_{S'}) \le k(k+1)/2$. Therefore, $y \in X_{S'}$ due to Proposition 3.7 and the fact that $r'_2 \ge f_9(1, s_F, k(k+1)/2)$. Let $C_{S'} := G \setminus X_{S'}$. Recall that $y$ is adjacent to $q > k(k+1)/2$ $p$-internal bags of $\tilde{Q}_y$. However, $\text{bid}_{\tilde{Q}_y}(X_{S'}) \le \text{bid}_{G \setminus (P \cup B), W'_2}(X_{S'}) \le k(k+1)/2$. Therefore, $y$ is adjacent to $C_{S'}$, so $y \in S'$. Since for every $y \in \tilde{A}$, for every $k$-elimination set $S'$, we have $y \in S'$, it implies that $\tilde{A}$ is included in every $k$-elimination set of $G$ for $\text{exc}(\mathcal{F})$. Hence, if the algorithm runs Step 3, it then recursively runs on the equivalent instance $(G, S_0 \cup \tilde{A}, k)$.

We do not suppose that $(G, k)$ is a yes-instance anymore. Let us show the correctness of Step 2. Suppose that we obtained the wanted flatness pair $(W_3, \mathbb{R}_3)$ in Step 1. We obtain a 7-tuple $\mathbb{R}'_3$ by adding all vertices of $G \setminus (S_0 \cup V(\text{Compass}_{\mathbb{R}_3}(W_3)))$ to the set in the first coordinate of $\mathbb{R}_3$. Since $(W_3, \mathbb{R}_3)$ is a regular flatness pair of $D_{W_3} \setminus A$ whose $\mathbb{R}_3$-compass has treewidth at most $t$ and since the vertices added in $\mathbb{R}'_3$ are only adjacent to the perimeter of $W^i$, it follows that $(W_3, \mathbb{R}'_3)$ is a regular flatness pair of $G \setminus (S_0 \cup A)$ whose $\mathbb{R}'_3$-compass has treewidth at most $t$.

If the algorithm applies the algorithm *Homogeneous of Proposition 3.5 with $(r_4, a, a, d, t, G \setminus S_0, A, W_3, \mathbb{R}'_3)$* as input, it obtains a flatness pair $(W_4, \mathbb{R}_4)$ of $G \setminus (S_0 \cup A)$ of height $r_4$ that is $d$-homogeneous with respect to $2^A$ and is a $W^*$-tilt of $(W_3, \mathbb{R}'_3)$ for some subwall $W'$ of $W$. According to Observation 5.3, $(W_4, \mathbb{R}_4)$ is regular.

Lemma 5.9 implies that for every $k$-elimination set $S' \supseteq S_0$, there is a set $X_{S'} \supseteq S'$ with $\text{bid}_{G \setminus (S_0 \cup A), W_4}(X_{S'}) \le k(k+1)/2$ and $G \setminus X_{S'} \in \text{exc}(\mathcal{F})$. We have that $|A \setminus X| \le |A| \le a$, so the algorithm can apply *Find-Irrelevant-Vertex of Proposition 3.6 with input $(k(k+1)/2, a, G \setminus S_0, A, W_4, \mathbb{R}_4)$* to obtain a vertex $v$ such that for every $k$-elimination set $S' \supseteq S_0$, $G \setminus X_{S'} \in \text{exc}(\mathcal{F})$ if and only if $G \setminus (X_{S'} \setminus v) \in \text{exc}(\mathcal{F})$. It follows that $(G, S_0, k)$ and $(G \setminus v, S_0, k)$ are equivalent instances of *ANNOTATED $\mathcal{F}$-M-ELIMINATION DISTANCE*.

Suppose now that $(G, S_0, k)$ is a no-instance. In Step 1, the algorithm either reports a no-instance or finds a wall. In the latter case, the algorithm either goes to Step 2 or to Step 3. If it runs Step 2, the previous paragraph justifies that the algorithm finds a vertex $v$ such that $(G \setminus v, S_0, k)$ is a no-instance. If the algorithm runs Step 3, then it either reports a no-instance or recursively runs on the instance $(G \setminus y, S_0 \cup \tilde{A}, k)$. If $(G \setminus y, S_0 \cup \tilde{A}, k)$ is yes-instance, then so is $(G, k)$. Thus, $(G \setminus y, S_0 \cup \tilde{A}, k)$ is a no-instance. Hence, the algorithm always report a no-instance. Therefore, Theorem 9.1 follows.
**Constructing the elimination ordering.** Notice that the results of Theorem 8.1 and Theorem 9.1 solve the decision version of ELIMINATION DISTANCE TO $\mathcal{G}$. Using the dynamic programming algorithm of Section 7, we may find a $k$-elimination set $X$ certifying that $\mathrm{ed}_{\mathcal{G}}(\mathcal{G}) \le k$. One may further determine, from $X$, the way the elimination ordering is applied on the vertices of $X$ as follows. Let $\mathrm{torso}(G, X)$ be the graph obtained from $G[X]$ if, for every connected component $C$ of $G-X$, we make adjacent all pairs of vertices in $N_{\mathcal{G}}(V(C))$ in $G[X]$. Then we know that $\mathrm{td}(\mathrm{torso}(G, X)) \le k$ and the required elimination ordering is the same as the one for $\mathrm{torso}(G, X)$, which can be computed by the algorithm of [61] in time $2^{O(k^2)} \cdot n$.

**10. Bounding the obstructions of $\mathcal{E}_k(\mathrm{exc}(\mathcal{F}))**

In this section, we prove the following result that provides an upper bound on the size of the
graphs in $\mathrm{obs}(\mathcal{E}_k(\mathrm{exc}(\mathcal{F})))$. The following theorem is a reformulation of Theorem 1.5.

**THEOREM 10.1.** Let $\mathcal{F}$ be a non-empty finite collection of non-empty graphs and $k$ be a positive integer. Every graph in $\mathrm{obs}(\mathcal{E}_k(\mathrm{exc}(\mathcal{F})))$ has $2^{2^{2^2k^{O_{\ell_F}(1)}}}$ vertices. In the particular case when $\mathcal{F}$ contains an apex-graph, every graph in $\mathrm{obs}(\mathcal{E}_k(\mathrm{exc}(\mathcal{F})))$ has $2^{2^k}$ vertices.

Recall that when $\mathcal{F} = \{K_1\} = \mathrm{obs}(G_0)$, it is known [22] that every graph in $\mathrm{obs}(\mathcal{E}_k(G_0))$ has at most $2^{2^{k-1}}$ vertices.

Theorem 10.1 implies that one can construct an algorithm that receives as input $\mathrm{obs}(\mathrm{exc}(\mathcal{F}))$ and $k$, and outputs $\mathrm{obs}(\mathcal{E}_k(\mathrm{exc}(\mathcal{F})))$. This is done by enumerating all graphs on at most $f(k)$ vertices, where $f(k)$ is the bound on the number of vertices given by Theorem 10.1, and filtering out those that are members of $\mathcal{E}_k(\mathrm{exc}(\mathcal{F}))$ and taking those that are minor-minimal in what is left. The running time of the algorithm can be bounded by $O(2^{2^{2^2k^{O_{\ell_F}(1)}}} \cdot n^2)$ in the general case and by $O(2^{2^k} \cdot n^2)$ if $\mathcal{F}$ contains an apex-graph.

Note that this brute-force algorithm can be used to solve $\mathcal{F}$-M-ELIMINATION DISTANCE. Indeed, to solve $\mathcal{F}$-M-ELIMINATION DISTANCE, we can compute $\mathrm{obs}(\mathcal{E}_k(\mathrm{exc}(\mathcal{F})))$ and then check whether there is a graph in $\mathrm{obs}(\mathcal{E}_k(\mathrm{exc}(\mathcal{F})))$ that is a minor of the input graph. Of course, this algorithm is much less efficient than the ones presented in the previous sections.

The rest of the section is structured as follows: in Subsection 10.1 we bound the treewidth of a minor-minimal obstruction of $\mathcal{E}_k(\mathrm{exc}(\mathcal{F}))$, while in Subsection 10.2 we bound the size of a minor-minimal obstruction of $\mathcal{E}_k(\mathrm{exc}(\mathcal{F}))$ of small treewidth. This immediately implies Theorem 10.1.
**10.1 Bounding the treewidth of an obstruction**

In this subsection we aim to prove an upper bound on the treewidth of a minor-minimal
obstruction of $\mathcal{E}_k(\mathrm{exc}(\mathcal{F}))$.

**LEMMA 10.2.** Let $\mathcal{F}$ be a finite collection of graphs. There exists a function $f_{15} : \mathbb{N}^3 \to \mathbb{N}$ such that if $G \in \mathrm{obs}(\mathcal{E}_k(\mathrm{exc}(\mathcal{F})))$, then $\mathrm{tw}(G) \le f_{15}(k, a_{\mathcal{F}}, s_{\mathcal{F}})$. Moreover, $f_{15}(k, a, s) = 2^{\log(k \cdot c) \cdot 2^{k^{a-1.2O(s^2 \log s)}}}$, where $a = a_{\mathcal{F}}$, $s = s_{\mathcal{F}}$, and $c$ is a constant depending on $\ell_{\mathcal{F}}$.

Note that when $a_{\mathcal{F}} = 1$, $f_{15}(k, 1, s) = O_{\ell_{\mathcal{F}}}(k^{2^{2O(s^2 \log s)}})$.

**PROOF.** For simplicity, we use $s, a$, and $\ell$ instead of $s_{\mathcal{F}}, a_{\mathcal{F}}$, and $\ell_{\mathcal{F}}$, respectively. We set

$$
\begin{align*}
b &= f_3(s) + k + 1, & d &= f_8(a - 1, \ell), \\
r_4 &= f_7(a - 1, \ell, 3, k(k+1)/2), & r_3 &= f_5(r_4, a - 1, b, d), \\
x &= f_{10}(a, s, k(k+1)/2), & p &= f_{11}(a, s, k(k+1)/2), \\
l &= (x - 1) \cdot b, & r_2 &= \mathrm{odd}(\max\{f_{13}(l+1, r_3, p), f_9(a, s, k(k+1)/2)\}), \\
r_1 &= f_2(s) \cdot r_2, \text{ and} & w &= f_{12}(s) \cdot r_1 + k + 1.
\end{align*}
$$

It is easy to verify that $w = 2^{\log(k \cdot c) \cdot 2^{k^{a-1.2O(s^2 \log s)}}}$.

Suppose towards a contradiction that $\mathrm{tw}(G) > w$. Since $G \in \mathrm{obs}(\mathcal{E}_k(\mathrm{exc}(\mathcal{F})))$, for each $v \in V(G)$, $G \setminus v \in \mathcal{E}_k(\mathrm{exc}(\mathcal{F}))$. Therefore, there exists a $(k+1)$-elimination set $S$ of $G$ for $\mathrm{exc}(\mathcal{F})$. Thus, for each $C \in \mathrm{cc}(G \setminus S)$, $C \in \mathrm{exc}(\mathcal{F})$. According to Lemma 4.6, $\mathrm{tw}(G \setminus S) > w-k-1 = f_{12}(s) \cdot r_1$, so there is $C \in \mathrm{cc}(G \setminus S)$, such that $\mathrm{tw}(C) > f_{12}(s) \cdot r_1$. Moreover, $K_S$ is not a minor of $C$. Therefore, according to Proposition 5.1, $C$ contains an $r_1$-wall $W_1$.

Since $r_1 = f_2(s) \cdot r_2$, by Proposition 3.3, there is a set $A \subseteq V(C)$ of size at most $f_3(s)$ and a flatness pair $(W_2, \mathfrak{R}_2)$ of $C \setminus A$ of height $r_2$ such that $W_2$ is a tilt of a subwall of $W_1$. Due to Proposition 5.5, there is a regular flatness pair $(W'_2, \mathfrak{R}'_2)$ of $C \setminus A$ of height $r_2$.

Since $S$ is a $(k+1)$-elimination set of $G$ for $\mathrm{exc}(\mathcal{F})$ and $C \in \mathrm{cc}(G \setminus S)$, there exists a set $P \subseteq S$ of size at most $k+1$ such that $(L, R) := (V(G) \setminus V(C), V(C) \cup P)$ is a separation of $G$ with $L \cap R = P$. Thus, if $\mathfrak{R}''_2$ is the 7-tuple obtained by adding the vertices of $G \setminus (C \cup P)$ to the set in the first coordinate of $\mathfrak{R}'_2$, $(W'_2, \mathfrak{R}''_2)$ is a regular flatness pair of $G \setminus (A \cup P)$ of height $r_2$.

Let $\tilde{Q}$ be a $W'_2$-canonical partition of $G \setminus (A \cup P)$. Let $B$ be the set of vertices of $A \cup P$ adjacent to vertices of at least $x$ $p$-internal bags of $\tilde{Q}$. Let $\mathcal{W} = \{W^1, \dots, W^{l+1}\}$ be a family of $l+1$ $r_3$-subwalls of $W'_2$ such that for every $i \in [l+1]$, $\mathbf{U}influence_{\mathfrak{R}''_2}(W^i)$ is a subgraph of $\mathbf{U}\{Q \mid Q \text{ is a } p\text{-internal bag of } \tilde{Q}\}$ and for every $i, j \in [l+1]$ with $i \neq j$, there is no internal bag $Q \in \tilde{Q}$ that contains vertices of both $V(\mathbf{U}influence_{\mathfrak{R}''_2}(W^i))$ and $V(\mathbf{U}influence_{\mathfrak{R}''_2}(W^j))$. The existence of $\mathcal{W}$ follows from the fact that $r_2 \ge f_{13}(l+1, r_3, p)$ and Proposition 5.6. Notice that the set $N_G((A \cup P) \setminus B)$ intersects the vertex set of at most $(x-1) \cdot |(A \cup P) \setminus B| \le l$ $p$-internal
bags of $\tilde{Q}$. Thus, there is an $i \in [l+1]$ such that no vertex in $(A \cup P) \setminus B$ is adjacent to vertices of $\bigcup \text{influence}_{\mathfrak{R}_2''}(W^i)$.

Let $(W_3, \mathfrak{R}_3)$ be a $W^i$-tilt of $(W'_2, \mathfrak{R}_2'')$. Since $|B| \le |A \cup P| \le f_3(s) + k + 1 = b$ and $r_3 = f_5(r_4, b, a-1, d)$, by Proposition 3.5, there is a flatness pair $(W_4, \mathfrak{R}_4)$ of $G \setminus B$ of height $r_4$ that is $d$-homogeneous with respect to $\binom{B}{<a}$ and is a tilt of a subwall of $(W_3, \mathfrak{R}_3)$. By Observation 5.2 and Observation 5.3, $(W_4, \mathfrak{R}_4)$ is regular.

Recall that $(W_3, \mathfrak{R}_3)$ is a $W^i$-tilt of $(W'_2, \mathfrak{R}_2'')$, $(W_4, \mathfrak{R}_4)$ is a tilt of a subwall of $(W_3, \mathfrak{R}_3)$, and $(W_4, \mathfrak{R}_4)$ is a flatness pair of $G \setminus B$ with $B \subseteq A \cup P$. Thus, given a $W_4$-canonical partition $\tilde{Q}_1$ of $G \setminus B$, there is a $W'_2$-canonical partition $\tilde{Q}_2$ of $G \setminus (A \cup P)$ such that each internal bag of $\tilde{Q}_1$ is contained in an internal bag of $\tilde{Q}_2$. Therefore, for every set $X \subseteq V(G)$, $\text{bid}_{G\setminus B, W_4}(X) \le \text{bid}_{G\setminus (A \cup P), W'_2}(X)$.

Moreover, since $r_2 \ge f_9(a, s, k(k+1)/2)$, according to Proposition 3.7, every subset of $B$ of size $a$ intersects every set $X \subseteq V(G)$ such that $G \setminus X \in \text{exc}(\mathcal{F})$ and $\text{bid}_{G\setminus(A \cup P), W'_2}(X) \le k(k+1)/2$. Hence, for any such $X$, $|B \setminus X| < a$.

Thus, according to Proposition 3.6, since $r_4 = f_7(a-1, l, 3, k(k+1)/2)$, it holds that there is a vertex $v$ such that, for every set $X \subseteq V(G)$ with $G \setminus X \in \text{exc}(\mathcal{F})$ and $\text{bid}_{G\setminus B, W_4}(X) \le k(k+1)/2$, $G \setminus X \in \text{exc}(\mathcal{F})$ if and only if $G \setminus (X \setminus v) \in \text{exc}(\mathcal{F})$.

Lemma 5.9 implies that for any $k$-elimination set $S'$ of $G \setminus v$ for $\text{exc}(\mathcal{F})$, there is a set $X \supseteq S'$ such that $G \setminus X \in \text{exc}(\mathcal{F})$ and $\text{bid}_{G\setminus(A \cup P), W'_2}(X) \le k(k+1)/2$. Since $\text{bid}_{G\setminus B, W_4}(X) \le \text{bid}_{G\setminus(A \cup P), W'_2}(X)$, we also have that $\text{bid}_{G\setminus B, W_4}(X) \le k(k+1)/2$. Thus, $G \setminus X \in \text{exc}(\mathcal{F})$ if and only if $G \setminus (X \setminus v) \in \text{exc}(\mathcal{F})$ and $G \in \mathcal{E}_k(\text{exc}(\mathcal{F}))$ if and only if $G \setminus v \in \mathcal{E}_k(\text{exc}(\mathcal{F}))$. However, since $G \in \text{obs}(\mathcal{E}_k(\text{exc}(\mathcal{F})))$, it holds that $G \notin \mathcal{E}_k(\text{exc}(\mathcal{F}))$ and $G \setminus v \in \mathcal{E}_k(\text{exc}(\mathcal{F}))$, a contradiction. ■

## 10.2 Bounding the size of an obstruction of small treewidth

In order to bound the size of an obstruction of small treewidth, we first present some additional notions on tree decompositions on bounded graphs.

**Treewidth of bounded graphs.** Let $G = (G, B, \rho)$ be a bounded graph. A tree decomposition of $G$ is a rooted tree decomposition $(\Gamma, \beta, r)$ of $G$ such that $\beta(r) = B$. The width of $(\Gamma, \beta, r)$ is the width of $(\Gamma, \beta)$. The treewidth of a bounded graph $G$ is the minimum width over all its tree decompositions and is denoted by $\text{tw}(G)$. A *nice tree decomposition* of $G$ is a tree decomposition $(\Gamma, \beta, r)$ of $G$ that is also a nice tree decomposition of $G$ rooted at $r$.

Let $G = (G, B, \rho)$ be a bounded graph and $\mathcal{T} = (\Gamma, \beta, r)$ be a tree decomposition of $G$. Notice that if $a, b \in V(\Gamma)$ and $a \in \text{Anc}_{\Gamma,r}(b)$, then $G_b$ is a subgraph of $G_a$. We define the $t_q$-bounded graph $\bar{G}_q = (\bar{G}_q, \beta(q), \rho_q)$, where $\bar{G}_q = G \setminus (V(G_q) \setminus \beta(q))$. Notice that $G_q$ and $\bar{G}_q$ are compatible and $G_q \oplus \bar{G}_q = G$.

**Linked tree decompositions.** Our next step is to use a special type of tree decompositions, namely *linked tree decompositions*, defined by Robertson and Seymour in [62]. Thomas in [71]
proved that every graph G admits a linked tree decomposition of width $tw(G)$ (see also [14, 24]). By combining the result of [71] and [18, Lemma 4], we can consider tree decompositions as asserted in the following result.

**PROPOSITION 10.3 ([18]).** Let $t \in \mathbb{N}_{\ge 1}$. For every bounded graph $G = (G, B, \rho)$ of treewidth $t-1$, there exists a tree decomposition $(T, \beta, r)$ of $G$ of width $t-1$ such that

1. $(T, r)$ is a binary tree,

2. for every $a, b \in V(T)$ where $a$ is a child of $b$ in $(T, r)$, if $|\beta(a)| = |\beta(b)|$ then $G_a$ is a proper subgraph of $G_b$, i.e., $|V(G_a)| < |V(G_b)|$,

3. for every $s \in \mathbb{N}$ and every pair $u_1, u_2 \in V(T)$, where $u_1 \in \text{Anc}_{T,r}(u_2)$ and $|\beta(u_1)| = |\beta(u_2)|$, either there is an internal vertex $w$ of $u_1Tu_2$ such that $|\beta(w)| < s$, or there exists a collection of $s$ vertex-disjoint paths in $G$ between $\beta(u_1)$ and $\beta(u_2)$, and

4. $|V(G)| \le t \cdot |V(T)|$.

In fact, linked tree decompositions are defined as the tree decompositions satisfying only property (3) [62, 71]. In our proofs, we will need the extra properties (1), (2), and (4) that are provided by [18, Lemma 4].

We bound the size of a minor-minimal obstruction of small treewidth in Lemma 10.5. To do so, we need the following result (for a proof see e.g. [31, Lemma 14]).

**PROPOSITION 10.4 ([31]).** Let $r, m \in \mathbb{N}_{\ge 1}$ and $w$ be a word of length $m^r$ over the alphabet $[r]$. Then there is a number $k \in [r]$ and a subword $u$ of $w$ such that $u$ contains only numbers not smaller than $k$ and $u$ contains the number $k$ at least $m$ times.

We are now ready to prove Lemma 10.5. The idea is to apply the technique of Lagergren [52] combined with the bound on the number of characteristics provided in Subsection 7.6. The proof of Lemma 10.5 is very similar to the corresponding proof in [69] for $\text{obs}(\mathcal{A}_k(\text{exc}(\mathcal{F})))$.

**LEMMA 10.5.** Let $\mathcal{F}$ be a finite non-trivial collection of graphs. There exists a function $f_{16}: \mathbb{N}^2 \to \mathbb{N}$ such that if $k$ is an integer and $G$ is a graph in $\text{obs}(\mathcal{E}_k(\text{exc}(\mathcal{F})))$ of treewidth $\text{tw}$, then $|V(G)| \le f_{16}(\text{tw}, k)$. Moreover, $f_{16}(t, k) = 2^{2^{O_{\ell_F}(t^3+k \cdot t^2)}}$.

**PROOF.** Let $G \in \text{obs}(\mathcal{E}_k(\text{exc}(\mathcal{F})))$. We set $t := \text{tw}(G) + 1$. For simplicity, we use $\ell$ instead of $\ell_F$. We set

$$d = f_{14}(t - 1, k) + 1,$$

$$x = m^t, \text{ and}$$

$$m = 2^{\binom{t}{2}} \cdot (d - 1) + 1,$$

$$b = t \cdot 2^x.$$

It is easy to verify that $b = 2^{2^{O_{\ell_F}(t^3+k \cdot t^2)}}$.

Suppose towards a contradiction that $|V(G)| > b$. Let $(T, \beta)$ be a tree decomposition of $G$ of width $\text{tw}(G)$ and let $r \in V(T)$. We consider the rooted tree $(T, r)$ and we set $B := \beta(r)$ and a
bijection $\rho : B \to [|B|]$. We set $\mathbf{G} = (G, B, \rho)$ and observe that $(T, \beta, r)$ is a tree decomposition of $\mathbf{G}$ of width $\mathrm{tw}(G)$. Since $\mathrm{tw}(\mathbf{G}) = \mathrm{tw}(G) = t - 1$, by Proposition 10.3, we can assume that for the tree decomposition $(T, \beta, r)$ of $\mathbf{G}$ of width $t-1$, Properties (1) to (4) are satisfied.

Since $|V(G)| > b = t \cdot 2^x$, Property (4) implies that $|V(T)| > 2^x$. Also, by Property (1), $(T, r)$ is a binary tree and therefore there exists a leaf $u$ of $T$ such that $|V(rTu)| \ge x$. We set $l := |V(rTu)|$.

We set $v_1 = r$ and for every $i \in [l-1]$, we set $v_{i+1}$ to be the child of $v_i$ in $(T, r)$ that belongs to $V(rTu)$. Keep in mind that $v_l = u$. For every $i \in [l]$, we set $c_i := |\beta(v_i)|$ and observe that, since $(T, \beta, r)$ has width $t-1$, $c_i \in [t]$.

Let $C$ be the word $c_1 \cdots c_x$. Since $x = m^t$ and every $c_i \in [t]$, then, due to Proposition 10.4, there is a $t' \in [t]$ and a subword $C'$ of $C$ such that, for every $c$ in $C'$, $c \ge t'$ and there are at least $m$ numbers in $C'$ that are equal to $t'$. Therefore, there exists a set $\{z_1, \dots, z_m\} \subseteq V(T)$ such that for every $i \in [2, m]$, $z_i$ is a descendant of $z_{i-1}$ in $(T, r)$, for every $z' \in V(z_1 \dots z_m)$ it holds that $|\beta(z')| \ge t'$, and, for every $i \in [m]$, $|\beta(z_i)| = t'$. Hence, Property (3) of the tree decomposition $(T, \beta, r)$ of $\mathbf{G}$ implies that there exists a collection $\mathcal{P} = \{P_1, \dots, P_{t'}\}$ of $t'$ vertex-disjoint paths in $\mathbf{G}$ between $\beta(z_1)$ and $\beta(z_m)$.

For every $i \in [m]$, let $\rho_i$ be the function mapping a vertex $v$ in $\beta(z_i)$ to the index of the path of $\mathcal{P}$ it intersects, i.e., for every $j \in [t']$, if $v$ is a vertex in $V(P_j) \cap \beta(z_i)$, where $P_j \in \mathcal{P}$, then $\rho_i(v) = j$. Also, for every $i \in [m]$, let $\mathbf{G}_{z_i}$ be the $t$-bounded graph $(G_{z_i}, \beta(z_i), \rho_i)$. Since, $m = 2^{\binom{t}{2}} \cdot (d-1)+1$, there is a set $J \subseteq [m]$ of size $d$ such that for every $i, j \in J$, the graph $G_{z_i}[\beta(z_i)]$ is isomorphic to the graph $G_{z_j}[\beta(z_j)]$. Therefore, for every $i, j \in J$, $\mathbf{G}_{z_i}$ and $\mathbf{G}_{z_j}$ are compatible. Furthermore, observe that for every $i, j \in J$ with $i \le j$, $\mathbf{G}_{z_j} \le \mathbf{G}_{z_i}$. To see why this holds, for every $i, j \in J$ with $i < j$, let $\mathcal{P}_{i,j}$ be the collection of subpaths of $\mathcal{P}$ between the vertices of $\beta(z_i)$ and $\beta(z_j)$ and consider the graph $G_{z_i}[\beta(z_i)] \cup \bigcup_{j \in J} \mathcal{P}_{i,j} \cup G_{z_j}$, which is a subgraph of $G_{z_i}$. By contracting the edges in $\mathcal{P}_{i,j}$, we obtain a bounded graph isomorphic to $\mathbf{G}_{z_j}$.

Recall that $|J| = d = f_{14}(t-1, k) + 1$. Thus, by Lemma 7.6, there exist $i, j \in J$ such that $j$ is the smallest element in $J$ that is greater than $i$ and $\mathrm{char}_k(\mathbf{G}_{z_i}) = \mathrm{char}_k(\mathbf{G}_{z_j})$. For simplicity, we set $a := z_i$ and $b := z_j$. Notice that, in $G$, by contracting the edges of the paths in $\mathcal{P}_{i,j}$ and removing the vertices of $G_a$ that are not vertices of $G_b$, we obtain a graph isomorphic to $\bar{\mathbf{G}}_a \oplus \mathbf{G}_b$. Therefore, $\bar{\mathbf{G}}_a \oplus \mathbf{G}_b$ is a minor of $G$. Furthermore, $|V(\bar{\mathbf{G}}_a \oplus \mathbf{G}_b)| < |V(G)|$. To prove this, we argue that $G_b$ is a proper subgraph of $G_a$. First recall that for every $y \in V(aTb)$, $|\beta(y)| \ge t'$. If there is a $y \in V(aTb)$ such that $|\beta(y)| > t'$, then there is a vertex $v \in \beta(y)$ that is a vertex of $V(G_a) \setminus V(G_b)$ and thus $G_b$ is a proper subgraph of $G_a$, while in the case where for every $y \in V(aTb)$, $|\beta(y)| = t'$, Property (2) of Proposition 10.3 implies that $G_b$ is a proper subgraph of $G_a$.

Let $G' := \bar{\mathbf{G}}_a \oplus \mathbf{G}_b$. Since $|V(G')| < |V(G)|$, $G'$ is a minor of $G$, and $G \in \mathrm{obs}(\mathcal{E}_k(\mathrm{exc}(\mathcal{F})))$, it holds that $G' \in \mathcal{E}_k(\mathrm{exc}(\mathcal{F}))$. By Lemma 7.16, since $\mathrm{char}_k(\mathbf{G}_a) = \mathrm{char}_k(\mathbf{G}_b)$, we have that $\mathrm{ed}_{\mathrm{exc}(\mathcal{F})}(\bar{\mathbf{G}}_a \oplus \mathbf{G}_a) = \mathrm{ed}_{\mathrm{exc}(\mathcal{F})}(\bar{\mathbf{G}}_a \oplus \mathbf{G}_b)$ and therefore $\mathrm{ed}_{\mathrm{exc}(\mathcal{F})}(G) = \mathrm{ed}_{\mathrm{exc}(\mathcal{F})}(G')$. This contradicts the fact that $\mathrm{ed}_{\mathrm{exc}(\mathcal{F})}(G) > k$ and $\mathrm{ed}_{\mathrm{exc}(\mathcal{F})}(G') \le k$. $\blacksquare$

<figure><img src="image_10.png" /></figure>
# 11. Concluding remarks

For a minor-closed graph class $\mathcal{G}$, we proved that VERTEX DELETION TO $\mathcal{G}$ can be solved in time $2^{\text{poly}(k)} \cdot n^2$ and that ELIMINATION DISTANCE TO $\mathcal{G}$ can be solved in time $2^{2^{2^{\text{poly}(k)}}} \cdot n^2$, and in time $2^{2^{c \cdot k^2 \log k}} \cdot n^2$ and $2^{\text{poly}(k)} \cdot n^3$ in the case where the obstruction set of $\mathcal{G}$ contains an apex-graph. Here the degree of poly and $c$ heavily depend on the size of the obstructions of $\mathcal{G}$. An open question is whether $\text{poly}(k)$ could be replaced by $c \cdot k^d$ for some constant $c$ depending on $\mathcal{G}$ and some *universal* constant $d$ (independent of $\mathcal{G}$). We tend to believe that this dependence on $\mathcal{G}$ in the exponent of the polynomial is unavoidable, at least if we want to use the irrelevant vertex technique, and specially our definition of homogeneity.

On the other hand, we are not aware, for any of the two considered problems, of any lower bound, assuming the Exponential Time Hypothesis [36], stronger than $2^{o(k)} \cdot n^{O(1)}$, which follows quite easily from known results for VERTEX COVER. Proving stronger lower bounds seems to be quite challenging.

Another open problem is whether it is possible to drop the time complexity of ELIMINATION DISTANCE TO $\mathcal{G}$ to $2^{\text{poly}(k)} \cdot n^2$ for every minor-closed graph class $\mathcal{G}$. We tend to believe that this should be possible. However, it seems to require to use branching ingeniously and, in particular, to find equivalent instances of ELIMINATION DISTANCE TO $\mathcal{G}$ with a decreasing value of $k$.

As for the polynomial running time of our FPT-algorithms, a priori, nothing prevents the existence of algorithms running in *linear time*, although we are quite far from achieving this. Kawarabayashi [41] presented such a linear FPT-algorithm for the PLANARIZATION problem, heavily relying on the embedding on the resulting planar graph. Extending this technique to general minor-closed classes would require a very compact encoding of the (entangled) structure of minor-free graphs [64] that would be possible to handle in linear time.

We also proposed an XP-algorithm for ELIMINATION DISTANCE TO $\mathcal{G}$ parameterized by the treewidth of the input graph (with running time $n^{O(\text{tw}^2)}$). As mentioned in the introduction (see also [4]), the existence of an FPT-algorithm for ELIMINATION DISTANCE TO $\mathcal{G}$, parameterized by treewidth, remains wide open and this is the case even in the very special case where $\mathcal{G}$ contains only the empty graph, where ELIMINATION DISTANCE TO $\mathcal{G}$ is equivalent to the problem of computing treedepth.

A last direction is to improve the bounds on the size of the obstructions given in Theorem 1.5. We believe that any substantial improvement should demand novel methodologies that go beyond the irrelevant vertex technique.
References

[1] Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos. Faster parameterized algorithms for minor containment. *Theoretical Computer Science*, 412(50):7018-7028, 2011. DOI (19)

[2] Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. *Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 641–650, 2008. URL DOI (4)

[3] Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Irrelevant vertices for the planar disjoint paths problem. *Journal of Combinatorial Theory, Series B*, 122:815-843, 2017. DOI (14)

[4] Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent. *Proc. of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 1976–2004, 2022. DOI (5, 6, 72)

[5] Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs. *SIAM J. Discret. Math.* 36(2):911-921, 2022. DOI (5)

[6] Akanksha Agrawal and M. S. Ramanujan. On the parameterized complexity of clique elimination distance. *Proc. of the 15th International Symposium on Parameterized and Exact Computation (IPEC)*, volume 180 of LIPIcs, 1:1-1:13, 2020. DOI (5)

[7] Ernst Althaus and Sarah Ziegler. Optimal tree decompositions revisited: a simpler linear-time fpt algorithm, *Graphs and Combinatorial Optimization: from Theory to Applications*. Volume 5, AIRO Springer Series, pages 67-78. Springer, 2021. DOI (20)

[8] Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. *SIAM Journal on Algebraic Discrete Methods*, 8(2):277-284, 1987. DOI (56)

[9] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. *Proc. of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 951-970, 2020. DOI (8, 10, 12, 21, 24, 32, 39)

[10] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. I. General upper bounds. *SIAM Journal on Discrete Mathematics*, 34(3):1623-1648, 2020. DOI (10)

[11] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms. *Theoretical Computer Science*, 814:135-152, 2020. DOI (10)

[12] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. III. Lower bounds. *Journal of Computer and System Sciences*, 109:56-77, 2020. DOI (10)

[13] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. IV. an optimal algorithm. *SIAM J. Comput.* 52(4):865-912, 2023. DOI (14)

[14] Patrick Bellenbaum and Reinhard Diestel. Two short proofs concerning tree-decompositions. *Combinatorics, Probability and Computing*, 11(6):541-547, 2002. DOI (70)

[15] Hans L. Bodlaender, John R. Gilbert, Ton Kloks, and Hjálmtýr Hafsteinsson. Approximating treewidth, pathwidth, and minimum elimination tree height. *Proc. of the 17th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 570 of LNCS, pages 1-12, 1991. DOI (4, 5, 19)

[16] Jannis Bulian and Anuj Dawar. Fixed-parameter tractable distances to sparse graph classes. *Algorithmica*, 79(1):139-158, 2017. DOI (2, 4, 61)

[17] Jannis Bulian and Anuj Dawar. Graph isomorphism parameterized by elimination distance to bounded degree. *Algorithmica*, 75(2):363-382, 2016. DOI (2)

[18] Dimitris Chatzidimitriou, Dimitrios M. Thilikos, and Dimitris Zoros. Sparse obstructions for minor-covering parameters. *Discrete Applied Mathematics*, 278:28-50, 2020. DOI (70)

[19] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. DOI (3)

[20] Reinhard Diestel. Graph Theory, volume 173. Springer-Verlag, 5th edition, 2017. DOI (8, 35, 64)

[21] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. DOI (3)

[22] Zdenek Dvorák, Archontia C. Giannopoulou, and Dimitrios M. Thilikos. Forbidden graphs for tree-depth. *European Journal of Combinatorics*, 33(5):969-979, 2012. DOI (7, 67)

[23] Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon. Measuring what matters: A hybrid approach to dynamic programming with treewidth. *Journal of Computer and System Sciences*, 121:57-75, 2021. DOI (5)

[24] Joshua Erde. A unified treatment of linked and lean tree-decompositions. *Journal of Combinatorial Theory, Series B*, 130:114-143, 2018. DOI (70)

[25] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. DOI (3)
[26] Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound logics for modification problems. 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, 61:1-61:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. DOI (14)

[27] Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Parameterized complexity of elimination distance to first-order logic properties. ACM Transactions on Computational Logic, 23(3):17:1-17:35, 2022. DOI (5)

[28] Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar $\mathcal{F}$-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. Proc. of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 470-479, 2012. DOI (4, 10)

[29] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Hitting topological minors is FPT. Proc. of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 1317-1326, 2020. DOI (4, 10)

[30] Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. A menger-like property of tree-cut width. J. Comb. Theory B, 148:1-22, 2021. DOI (8)

[31] Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: obstructions and algorithmic aspects. Algorithmica, 81(2):557-588, 2019. DOI (8, 70)

[32] Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Linear kernels for edge deletion problems to immersion-closed graph classes. Proc. of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), volume 80 of LIPIcs, 57:1-57:15, 2017. DOI (8)

[33] Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Combing a linkage in an annulus. SIAM J. Discret. Math. 37(4):2332-2364, 2023. DOI (14)

[34] Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Model-checking for first-order logic with disjoint paths predicates in proper minor-closed graph classes. Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3684-3699. SIAM, 2023. DOI (14)

[35] Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems: distance from triviality. Proc. of the 1st International Workshop on Parameterized and Exact Computation (IWPEC), volume 3162 of LNCS, pages 162-173, 2004. DOI (2)

[36] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. DOI (72)

[37] Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. Vertex deletion parameterized by elimination distance and even less. Proc. of the 53rd Annual ACM-SIGACT Symposium on Theory of Computing (STOC), pages 1757-1769, 2021. DOI (5)

[38] Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1802-1811, 2014. DOI (4)

[39] Mamadou Moustapha Kanté and O-joung Kwon. An upper bound on the size of obstructions for bounded linear rank-width, 2014. URL (8)

[40] Mamadou Moustapha Kanté and O-joung Kwon. Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions. European Journal of Combinatorics, 74:110-139, 2018. DOI (8)

[41] Ken-ichi Kawarabayashi. Planarity allowing few error vertices in linear time. Proc. of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 639-648, 2009. DOI (72)

[42] Ken-ichi Kawarabayashi and Yusuke Kobayashi. Linear min-max relation between the treewidth of an *H*-minor-free graph and its largest grid minor. Journal of Combinatorial Theory, Series B, 141:165-180, 2020. DOI (24)

[43] Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A. Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B, 102(2):424-435, 2012. DOI (4, 22)

[44] Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. A new proof of the flat wall theorem. Journal of Combinatorial Theory, Series B, 129:204-238, 2018. DOI (7, 13, 22, 24, 25)

[45] Ken-ichi Kawarabayashi and Paul Wollan. A Shorter Proof of the Graph Minor Algorithm: The Unique Linkage Theorem. Proc. of the 42nd ACM Symposium on Theory of Computing (STOC), pages 687-694, 2010. DOI (14, 15)

[46] Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Transactions on Algorithms, 12(2):21:1-21:41, 2016. DOI (4, 10)

[47] Eun Jung Kim, Maria J. Serna, and Dimitrios M. Thilikos. Data-compression for parametrized counting problems on sparse graphs. Proc. of the 29th International Symposium on Algorithms and Computation (ISAAC), volume 123 of LIPIcs, 20:1-20:13, 2018. DOI (10)

[48] Ton Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994. DOI (3)

[49] Tomasz Kociumaka and Marcin Pilipczuk. Deleting Vertices to Graphs of Bounded Genus. Algorithmica, 81(9):3655-3691, 2019. DOI (4)
[50] Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. *Proc. of the 62nd Annual Symposium on Foundations of Computer Science (FOCS)*, pages 184–192, 2021. DOI (19)

[51] Jens Lagergren. An upper bound on the size of an obstruction, *Graph Structure Theory*. Volume 147, Contemporary Mathematics, pages 601–621. American Mathematical Society, 1991. DOI (8)

[52] Jens Lagergren. Upper bounds on the size of obstructions and intertwines. *Journal of Combinatorial Theory, Series B*, 73:7–40, 1998. DOI (8, 70)

[53] Jens Lagergren and Stefan Arnborg. Finding minimal forbidden minors using a finite congruence. *Proc. of the 18th International Colloquium on Automata, Languages and Programming (ICALP)*, volume 510 of LNCS, pages 532–543, 1991. DOI (8)

[54] John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. *Journal of Computer and System Sciences*, 20(2):219–230, 1980. DOI (3)

[55] Dániel Marx and Ildikó Schlotter. Obtaining a planar graph by vertex deletion. *Algorithmica*, 62(3-4):807–822, 2012. DOI (4, 7, 15)

[56] Laure Morelle, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Faster Parameterized Algorithms for Modification Problems to Minor-Closed Classes. *Proc. of the 50th International Colloquium on Automata, Languages, and Programming (ICALP)*, volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), 93:1–93:19, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. DOI (1)

[57] Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of *Algorithms and combinatorics*. Springer, 2012. DOI (3)

[58] Rolf Niedermeier. Invitation to fixed parameter algorithms, volume 31. Oxford University Press, 2006. DOI (3)

[59] Ljubomir Perkovic and Bruce A. Reed. An improved algorithm for finding tree decompositions of small width. *International Journal of Foundations of Computer Science*, 11(3):365–371, 2000. DOI (56)

[60] Alex Pothen. The complexity of optimal elimination trees. Technical Report. Pennsylvania State University. Dept. of Computer Science, 1988. URL (3)

[61] Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. *Proc. of the 41st International Colloquium on Automata, Languages, and Programming (ICALP)*, volume 8572 of LNCS, pages 931–942, 2014. DOI (4, 6, 8, 39, 40, 67)

[62] Neil Robertson and Paul D. Seymour. Graph Minors. V. Excluding a planar graph. *Journal of Combinatorial Theory, Series B*, 41(2):92–114, 1986. DOI (69, 70)

[63] Neil Robertson and Paul D. Seymour. Graph Minors. XIII. The Disjoint Paths Problem. *Journal of Combinatorial Theory, Series B*, 63(1):65–110, 1995. DOI (4, 7, 24)

[64] Neil Robertson and Paul D. Seymour. Graph Minors. XVI. Excluding a non-planar graph. *Journal of Combinatorial Theory, Series B*, 89(1):43–76, 2003. DOI (72)

[65] Neil Robertson and Paul D. Seymour. Graph Minors. XX. Wagner's conjecture. *Journal of Combinatorial Theory, Series B*, 92(2):325–357, 2004. DOI (4, 10)

[66] Neil Robertson and Paul D. Seymour. Graph Minors. XXI. Graphs with unique linkages. *Journal of Combinatorial Theory, Series B*, 99(3):583–616, 2009. DOI (14)

[67] Neil Robertson and Paul D. Seymour. Graph Minors. XXII. Irrelevant vertices in linkage problems. *Journal of Combinatorial Theory, Series B*, 102(2):530–563, 2012. DOI (14)

[68] Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. A more accurate view of the Flat Wall Theorem, 2021. URL (7, 11, 13, 14, 22, 24, 25, 27)

[69] Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. *k*-apices of minor-closed graph classes. i. bounding the obstructions. *J. Comb. Theory B*, 161:180–227, 2023. DOI (7, 8, 11, 14, 15, 22, 25, 29, 31, 70)

[70] Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. *k*-apices of minor-closed graph classes. II. parameterized algorithms. *ACM Trans. Algorithms*, 18(3):21:1–21:30, 2022. DOI (4–7, 10–16, 22, 25, 31, 33, 56, 60)

[71] Robin Thomas. A Menger-like property of tree-width: The finite case. *Journal of Combinatorial Theory, Series B*, 48(1):67–76, 1990. DOI (69, 70)

[72] Andrew Thomason. The extremal function for complete minors. *Journal of Combinatorial Theory, Series B*, 81(2):318–338, 2001. DOI (10)