# Quickly excluding an apex-forest

Jędrzej Hodor, Xuan Hoang La, Piotr Micek, Clément Rambaud

► To cite this version:

Jędrzej Hodor, Xuan Hoang La, Piotr Micek, Clément Rambaud. Quickly excluding an apex-forest.
2024. hal-04819247

HAL Id: hal-04819247

https://inria.hal.science/hal-04819247v1

Preprint submitted on 4 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
QUICKLY EXCLUDING AN APEX-FOREST

JĘDRZEJ HODOR, HOANG LA, PIOTR MICEK, AND CLÉMENT RAMBAUD

ABSTRACT. We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)| - 3$. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our main tool is a structural result about graphs excluding a forest as a rooted minor, which is of independent interest. We develop similar tools for treedepth and treewidth. We discuss implications for Erdős-Pósa properties of rooted models of minors in graphs.

# 1. INTRODUCTION

Within the seminal *Graph minors* series, spanning from 1983 to 2010, Robertson and Seymour described the structure of graphs excluding a graph as a minor. One of many key insights of this series is the interplay between forbidding graphs as minors and treewidth or pathwidth. Indeed, excluding a planar graph as a minor is equivalent to having bounded treewidth, which follows from the Grid Minor Theorem [11]. Similarly, excluding a forest as a minor is equivalent to having bounded pathwidth, which was proved in the first paper of the series [10]. Another relevant statement following this pattern is that excluding a path as a minor is equivalent to having bounded treedepth; see e.g. [8, Chapter 6].

In this paper, we study analogous statements for excluding apex-type graphs as minors. Recall that a graph is an *apex graph* if it can be made planar by the removal of at most one vertex, and a graph is an *apex-forest* if it can be made acyclic by the removal of at most one vertex. It turns out that forbidding apex-type graphs as minors interplays with the layered versions of treewidth, pathwidth, and treedepth. Dujmović, Morin, and Wood [6] proved that a minor-closed class of graphs excludes an apex graph if and only if it has bounded layered treewidth. Similarly, Dujmović, Eppstein, Joret, Morin, and Wood in [4], proved that a minor-closed class of graphs excludes an apex-forest if and only if it has bounded layered pathwidth. Our first contribution is a short and simple proof of the latter statement with an explicit and much better bound on layered pathwidth. In what follows, for a graph $G$, we denote by $\text{tw}(G)$, $\text{pw}(G)$, $\text{td}(G)$, and $\text{lpw}(G)$ the treewidth, pathwidth, treedepth, and layered pathwidth of $G$ respectively.

(J. Hodor) THEORETICAL COMPUTER SCIENCE DEPARTMENT, FACULTY OF MATHEMATICS AND COMPUTER SCIENCE AND DOCTORAL SCHOOL OF EXACT AND NATURAL SCIENCES, JAGIELLONIAN UNIVERSITY, KRAKÓW, POLAND

(H. La) LISN, UNIVERSITÉ PARIS-SACLAY, CNRS, GIF-SUR-YVETTE, FRANCE

(P. Micek) THEORETICAL COMPUTER SCIENCE DEPARTMENT, FACULTY OF MATHEMATICS AND COMPUTER SCIENCE, JAGIELLONIAN UNIVERSITY, KRAKÓW, POLAND

(C. Rambaud) UNIVERSITÉ CÔTE D'AZUR, CNRS, INRIA, I3S, SOPHIA-ANTIPOLIS, FRANCE

E-mail addresses: jedrzej.hodor@gmail.com, hoang.la.research@gmail.com, piotr.micek@uj.edu.pl, clement.rambaud@inria.fr.

This research was funded by the National Science Center of Poland under grant UMO-2023/05/Y/ST6/00079 within the OPUS 25 program. C. Rambaud was partially supported by the French Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01.
**Theorem 1.** For every apex-forest $X$ with at least two vertices, and for every graph $G$, if $G$ is $X$-minor-free, then $\text{lpw}(G) \le 2|V(X)| - 3$.

The main novelty in the proof of Theorem 1 is a version of path decomposition (and pathwidth) of a graph $G$ focused on some fixed subset $S$ of $V(G)$. We denote the new parameter by $\text{pw}(G, S)$, and we prove that for every forest $F$, if $G$ has no $S$-rooted model of $F$, then $\text{pw}(G, S) \le 2|V(F)| - 2$, see Theorem 7. This part of the proof follows closely the argument by Diestel [3] showing that for every forest $F$, if $G$ has no $F$-minor, then $\text{pw}(G) \le |V(F)| - 2$.

A graph is a fan or (an apex-path) if it becomes a path by the removal of at most one vertex. We introduce the concept of layered treedepth mimicking other layered parameters. It will be immediate that fans may have arbitrarily large layered treedepth. Conversely, we prove that excluding a fan as a minor implies having bounded layered treedepth. For a graph $G$, let $\text{ltd}(G)$ be the layered treedepth of $G$.

**Theorem 2.** For every fan $X$ with at least three vertices, and for every graph $G$, if $G$ is $X$-minor-free, then $\text{ltd}(G) \le (|V(X)|-1)/2$.

Similarly to the proof of Theorem 1, the proof of Theorem 2 relies on a version of treedepth focused on some fixed subset $S$ of $V(G)$ that we denote by $\text{td}(G, S)$. The crucial property of this parameter is that for every path $P$, if $G$ has no $S$-rooted model of $P$, then $\text{td}(G, S) \le (|V(P)|/2)$, see Theorem 6.

Following the definition of $\text{pw}(G, S)$, one can also define a notion of treewidth focused on $S$, denoted by $\text{tw}(G, S)$. We show an approximate duality between this parameter and a version of tangles focused on $S$ proposed by Marx, Seymour, and Wollan [7], see Theorem 10. Combined with the main result of [7], this yields a grid-minor theorem for this notion of treewidth, see Theorem 8.

The next two statements will follow immediately from the definitions of layered treedepth and pathwidth, Theorem 2 and Theorem 1, respectively. Recall that the diameter of a graph $G$, denoted by $\text{diam}(G)$, is the maximal distance between two vertices in $G$ taken over all pairs of vertices in $G$.

**Corollary 3.** For every fan $X$ with at least two vertices, and for every connected graph $G$, if $G$ is $X$-minor-free, then $\text{td}(G) \le (|V(X)|-1)/2 (\text{diam}(G) + 1)$.

**Corollary 4.** For every apex-forest $X$ with at least two vertices, and for every connected graph $G$, if $G$ is $X$-minor-free, then $\text{pw}(G) \le (2|V(X)| - 3)(\text{diam}(G) + 1) - 1$.

Note that Corollary 3 and Corollary 4 are both optimal in the following sense. There are fans of diameter 2 and unbounded treedepth and there are apex-forests of diameter 2 and unbounded pathwidth. We also give a construction showing that the upper bound in Corollary 4 is tight up to a multiplicative constant, see Theorem 20.

A natural strengthening of Theorem 1 is the following (false) product structure statement: for every apex-forest $X$, there is a constant $c_X$ such that for every $X$-minor-free graph $G$, we have $G \subseteq H \boxtimes P^1$ for some graph $H$ with $\text{pw}(H) \le c_X$ and some path $P$. The statement is false even for $X = K_3$, as Bose, Dujmović, Javarsineh, Morin, and Wood [2] proved that trees do

<footnote n="1">¹The strong product $G_1 \boxtimes G_2$ of two graphs $G_1$ and $G_2$ is the graph with vertex set $V(G_1 \boxtimes G_2) := V(G_1) \times V(G_2)$ and that contains the edge with endpoints $(v, x)$ and $(w, y)$ if and only if $vw \in E(G_1)$ and $x = y$; or $v = w$ and $xy \in E(G_2)$; or $vw \in E(G_1)$ and $xy \in E(G_2)$.</footnote>
not admit such a product structure. Since $K_3$ is a fan, the construction in [2] also shows that
the analogous strengthening of Theorem 2 does not hold.

In Section 2, we give all necessary definitions. In Section 3, we state our main technical
contribution – a collection of graph decompositions focused on a prescribed subset of vertices.
In Section 4, we prove Theorem 1 and the main properties of pw(G, S). In Section 5, we prove
Theorem 2 and the main properties of td(G, S). In Section 6, we prove the main properties of
tw(G, S). Additionally, in Section 7, we give a lower bound construction for Corollary 3 and
Corollary 4. In Section 8, we discuss further applications of our results concerning Erdős-Pósa
properties of rooted models of graphs. In Section 9, we state a few open problems.

## 2. PRELIMINARIES

We allow a graph to be the null graph. Moreover, the null graph is a path, a tree, and a grid.
For a non-negative integer $\ell$, we denote by $P_\ell$ a graph that is a path on $\ell$ vertices and by $\boxplus_\ell$
an $\ell \times \ell$ planar grid.

Let $G$ be a graph. The neighborhood of a vertex $v$ is the set of neighbors of $v$, denoted by $N(v)$.
The neighborhood of a set $R \subseteq V(G)$ is $N_G(R) = \bigcup_{v \in R} N_G(v) - R$. We drop the subscript
when the graph is clear from context.

Let $H$ be a graph. A *model* of $H$ in $G$ is a family $(B_x | x \in V(H))$ of pairwise disjoint subsets of $V(G)$ such that:

(i) for every $x \in V(H)$, the subgraph of $G$ induced by $B_x$ is non-empty and connected, and

(ii) for every edge $xy \in E(H)$, there is an edge between $B_x$ and $B_y$ in $G$.

The set $B_x$ for $x \in V(H)$ is called the *branch set* of $u$ in the model. We say that $H$ is a *minor* of $G$ if $G$ contains a model of $H$. Otherwise, we say that $G$ is *H-minor-free*. Let $S \subseteq V(G)$. A model $(B_x | x \in V(H))$ of $H$ in $G$ is *S-rooted* if $B_x \cap S \neq \emptyset$ for each $x \in V(H)$. Moreover, if $H$ is a plane graph, we say that a model $(B_x | x \in V(H))$ of $H$ in $G$ is *S-outer-rooted* if $B_x \cap S \neq \emptyset$ for each vertex $x$ in the outer face of $H$.

A *rooted forest* is a disjoint union of rooted trees. The *vertex-height* of a rooted forest $F$ is the maximum number of vertices on a path from a root to a leaf in $F$, and the *depth* of a vertex $u \in V(F)$ is the number of vertices in the path between $u$ and the root of its component. For two vertices $u, v$ in a rooted forest $F$, we say that $u$ is a *descendant* of $v$ in $F$ if $v$ lies on the path from a root to $u$ in $F$. The *closure* of $F$ is the graph with vertex set $V(F)$ and edge set $\{vw | v \neq w \text{ and } v \text{ is a descendant of } w \text{ in } F\}$. We say that $F$ is an *elimination forest* of $G$ if $V(F) = V(G)$ and $G$ is a subgraph of the closure of $F$. The *treewidth* of a graph $G$, denoted by $\text{td}(G)$, is 0 if $G$ is empty, and otherwise is the minimum vertex-height of an elimination forest of $G$.

A *tree decomposition* of $G$ is a pair $\mathcal{B} = (T, (W_x | x \in V(T)))$, where $T$ is a non-null tree and the sets $W_x$ for each $x \in V(T)$ are subsets of $V(G)$ called *bags* satisfying:

(i) for each edge $uv \in E(G)$ there is a bag containing both $u$ and $v$, and

(ii) for each vertex $v \in V(G)$ the set of vertices $x \in V(T)$ with $v \in W_x$ induces a non-empty subtree of $T$.

The *width* of $\mathcal{B}$ is $\max\{|W_x| - 1 \mid x \in V(T)\}$. The *treewidth* of $G$, denoted $\text{tw}(G)$, is the minimum width of a tree decomposition of $G$. A *path decomposition* of $G$ is a tree decomposition $(T, (W_x \mid x \in V(T)))$, where $T$ is a path. In that case, we simply write $(W_i \mid i \in [m])$ for $(T, (W_x \mid x \in V(T)))$, where $m = |V(T)|$, simply identifying $T$ with a path on $[m]$. The *pathwidth* of a graph $G$, denoted $\text{pw}(G)$, is the minimum width of a path decomposition of $G$.
A *layering* of $G$ is a sequence $(L_i | i \ge 0)$ of disjoint subsets of $V(G)$ whose union is $V(G)$ and such that for every $uv \in E(G)$ there is a non-negative integer $i$ such that $u, v \in L_i \cup L_{i+1}$.

Let $\mathcal{B} = (T, (B_x | x \in V(T)))$ be a tree decomposition of $G$ and let $\mathcal{L} = (L_i | i \ge 0)$. The *width* of $(\mathcal{B}, \mathcal{L})$ is $\max\{|B_x \cap L_i| \mid x \in V(T), i \ge 0\}$. The *layered treewidth* of $G$ is the minimum width of a pair $(\mathcal{B}, \mathcal{L})$, where $\mathcal{B}$ is a tree decomposition of $G$ and $\mathcal{L}$ is a layering of $G$. The *layered pathwidth* of $G$ is the minimum width of a pair $(\mathcal{B}, \mathcal{L})$, where $\mathcal{B}$ is a path decomposition of $G$ and $\mathcal{L}$ is a layering of $G$.

We propose a natural counterpart of the definitions above for treedepth. Let $F$ be an elimination forest of $G$, and let $\mathcal{L} = (L_i | i \ge 0)$ be a layering of $G$. The *width* of $(F, \mathcal{L})$ is $\max\{|R \cap L_i| \mid R \text{ is a root-to-leaf path in } F, i \ge 0\}$. The *layered treedepth* of $G$ is the minimum width of a pair $(F, \mathcal{L})$, where $F$ is an elimination forest of $G$ and $\mathcal{L}$ is a layering of $G$.

A *separation* of $G$ is a pair $(A, B)$ of subgraphs of $G$ such that $A \cup B = G$, $E(A \cap B) = \emptyset$, and $|V(A \cap B)| = k$. The *order* of $(A, B)$ is $|V(A) \cap V(B)|$. For $X, Y \subseteq V(G)$, an $X-Y$ *path* is a path in $G$ that is either a one-vertex path with the vertex in $X \cap Y$ or a path with one endpoint in $X$ and the other endpoint in $Y$ such that no internal vertices are in $X \cup Y$. We need the following well-known theorem.

**Theorem 5 (Menger's Theorem).** Let $G$ be a graph and $X, Y \subseteq V(G)$. There exists a separation $(A, B)$ of $G$ such that $X \subseteq V(A)$, $Y \subseteq V(B)$, and there exists $|V(A) \cap V(B)|$ pairwise disjoint $X-Y$ paths.

### 3. EXCLUDING A ROOTED MINOR

In this section, we introduce a new family of graph parameters and we state some of their properties that are the key technical ingredients of the proofs of our main results. However, we believe that the parameters and their properties are of independent interest. We start with the new version of treedepth, and afterward, we discuss the new versions of pathwidth and treewidth.

Let $G$ be a graph and let $S \subseteq V(G)$. An *elimination forest* of $(G, S)$ is an elimination forest $F$ of $H$, an induced subgraph of $G$ such that $S$ is contained in $V(H)$ and for every component $C$ of $G - V(H)$, there is a root-to-leaf path in $F$ containing all the neighbors of $V(C)$ in $G$. The *treedepth* of $(G, S)$, denoted by $\text{td}(G, S)$, is the minimum vertex-height of an elimination forest of $(G, S)$. This notion is similar in its definition to the elimination distance to a given subgraph-closed class of graph $\mathcal{C}$ (see e.g. [9]), which is defined as $\min\{\text{td}(G, S) \mid S \subseteq V(G) \text{ such that every component of } G-S \text{ is in } \mathcal{C}\}$.

Recall that if a graph $G$ has no model of $P_\ell$, then $\text{td}(G) < \ell$. We prove an analogous result within the setting of $S$-rooted models of paths.

**Theorem 6.** For every positive integer $\ell$, for every graph $G$, and for every $S \subseteq V(G)$, if $G$ has no $S$-rooted model of $P_\ell$, then $\text{td}(G, S) \le \binom{\ell}{2}$.

As already mentioned, Theorem 6 is the main ingredient of the proof of Theorem 2. Actually, the intuition standing behind this is very simple. For a vertex $u$ in a graph $G$, we set $S = N(u)$. Now, if $G - u$ has a $S$-rooted model of a path $P_\ell$, then $G$ has a model of $P_\ell$ with a universal vertex added, and so $G$ has a model of every fan on $\ell + 1$ vertices.
Let $G$ be a graph and let $S \subseteq V(G)$. A tree decomposition (resp. path decomposition) of $(G, S)$ is a tree decomposition (resp. path decomposition) $\mathcal{B}$ of $H$, an induced subgraph of $G$ such that $S$ is contained in $V(H)$, and for every component $C$ of $G - V(H)$, there exists a bag of $\mathcal{B}$ containing all the neighbors of $V(C)$ in $G$. The treewidth (resp. pathwidth) of $(G, S)$, denoted by $\mathrm{tw}(G, S)$ (resp. $\mathrm{pw}(G, S)$), is the minimum width of a tree decomposition (resp. path decomposition) of $(G, S)$. We illustrate the notion of a path decomposition of $(G, S)$ in Figure 1.

$$V(H) \supseteq S = \bullet \circ$$

<figure><img src="image_2.png" /><figcaption>FIGURE 1. The green and blue bags depict a path decomposition of $H$, an induced subgraph of $G$ such that $S \subseteq V(H)$. Each component of $G - V(H)$ (yellow) has all the neighbors in one of the bags. Note that such a bag does not have to be unique.</figcaption></figure>

Bienstock, Robertson, Seymour, and Thomas [1] first proved that if a graph $G$ has no model of a forest $F$, then $\mathrm{pw}(G) \le |V(F)| - 2$. Note that the first bound on $\mathrm{pw}(G)$ in terms of $|V(F)|$ was proved by Robertson and Seymour in [10]. On the other hand, Diestel gave a beautiful and short proof of the above in [3]. We prove an analogous result within the setting of $S$-rooted models of forests.

**Theorem 7.** For every forest $F$ with at least one vertex, for every graph $G$, and for every $S \subseteq V(G)$, if $G$ has no $S$-rooted model of $F$, then $\mathrm{pw}(G, S) \le 2|V(F)| - 2$.

The Grid Minor Theorem can be generalized to the setting of $S$-outer-rooted models as follows.

**Theorem 8.** For every plane graph $H$, there exists a positive integer $c_H$ such that, for every graph $G$, and for every $S \subseteq V(G)$, if $G$ has no $S$-outer-rooted model of $H$, then $\mathrm{tw}(G, S) \le c_H$.

Note that in this result, one cannot replace “$S$-outer-rooted model” with “$S$-rooted model”. Indeed, for every non-negative integer $\ell$, the graph $\oplus_{\ell}$ with $S_\ell$ being the vertex set of the outer face has no $S_\ell$-rooted model of $K_4$, while $\mathrm{tw}(\oplus_{\ell}, S_\ell) \ge \ell - 1$. The latter inequality follows from Lemma 22 applied for the family of all the connected subgraphs that are the union of a row with a column.

We obtain Theorem 8 via tangles. First, let us recall the definition of tangles in graphs. Let $G$ be a graph and let $k$ be a positive integer. Let $\mathcal{T}$ be a family of separations of $G$ of order less than $k$ in $G$. $\mathcal{T}$ is a *tangle* of order $k$ in $G$ if

(T1) for every separation $(A, B)$ of order at most $k-1$ in $G$, $(A, B) \in \mathcal{T}$ or $(B, A) \in \mathcal{T}$,

(T2) for every $(A_1, B_1), (A_2, B_2), (A_3, B_3) \in \mathcal{T}$, $A_1 \cup A_2 \cup A_3 \ne G$, and

(T3) for every $(A, B) \in \mathcal{T}$, $V(A) \ne V(G)$.

Marx, Seymour, and Wollan [7] proposed a variant of tangles that is focused on a prescribed set. Additionally, for a fixed $S \subseteq V(G)$, $\mathcal{T}$ is a *tangle* of $(G, S)$ if it is a tangle of $G$ and
(T4) for every $(A, B) \in \mathcal{T}, S \not\subseteq V(A)$.

The *tangle number* of $(G, S)$, denoted by $\text{tn}(G, S)$, is the maximum order of a tangle of $(G, S)$. When $S = V(G)$, condition (T4) is vacuous, and $\text{tn}(G) = \text{tn}(G, V(G))$ is a classical tangle number of $G$. One of the cornerstones of structural graph theory is that the following graph parameters are functionally tied to each other: treewidth, tangle number, and the maximum integer $\ell$ such that a graph contains a model of $\boxplus_\ell$. An analog in the “focused” setting also holds.

Marx, Seymour, and Wollan [7] showed that the tangle number of $(G, S)$ is functionally tied to the maximum integer $\ell$ such that $G$ has an $S$-outer-rooted model of $\boxplus_\ell$.

**Theorem 9 ([7]).** Let $H$ be a plane graph. There is an integer $c_H$ such that for every graph $G$, if there is a tangle $\mathcal{T}$ of $(G, S)$ of order $c_H$, then $G$ contains an $S$-outer-rooted model of $H$.

We prove that $\text{tn}(G, S)$ is functionally tied to $\text{tw}(G, S)$.

**Theorem 10.** For every graph $G$ with at least one vertex, and for every $S \subseteq V(G)$,
$$ \text{tn}(G, S) - 1 \le \text{tw}(G, S) \le 10 \max\{\text{tn}(G, S), 2\} - 12. $$

Note that Theorem 9 and Theorem 10 immediately imply Theorem 8.

## 4. LAYERED PATHWIDTH

The proof of Theorem 7 follows Diestel's proof [3] that graphs excluding a forest $F$ as a minor have pathwidth at most $|V(F)| - 2$. The notation follows a recent paper by Seymour [12].

Let $G$ be a graph, let $w$ be a positive integer, and let $S \subseteq V(G)$. A separation $(A, B)$ is $(w, S)$-good if it is of order at most $w$ and $(A, S \cap V(A))$ has a path decomposition of width at most $2w - 2$ whose last bag contains $V(A) \cap V(B)$ as a subset. When $(A, B)$, $(A', B')$ are separations of $G$, we write $(A, B) \le (A', B')$, if $A \subseteq A'$ and $B \supseteq B'$. If moreover the order of $(A', B')$ is at most the order of $(A, B)$, then we say that $(A', B')$ *extends* $(A, B)$. A separation $(A, B)$ in $G$ is *maximal* $(w, S)$-good if it is $(w, S)$-good and for every $(w, S)$-good separation $(A', B')$ extending $(A, B)$, we have $A' = A$ and $B' = B$.

We start with a simple lemma illustrated in Figure 2.

**Lemma 11.** Let $G$ be a graph, let $w$ be a positive integer, let $S \subseteq V(G)$, and let $(A', B')$ and $(P, Q)$ be two separations of $G$ with $(P, Q) \le (A', B')$. If $(A', B')$ is $(w, S)$-good and there are $|V(P) \cap V(Q)|$ vertex-disjoint $V(P)-V(B')$ paths in $G$, then $(P, Q)$ is $(w, S)$-good.

*Proof.* Suppose that $(A', B')$ is $(w, S)$-good and there are $|V(P) \cap V(Q)|$ vertex-disjoint $V(P)-V(B')$ paths $(R_x \mid x \in V(P) \cap V(Q))$ in $G$. Let $(W_i \mid i \in [m])$ be a path decomposition of $(A', S \cap V(A'))$ of width at most $2w-2$ with $V(A') \cap V(B') \subseteq W_m$. Let $(V_i \mid i \in [m])$ be obtained from $(W_i \mid i \in [m])$ by contracting $R_x$ into a single vertex that we identify with $x$, for every $x \in V(P) \cap V(Q)$. In other words, $V_i = (W_i \cap V(P)) \cup \{x \in V(P) \cap V(Q) \mid V(R_x) \cap W_i \ne \emptyset\}$ for every $i \in [m]$. Observe that $|V_i| \le |W_i|$ for every $i \in [m]$. We claim that $(V_i \mid i \in [m])$ is a path decomposition of $(P, S \cap V(P))$.

The fact that $(V_i \mid i \in [m])$ is a path decomposition of $H = P[\cup_{i \in [m]} V_i]$ follows from the construction. We show that every component $C$ of $P - V(H)$ has its neighborhood in $P$ contained in $V_i$ for some $i \in [m]$. Let $H' = A'[\cup_{i \in [m]} W_i]$ and let $C$ be a component of
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Illustration of the proof of Lemma 11. On the left, we depict the initial situation and on the right, we depict the result of applying the procedure from the lemma. Bags of path decompositions (of ($A'$, $S \cap V(A')$) on the left and of ($P, S \cap V(P)$) on the right) are green and blue alternately. In yellow, we show the components that are left after removing all vertices of respective path decompositions. The latter is obtained from the former by contracting $|V(P) \cap V(Q)|$ disjoint $V(P)-V(B')$ paths (in blue).</figcaption></figure>

P − V ( H ). Observe that V ( H ) ∩ V ( P ) = V ( H $^{′}$) ∩ V ( P ), and so, P − V ( H ) is a subgraph of A ′ − V ( H $^{′}$). It follows that C is a connected subgraph of A ′ − V ( H $^{′}$). Therefore, there exists i ∈ [ m ] such that the neighborhood of V ( C ) in A ′ is contained in W$_{i}$ , and thus, the neighborhood of C in P is contained in V$_{i}$ .

Finally, since $V(A') \cap V(B') \subseteq W_m$, we have $V(P) \cap V(Q) \subseteq W_m$. Additionally, $|V(P) \cap V(Q)| =$ $|\{R_x \mid x \in V(P) \cap V(Q)\}| \le |V(A') \cap V(B')| \le w$. All this proves that $(P, Q)$ is $(w, S)$-good. □

We will use the following version of Menger's theorem in the proof of Lemma 13.

**Lemma 12.** Let $G$ be a graph and let $(A, B)$ and $(A', B')$ be two separations of $G$. If $(A, B) \le (A', B')$, then there is a separation $(P, Q)$ of $G$ such that

(i) $(A, B) \leq (P, Q) \leq (A', B')$, and

(ii) there are $|V(P) \cap V(Q)|$ pairwise disjoint $V(A)-V(B')$ paths in $G$.

**Lemma 13.** Let $w$ be a positive integer, let $G$ be a graph, and let $S \subseteq V(G)$ such that $pw(G, S) > 2w - 2$. If $F$ is a forest on at most $w$ vertices, then there is a separation $(A, B)$ of $G$ such that

(s1) $|V(A) \cap V(B)| \leq |V(F)|$,

(s2) there is a $(V(A) \cap V(B))$-rooted model of $F$ in $A$, and

(s3) $(A, B)$ is maximal $(w, S)$-good.

*Proof.* We proceed by induction on $|V(F)|$. Suppose that $F$ is the null graph. Since $(\emptyset, G)$ is $(w, S)$-good, then a maximal $(w, S)$-good separation $(A, B)$ extending $(\emptyset, G)$ satisfies (s1)-(s3). Next, let $F$ be a non-empty forest on at most $w$ vertices. Let $t$ be a vertex of $F$ of degree at most one.

By induction hypothesis for $F-t$, $G$ has a separation $(A^0, B^0)$ satisfying (s1)-(s3) for $F-t$. Let $(W_i | i \in [m])$ be a path decomposition of $(A^0, S \cap V(A^0))$ of width at most $2w-2$ with $V(A^0) \cap V(B^0) \subseteq W_m$. If $V(A^0) = V(G)$, then $(W_i | i \in [m])$ is a path decomposition of $(G, S)$, which contradicts the fact that $pw(G, S) > 2w-2$. Hence $V(B^0) - V(A^0) \neq \emptyset$. Let $(B_x | x \in V(F-t))$ be a $(V(A^0) \cap V(B^0))$-rooted model of $F-t$ in $A^0$. If $t$ has degree 0 in $F$, then choose a vertex $v \in V(B^0) - V(A^0)$ arbitrarily. Otherwise, $t$ has a unique neighbor $s$
in $F$. Since $|V(A^0) \cap V(B^0)| = |V(F)| - 1$, let $u$ be the unique vertex in $B_s \cap V(A^0) \cap V(B^0)$, and choose $v$ to be a neighbor of $u$ in $V(B^0) - V(A^0)$. Such a neighbor exists as otherwise $(A^0 \cup \{uu' | uu' \in E(B^0)\}, B^0 - u)$ is $(w, S)$-good, which contradicts the maximality of $(A^0, B^0)$.

Let $(A, B)$ be the separation of $G$ defined by $A = G[V(A^0) \cup \{v\}]$ and $B = G[V(B^0)] - E(A)$. Since $V(A^0) \cap V(B^0) \subseteq W_m$, and the neighborhood of $v$ in $A$ is contained in $V(A^0) \cap V(B^0)$, $(W_1, \dots, W_{m-1}, W_m, V(A) \cap V(B))$ is a path decomposition of $(A, S \cap V(A))$. Moreover, since $|V(A) \cap V(B)| \le |V(F)| \le w \le 2w - 1$, this path decomposition is of order at most $2w - 2$. Therefore, $(A, B)$ is $(w, S)$-good, and so, there is a maximal $(w, S)$-good separation $(A', B')$ extending $(A, B)$ in $G$. In particular, $|V(A') \cap V(B')| \le |V(F)|$.

The next step of the proof is illustrated in Figure 3. By Lemma 12, there exists a separation $(P, Q)$ such that $(A, B) \le (P, Q) \le (A', B')$ and there is a family $\mathcal{L}$ of $|V(P) \cap V(Q)|$ disjoint $V(A)-V(B')$ paths in $G$. If $|V(P) \cap V(Q)| \le |V(F)| - 1$, then by Lemma 11, since $(A', B')$ is $(w, S)$-good, $(P, Q)$ is $(w, S)$-good as well. Since $(P, Q)$ extends $(A^0, B^0)$, and $v \in V(P) - V(A^0)$, this contradicts the maximality of $(A^0, B^0)$. Hence $|V(P) \cap V(Q)| \ge |V(F)|$. Setting $B_t = \{v\}$ gives a $(V(A) \cap V(B))$-rooted model $(B_x | x \in V(F))$ of $F$ in $A$. Since $(A, B) \le (A', B')$, every $V(A)-V(B')$ path is a $(V(A) \cap V(B))-(V(A') \cap V(B'))$-path contained in $V(B) \cap V(A')$. Therefore, the model can be extended using $|V(F)|$ paths in $\mathcal{L}$ yielding a $(V(A') \cap V(B'))$-rooted model of $F$ in $A'$. This proves that $(A', B')$ satisfies (s1)-(s3). $\square$

<figure><img src="image_4.png" /><figcaption>FIGURE 3. An illustration of the proof of Lemma 13. We consider $F$ to be a forest ($|V(F)| = 5$ in the figure). In pink, we depict the branch sets of the rooted model of $F-t$. We argue that if $|V(P) \cap V(Q)| < |V(F)|$, then $(P, Q)$ contradicts the maximality of $(A^0, B^0)$. Hence, $V(A)$ is connected with $V(B')$ by 5 pairwise disjoint paths. We add the blue branch set containing $v$ to the model and extend pink branch sets using the paths obtaining a $(V(A') \cap V(B'))$-rooted model of $F$ in $A'$.</figcaption></figure>

*Proof of Theorem 7.* The proof is illustrated in Figure 4. Let $F$ be a forest with at least one vertex, let $G$ be a graph, and let $S \subseteq V(G)$ such that $G$ has no $S$-rooted model of $F$. Suppose that $pw(G, S) > 2|V(F)| - 2$ and let $w = |V(F)|$. By Lemma 13, $G$ admits a separation $(A, B)$ satisfying (s1)-(s3). Let $(W_i | i \in [m])$ be a path decomposition of $(A, S \cap V(A))$ of width at most $2w - 2$ with $V(A) \cap V(B) \subseteq W_m$. By Menger's Theorem applied to $V(A)$ and $S \cap V(B)$ there is a separation $(P, Q)$ of $G$ with $V(A) \subseteq V(P)$, $S \cap V(B) \subseteq V(Q)$ and a family $\mathcal{L}$ of $|V(P) \cap V(Q)|$ pairwise disjoint $V(A)-(S \cap V(B))$ paths in $G$.

First, suppose that $|V(P) \cap V(Q)| < |V(F)|$. Then we claim that $(W_1, \dots, W_m, (V(A) \cap V(B)) \cup (V(P) \cap V(Q)))$ is a path decomposition of $(P, S \cap V(P))$ of width at most $2w - 1$.
whose last bag contains $V(P) \cap V(Q)$. Indeed, $|V(A) \cap V(B)| + |V(P) \cap V(Q)| - 1 \le 2w - 2$.
Let $C$ be a component of $P - (\bigcup_{i \in [m]} W_i \cup (V(P) \cap V(Q)))$. Since $V(A) \cap V(B) \subseteq W_m$, either
$C$ is a component of $A - \bigcup_{i \in [m]} W_i$ or $C$ is a component of $P - (V(A) \cup (V(P) \cap V(Q)))$.
In the former case, there is $i \in [m]$ such that the neighborhood of $V(C)$ in $A$ (and so in
$P$) is contained in $W_i$. In the latter case, the neighborhood of $V(C)$ in $P$ is contained in
$(V(A) \cap V(B)) \cup (V(P) \cap V(Q))$. Hence, $(P, Q)$ is $(w, S)$-good, which contradicts the maximality
of $(A, B)$ because $(P, Q)$ extends $(A, B)$ and $|V(P) \cap V(Q)| < |V(F)| = |V(A) \cap V(B)|$.

It follows that $|V(P) \cap V(Q)| \ge |V(F)|$. By (s2), there is a $(V(A) \cap V(B))$-rooted model of $F$ in $A$. The model combined with the paths in $\mathcal{L}$ yields an $S$-rooted model of $F$ in $G$. This contradicts the assumption on $G$ and ends the proof of the theorem. $\square$

<figure><img src="image_5.png" /><figcaption>FIGURE 4. An illustration of the proof of Theorem 7. On the left, we depict the situation, where $|V(P) \cap V(Q)| < |V(F)|$. We can extend the path decomposition by appending the bag $(V(A) \cap V(B)) \cup (V(P) \cap V(Q))$ (the last green bag in the figure). On the right, we depict the opposite situation, where $|V(P) \cap V(Q)| \ge |V(F)|$. Then, we simply extend the model and make it $S$-rooted.</figcaption></figure>

Finally, we proceed with a proof of Theorem 1. The proof is by induction, however, since we need to keep some invariant stronger than the statement of the theorem, we encapsulate it in the following technical lemma, which we later show implies the theorem.

**Lemma 14.** Let $X$ be an apex-forest with at least two vertices. Let $G$ be a connected graph and let $u$ be a vertex of $G$. If $G$ is $X$-minor-free, then $G$ has a layering ($L_j$ | $j \ge 0$) and there is a path decomposition ($W_i$ | $i \in [m]$) of $G - u$ with

(i) $L_0 = \{u\}$, and

(ii) $|W_i \cap L_j| \le 2|V(X)| - 3$, for all $i \in [m]$ and $j \ge 1$.

*Proof.* Let $x$ be a vertex of $X$ such that $X - x$ is a forest, which we denote by $F$. We proceed by induction on $|V(G)|$. If $G$ has only one vertex, then the result is clear. Hence, assume that $G$ has more vertices.

Let $S = N(u)$ and $G' = G - u$. Observe that $G'$ has no $S$-rooted model of $F$, as otherwise, this model together with a branch set $\{u\}$ added would give a model of $X$ in $G$. By Theorem 7, there is a path decomposition of $(G', S)$ of width at most $2|V(F)| - 2 = 2|V(X)| - 4$. Let $(V_i | i \in [m_0])$ be such a path decomposition of $(G', S)$ with $U = \bigcup_{i \in [m_0]} V_i$ of minimum size.

Let $C$ be a component of $G' - U$. We claim that $G - V(C)$ is connected. Suppose to the contrary that there exists a component $C'$ of $G - V(C)$ that does not contain $u$. In other words, $C'$ is disjoint from $S = N(u)$. Since $G$ is connected, there is an edge $vw$ in $G$ such that $v \in V(C)$ and $w \in V(C')$. More precisely, $w \in U$ since otherwise $C$ is not a component
of $G - U$. It follows that $U' = U - V(C')$ is strictly less than $U$. For every component $C''$ of $G' - U'$, either $C''$ is a component of $G' - U$, or $V(C'') = V(C') \cup V(C)$. Since $C'$ has not neighbors in $U'$, in both cases, there exists $i \in [m_0]$ such that $N(V(C'')) \subseteq V_i - V(C')$. Hence $(V_i - V(C') | i \in [m_0])$ is a path decomposition of $(G', S)$. The width of this path decomposition is at most $2|V(X)| - 4$, which contradicts the minimality of $U$.

Let $G_C$ be obtained from $G$ by contracting $V(G) - V(C)$ into a single vertex $u_C$, in particular, $G_C$ is a minor of $G$ and therefore $G_C$ is $X$-minor-free. Since $G$ is connected, $S$ is non-empty, thus, $|V(G_C)| \le |V(G)| - |S \cup \{u\}| + 1 \le |V(G)| - 1$. Hence, by induction hypothesis, there is a layering $(L_{C,j} | j \ge 0)$ and a path decomposition $(V_{C,i} | i \in [m_C])$ of $G_C - u_C$ such that

$$L_{C,0} = \{u_C\} \text{ and } |V_{C,i} \cap L_{C,j}| \le 2|V(X)| - 3, \text{ for every } i \in [m_C] \text{ and } j \ge 1.$$

Let $L_0 = \{u\}$, $L_1 = U$, and for every $j \ge 2$, $L_j = \bigcup_C L_{C,j-1}$ where $C$ goes over all components of components of $G' - U$. See Figure 5. We claim that $(L_j | j \ge 0)$ is a layering of $G$. Indeed, every edge of $G$ is either inside a layer or between two consecutive layers of $(L_j | j \ge 0)$ since $N(u) = S \subseteq U = L_1$, and $N(V(C)) \subseteq L_1$ and $(L_{C,j} | j \ge 0)$ is a layering of $C$, for every component $C$ of $G' - U$.

<figure><img src="image_6.png" /><figcaption>FIGURE 5. An illustration of how we construct the layering $(L_j | j \ge 0)$ in the proof of Lemma 14.</figcaption></figure>

For every component $C$ of $G' - U$, fix some $\alpha(C) \in [m_0]$ such that the neighborhood of $V(C)$ in $G$ is contained in $V_{\alpha(C)}$. Moreover, let the path decomposition obtained as a concatenation of the path decompositions $(V_{C,i} | i \in [m_C])$ for every component $C$ of $G' - U$ with $\alpha(C) = k$ be denoted by $(V_{k,i} | i \in [m_k])$ where $m_k = \sum_C m_C$. For every $k \in [m_0]$, let $V'_{k,0} = V_k$ and $V'_{k,i} = V_{k,i} \cup V_k$ for every $i \in [m_k]$. Observe that $(V'_{k,i} | 0 \le i \le m_k)$ is a path decomposition of the subgraph of $G'$ induced by $V_k \cup \bigcup_C V(C)$ where $C$ goes over all components of $G' - U$ with $\alpha(C) = k$. Now, let $(W_i | i \in [m])$ be the concatenation of the path decompositions $(V'_{k,i} | 0 \le i \le m_k)$ for each $k \in [m_0]$ in the increasing order of $k$. Here, $m = \sum_{k=1}^{m_0} (m_k + 1)$. This yields a path decomposition of $G - u$. This construction is illustrated in Figure 6.

Finally, we argue that the width of $((W_i | i \in [m]), (L_j | j \ge 0))$ is at most $2|V(F)| - 3$. For every $i \in [m]$, we have $W_i \cap L_1 = W_i \cap U = V_k$ for some $k \in [m_0]$, and so, $|W_i \cap L_1| \le 2|V(X)| - 3$. On the other hand, for every $j \ge 2$ and $i \in [m]$, we have $W_i \cap L_j = V_{C,l} \cap L_{C,j-1}$ for some $C$ component of $G' - U$ and $l \in [m_k]$, which gives $|W_i \cap L_j| \le 2|V(X)| - 3$ and ends the proof. $\square$

*Proof of Theorem 1.* Let $X$ be an apex-forest with at least two vertices, and let $G$ be an $X$-minor-free graph. If $G$ has no vertex, then the result is clear. Hence, we assume that $V(G)$ is non-empty. When $G$ is connected, apply Lemma 14 to $G$ with an arbitrary vertex $u \in V(G)$. We obtain a path decomposition $(W_i | i \in [m])$ of $G - u$ and a layering $(L_j | j \ge 0)$ of $G$ such that $|W_i \cap L_j| \le 2|V(X)| - 3$, for every $i \in [m]$ and $j \ge 1$, and $L_0 = \{u\}$. Then
<figure><img src="image_7.png" /><figcaption>FIGURE 6. An illustration of how we construct the path decomposition $(W_i | \{i \in [m]\})$ in the proof of Lemma 14.</figcaption></figure>

$(W_i \cup \{u\} | i \in [m])$ is a path decomposition of $G$ such that every bag has intersection with every layer of $(L_j | j \ge 0)$ of size at most $2|V(X)| - 3$. When $G$ is not connected, apply the above to each component of $G$ and concatenate the layerings and the path decompositions. □

## 5. LAYERED TREEDEPTH

In this section, we prove Theorem 6 and Theorem 2. In the preliminaries section, we stated the definition of treedepth via elimination trees. Treedepth can be also equivalently defined inductively. Namely, treedepth of a graph is the maximum of treedepth of its components, treedepth of the one-vertex graph is 1, and when a graph $G$ has more than one vertex and is connected, treedepth is the minimum over all vertices $v \in V(G)$ of $\text{td}(G - v) + 1$. The new version of treedepth that we proposed in Section 3 also admits an inductive definition, which we state in terms of properties (t1) to (t3). Let $G$ be a graph, and $S \subseteq V(G)$.

(t1) If $S = \emptyset$, then $\text{td}(G, S) = 0$.

(t2) If $V(G) \neq \emptyset$, then $\text{td}(G, S) = \max_C \text{td}(C, S \cap V(C))$, where $C$ goes over all components of $G$.

(t3) If $G$ is connected and $S \neq \emptyset$, then $\text{td}(G, S) = 1 + \min_{u \in V(G)} \text{td}(G - u, S - \{u\})$.

It immediately follows that treedepth is monotone in the following sense.

(t4) If $H$ is a subgraph of $G$, then $\text{td}(H, S \cap V(H)) \le \text{td}(G, S)$.

A depth-first-search tree, DFS tree for short, of $G$ is a rooted spanning tree $T$ of $G$ such that $T$ is an elimination forest of $G$. We proceed with the proof of Theorem 6, the key inductive step is encapsulated in the following lemma.

**Lemma 15.** Let $G$ be a connected graph, let $S \subseteq V(G)$, and let $T$ be a DFS tree of $G$. For every positive integer $\ell$, if for each root-to-leaf path $P$ in $T$, there are no $\ell$ pairwise disjoint $V(P)-S$ paths in $G$, then

$$ \text{td}(G, S) \le \binom{\ell}{2}. $$

*Proof.* We proceed by induction on $\ell$. If $\ell = 1$, then we set $S = \emptyset$, and so, $\text{td}(G, S) = 0$ by (t1). Now, assume that $\ell \ge 2$.

For every $u \in V(G)$, let $T_u$ be the subtree of $T$ rooted in $u$, and let $G_u = G[V(T_u)]$. Let $s_0 \in V(G)$ be the vertex with maximum depth in $T$ such that $S \subseteq V(T_{s_0})$. Let $R$ be the path from the root to $s_0$ in $T$. By assumption, there are no $\ell$ pairwise disjoint $V(R)-S$ paths.
Hence by Menger's Theorem, there is a separation $(A, B)$ of $G$ of order at most $\ell-1$ such that $V(R) \subseteq V(A)$ and $S \subseteq V(B)$. In particular, every $V(R)-S$ path intersects $X = V(A) \cap V(B)$.

Consider a component $C$ of $G-X$. If $C$ has no vertex in $S$, then $\text{td}(C, S \cap V(C)) = 0$. Therefore, we assume the opposite, namely, $V(C) \subseteq V(T_{s_0}) - \{s_0\}$. It follows that there is a child $v$ of $s_0$ with $V(C) \subseteq V(T_v)$. The next goal is to apply induction to $G_v$ – this step is illustrated in Figure 7. To this end, we claim that for every root-to-leaf path $P'$ in $T_v$ there are no $\ell-1$ pairwise disjoint $V(P')-S$ paths in $G_v$. Suppose to the contrary that there is such a root-to-leaf path $P'$. Let $P$ be the path connecting the root of $T$ and the unique leaf in $P'$. By the maximality of $s_0$, $S \not\subseteq V(T_v)$, hence, there is $w \in S$ such that $w \notin V(T_v)$. Let $Q$ be the shortest path from $s_0$ to $w$ in $T$. Note that $Q$ is a $V(R)-S$ path, and $Q$ disjoint from $V(T_v)$. Therefore, the $\ell-1$ pairwise disjoint $V(P')-S$ paths in $G_v$ and $Q$ form a collection of $\ell$ pairwise disjoint $V(P)-S$ paths in $G$, which is a contradiction.

By inductive hypothesis applied to $G_v$ and $T_v$ we obtain $\text{td}(G_v, S \cap V(G_v)) \le \binom{\ell-1}{2}$. By repeating the above reasoning for every component of $G-X$ and (t4), this yields $\text{td}(C, S \cap V(C)) \le \binom{\ell-1}{2}$ for every component of $G-X$. In particular, by (t2), $\text{td}(G-X, S-X) \le \binom{\ell-1}{2}$. Finally, by (t3),

$$ \text{td}(G, S) \le |X| + \text{td}(G-X, S-X) \le (\ell-1) + \binom{\ell-1}{2} = \binom{\ell}{2}. \quad \square $$

<figure><img src="image_8.png" /><figcaption>FIGURE 7. An illustration to the proof of Lemma 15. In the figure $\ell = 5$. On the left, we illustrate the proof by contradiction that induction can be applied to $G_v$. On the right, we illustrate an elimination tree that is built in the proof.</figcaption></figure>

*Proof of Theorem 6.* Let $\ell$ be a positive integer, let $G$ be a graph, and let $S \subseteq V(G)$. We can assume that $G$ is connected due to (t2). Assume that $G$ has no $S$-rooted model of $P_\ell$, and suppose to the contrary that $\text{td}(G, S) > \binom{\ell}{2}$. Then, by Lemma 15 applied with an arbitrary DFS-tree of $G$, there is a path $P$ in $G$ and $\ell$ pairwise disjoint $V(P)-S$ paths in $G$. These paths, together with $P$, give an $S$-rooted model of $P_\ell$ in $G$. This is a contradiction, which ends the proof. $\square$

In the second part of this section, we prove Theorem 2. The proof is quite similar to the second part of the proof of Theorem 1 in terms of structure and content. Again, we first prove a technical lemma and then derive the theorem.
**Lemma 16.** Let $X$ be a fan with at least one vertex. Let $G$ be a connected graph and let $u$ be a vertex of $G$. If $G$ is $X$-minor-free, then $G$ has a layering $(L_j | j \ge 0)$ and there is an elimination forest $F$ of $G - u$ with

(i) $L_0 = \{u\}$, and

(ii) $|V(P) \cap L_j| \le (|V(X)|-1)/2$ for every root-to-leaf path $P$ in $F$ and for every $j \ge 1$.

*Proof.* Let $x$ be a vertex of $X$ such that $X - x$ is a path, and let $\ell = |V(X)| - 1$. If $\ell = 0$, then the result is vacuously true, thus, we assume that $\ell > 0$. We proceed by induction on $|V(G)|$. If $G$ has only one vertex, then the result is clear. Hence, assume that $G$ has more vertices.

Let $S = N(u)$ and $G' = G - u$. Observe that $G'$ has no $S$-rooted model of $P_\ell$ as otherwise, this model together with a branch set $\{u\}$ added would give a model of $X$ in $G$. By Theorem 6, there is an elimination forest of $(G', S)$ of vertex-height at most $\binom{\ell}{2}$. Let $F'$ be such a forest with $|V(F')|$ minimum.

Let $C$ be a component of $G' - V(F')$. We claim that $G - V(C)$ is connected. Suppose to the contrary that there exists a component $C'$ of $G - V(C)$ that does not contain $u$. In other words, $C'$ is disjoint from $S = N(u)$. Since $G$ is connected, there is an edge $vw$ in $G$ such that $v \in V(C)$ and $w \in V(C')$. More precisely, $w \in V(F')$ since otherwise, $C$ is not a component of $G - V(F')$. It follows that $V(F') - V(C')$ is strictly less than $V(F')$. Let $F''$ be the forest with the vertices $V(F') = V(C')$, where for all $x, y \in V(F')$, we have $xy \in E(F'')$ whenever there is an $\{x\}-\{y\}$ path in $F'$ with all internal vertices in $V(C')$. For every component $C''$ of $G' - V(F'')$, either $C''$ is a component of $G' - V(F')$, or $V(C'') = V(C') \cup V(C)$. Since $C'$ has not neighbors in $V(F'')$, in both cases, there exists a root-to-leaf path containing the neighborhood of $V(C')$ in $G'$. Hence $F''$ is an elimination forest of $(G', S)$. The vertex-height of $F'$ is at most $\binom{\ell}{2}$, which contradicts the minimality of $F'$.

Let $G_C$ be obtained from $G$ by contracting $V(G) - V(C)$ into a single vertex $u_C$, in particular, $G_C$ is a minor of $G$ and therefore $G_C$ is $X$-minor-free. Since $G$ is connected, $S$ is non-empty, thus, $|V(G_C)| \le |V(G)| - |S \cup \{u\}| + 1 \le |V(G)| - 1$. Hence, by induction hypothesis, there is a layering $(L_{C,j} | j \ge 0)$ and an elimination forest $F_C$ of $G_C - u_C$ such that

$$L_{C,0} = \{u_C\} \text{ and } |V(P) \cap L_{C,j}| \le \binom{\ell}{2}, \text{ for every root-to-leaf path } P \text{ in } F_C \text{ and } j \ge 1.$$

Let $L_0 = \{u\}$, $L_1 = V(F')$, and for every $j \ge 2$, $L_j = \bigcup_C L_{C,j-1}$ where $C$ goes over all components of $G' - V(F')$. We claim that $(L_j | j \ge 0)$ is a layering of $G$. Indeed, every edge of $G$ is either inside a layer or between two consecutive layers of $(L_j | j \ge 0)$ since $N(u) = S \subseteq V(F') = L_1$, and $N(V(C)) \subseteq L_1$ and $(L_{C,j} | j \ge 0)$ is a layering of $C$, for every component $C$ of $G' - U$.

Let $Z$ be the set of all leaves of $F'$, and for each $y \in Z$, let $P_y$ be the path from the root of $F'$ to $y$ in $F'$. For every component $C$ of $G' - V(F')$, fix some $\alpha(C) \in Z$ such that the neighborhood of $V(C)$ in $G$ is contained in $P_{\alpha(C)}$. Let $F$ be a forest obtained from $F'$ in the following way. For each component $C$ of $G - V(F')$ add $F_C$ and edges of the form $\alpha(C)x$ for every $x$ root of $F_C$. Let the set of roots of $F$ be the same as $F'$. It follows that $F$ is an elimination forest of $G - u$.

Finally, let $P$ be a root-to-leaf path in $F$. We have $|V(P) \cap L_1| \le \binom{\ell}{2}$ since $V(P) \cap L_1$ is a vertex set of a root-to-leaf path of $F'$. For every $j \ge 2$, $V(P) \cap L_j \subseteq V(F_C)$ for some component $C$ of $G' - V(F')$, which implies $|V(P) \cap L_j| = |V(P) \cap L_{C,j-1}| \le \binom{\ell}{2}$. This proves the lemma. $\square$
*Proof of Theorem 2.* Let $X$ be a fan with at least three vertices, and let $G$ be an $X$-minor-free graph. If $G$ has no vertex, then the result is clear. Hence, we assume that $V(G)$ is non-empty. When $G$ is connected, apply Lemma 16 to $G$ with an arbitrary vertex $u \in V(G)$. We obtain an elimination forest $F$ of $G-u$ and a layering $(L_j | j \ge 0)$ of $G$ such that $|V(P) \cap L_j| \le (|V^{(X)}| - 1)$, for every root-to-leaf path $P$ and for every $j \ge 1$, and $L_0 = \{u\}$. Let $T$ be obtained by adding $u$ to $F$ as a new root adjacent to all the roots of $F$. Then $T$ is an elimination tree of $G$ witnessing that $\text{ltd}(G, S) \le (|V^{(X)}| - 1)$. When $G$ is not connected, apply the above to each component of $G$, take for $F$ the disjoint union of the elimination forests obtained for each component, and concatenate the layerings.
□

## 6. TREEWIDTH AND TANGLES FOCUSED ON A SET OF VERTICES

In this section, we prove Theorem 10. Let $G$ be a graph with at least one vertex, and $S \subseteq V(G)$. Lemma 17 directly implies the upper bound, that is, $\text{tw}(G, S) \le 10 \max\{\text{tn}(G, S), 2\} - 12$. Lemma 19 implies the lower bound, that is, $\text{tn}(G, S) - 1 \le \text{tw}(G, S)$.

**Lemma 17.** Let $k$ be an integer with $k \ge 2$. Let $G$ be a graph and let $S \subseteq V(G)$ be such that there is no tangle of $(G, S)$ of order $k$. Then for every $R \subseteq V(G)$ with $|R| \le 7k - 8$, there is a tree decomposition $\mathcal{D}$ of $(G, S)$ of width at most $10k - 12$ such that there is a bag of $\mathcal{D}$ containing $R$.

*Proof.* We proceed by induction on $|V(G)|$. If $|V(G)| \le 10k - 11$, then the tree decomposition consisting of a single bag $V(G)$ witnesses the statement. Thus, we assume that $|V(G)| \ge 10k - 10 \ge 7k - 8$. By possibly adding some vertices to $R$, we assume without loss of generality that $|R| = 7k - 8$.

Let $\mathcal{T}$ be the family of all separations $(A, B)$ of $G$ of order at most $k-1$ such that $|V(A) \cap R| \le 4k-5$. By assumption, $\mathcal{T}$ is not a tangle of $(G, S)$. Therefore, one of (T1)-(T4) does not hold.

If (T1) does not hold, then there is a separation $(A, B)$ of $G$ of order at most $k-1$ such that $|V(A) \cap R| \ge 4k-4$ and $|V(B) \cap R| \ge 4k-4$. Then $|R| \ge |V(A) \cap R| + |V(B) \cap R| - |V(A) \cap V(B)| \ge 8k-8-(k-1) = 7k-7 > 7k-8$, a contradiction.

If (T2) does not hold, then there are separations $(A_1, B_1), (A_2, B_2), (A_3, B_3)$ in $\mathcal{T}$ such that $A_1 \cup A_2 \cup A_3 = G$. Let $Z = \cup_{i=1}^3 V(A_i) \cap V(B_i)$. Let $C$ be a component of $G-Z$, let $G_C = G[V(C) \cup N(C)]$, let $R_C = N(V(C)) \cup (R \cap V(C))$. Since $V(C) \subseteq V(A_i)$ for some $i \in \{1, 2, 3\}$, $|V(C) \cap R| \le |V(A_i) \cap R| \le 4k-5$. Note that $V(G_C) = V(C) \cap N(C) \subseteq A_i$, and thus,

$$|V(G) - V(G_C)| \ge |V(B_i) - V(A_i)| \ge |(V(B_i) - V(A_i)) \cap R| \ge 3k - 3 > 0.$$

Moreover, since $N(V(C)) \subseteq Z$, $|N(V(C))| \le |Z| = 3(k-1)$. Hence, $|R_C| \le |V(C) \cap R| + |N(V(C))| \le 4k-5+3k-3 = 7k-8$. In order to apply induction to $G_C$ and $R_C$, we have to argue that $|V(G_C)| < |V(G)|$. We have $V(C) \cup N(C) \subseteq A_i$ for some $i \in \{1, 2, 3\}$. By induction hypothesis applied to $G_C$ and $R_C$, there is a tree decomposition $(T_C, (W_{C,x} | x \in V(T_C)))$ of $(G_C, S \cap V(G_C))$ of width at most $10k - 12$ such that $R^C \subseteq W_{C,r_C}$ for some $r_C \in V(T_C)$. Let $T$ be obtained from the disjoint union of $T_C$ for all components $C$ of $G-Z$ by adding a new vertex $r$ and edges $rr_C$ for every component $C$ of $G-Z$. Finally, let $W_r = Z \cup R$, and for every component $C$ of $G-Z$ and every $x \in V(T_C)$, let $W_x = W_{C,x}$. Observe that $|W_r| \le |Z| + |R| \le 3(k-1) + 7k - 8 = 10k - 11$. Every component of $G - \cup_{x \in V(T_C)} W_x$ is a subgraph of a component of $G_C - \cup_{x \in V(T_C)} W_{C,x}$ for some component $C$ of $G-Z$. Therefore,
$(T, (W_x | x \in V(T)))$ is a tree decomposition of $(G, S)$ of width at most $10k - 12$ such that $R \subseteq W_r$.

If (T3) does not hold, then there is a separation $(A, B) \in \mathcal{T}$ such that $V(A) = V(G)$. It follows that $|R| = |R \cap V(A)| \le 4k - 5 < 7k - 8 = |R|$, a contradiction.

If (T4) does not hold, then there is a separation $(A, B) \in \mathcal{T}$ such that $S \subseteq V(A)$. Let $R' = (R \cap V(A)) \cup (V(A) \cap V(B))$. Note that $|R'| \le 4k - 5 + (k - 1) = 5k - 6 \le 7k - 8$. By induction hypothesis applied to $A$ and $R'$, there is tree decomposition $(T', (W_x | x \in V(T')))$ of $(A, S \cap V(A))$ of width at most $10k - 12$ such that $R' \subseteq W_{r'}$ for some $r' \in V(T')$. Let $T$ be obtained from $T'$ by adding a new vertex $r$ and the edge $rr'$. Finally, set $W_r = R \cup (V(A) \cap V(B))$ and observe that $|W_r| \le |R| + k - 1 \le 7k - 8 + k - 1 = 8k - 9 \le 10k - 12$. Every component of $G - \bigcup_{x \in V(T)} W_x$ is either a component of $B - A$ or is a subgraph of a component of $A - \bigcup_{x \in V(T')} W_x$. In both cases, the neighborhood of the component is contained in a single bag. Therefore, $(T, (W_x | x \in V(T)))$ is a tree decomposition of $(G, S)$ of width at most $10k - 12$ such that $R \subseteq W_r$. $\square$

In the proof of Lemma 19 we use the following simple observation.

**Observation 18.** Let $k$ be a positive integer, let $G$ be a graph, and let $\mathcal{T}$ be a tangle of $G$ of order $k$. Let $(A, B)$ and $(A', B')$ be two separations of $G$ of order at most $k - 1$ such that $V(A) = V(A')$ and $V(B) = V(B')$. Then,

$$ (B, A) \notin \mathcal{T} \iff (A, B) \in \mathcal{T} \iff (A', B') \in \mathcal{T} \iff (B', A') \notin \mathcal{T}. $$

*Proof.* The first and last equivalences are clear by (T1) and (T2). In order to prove the middle equivalence, suppose to the contrary that $(A, B) \in \mathcal{T}$ and $(A', B') \notin \mathcal{T}$. By (T2), $(B', A') \in \mathcal{T}$. Observe that $(A \cup B', A' \cap B)$ is a separation of $G$, and its order is at most $k - 1$. By (T3), $(A \cup B', A' \cap B) \notin \mathcal{T}$, hence by (T1), $(A' \cap B, A \cup B') \in \mathcal{T}$. But then $B' \cup A \cup (A' \cap B) = G$, which contradicts (T3). $\square$

**Lemma 19.** Let $k$ be a positive integer, let $G$ be a graph with at least one vertex, and let $S \subseteq V(G)$. If $\tn(G, S) \ge k$, then $\text{tw}(G, S) \ge k - 1$.

*Proof.* Let $\mathcal{T}$ be a tangle of $(G, S)$ of order $k$. Suppose to the contrary that there is a tree decomposition $(T_0, (W_x | x \in V(T_0)))$ of $(G, S)$ of width at most $k - 2$. Let $U = \bigcup_{x \in V(T_0)} W_x$. By possibly adding some vertices to $T_0$ and some bags to $(W_x | x \in V(T_0))$, without loss of generality we can assume that every vertex in $U$ is in at least two bags. For every component $C$ of $G - U$, there is a bag $x_C \in V(T_0)$ such that $N(V(C)) \subseteq W_{x_C}$. Let $T$ be obtained from $T_0$ by adding a new vertex $u_C$ and the edge $x_C u_C$ for every component $C$ of $G - U$. Let $W_{u_C} = N(V(C)) \cup V(C)$ for every component $C$ of $G - U$. It follows that $(T, (W_x | x \in V(T)))$ is a tree decomposition $(T, (W_x | x \in V(T)))$ of $G$. While this tree decomposition may have large width, for every edge $xy \in E(T)$, we have $|W_x \cap W_y| \le k - 1$.

Let $Z = V(T) - V(T_0)$ be the set of all added vertices. For every $uv \in E(T)$, let $T_{uv}$ be the component of $T - uv$ containing $u$, and let $G_{uv}$ be the subgraph $G[\bigcup_{x \in V(T_{uv})} W_x]$.

Let $\vec{T}$ be the directed graph with the vertex set $V(T)$ and the arc set consisting of all the pairs $(u, v) \in V(T)^2$ such that $uv \in E(T)$ and for every separation $(A, B)$ of $G$ with $V(A) = V(G_{uv})$ and $V(B) = V(G_{vu})$, we have $(A, B) \in \mathcal{T}$. By Observation 18, $\vec{T}$ is an orientation of $T$. Since $T$ is a tree, $\vec{T}$ is acyclic, and thus, there is a sink $x$ in $\vec{T}$. If $x \in Z$, then the neighbor $y$ of $x$ in $T$ is such that $(G_{yx}, G_{xy} - E(G_{yx})) \in \mathcal{T}$, which contradicts (T4) since $S \subseteq V(G_{yx})$. Hence, $x \notin Z$,
and so, $|W_x| \le k - 1$. Let $y_1, \dots, y_d$ be the neighbors of $x$ in $T$. For every $i \in [d]$, let $(A_i, B_i)$ be a separation of $G$ with $A_i = G[\bigcup_{j=1}^i V(G_{y_j x})]$ and $B_i = G[\bigcap_{j=1}^i V(G_{x_j y})] - E(A_i)$. It follows that $V(A_i) \cap V(B_i) \subseteq W_x$. Therefore, $(A_i, B_i)$ has order at most $|W_x| \le k - 1$ for every $i \in [d]$.

We claim that $(A_i, B_i) \in \mathcal{T}$ for every $i \in [d]$. We prove this by induction on $i$. The fact that $x$ is a sink implies that $(A_1, B_1) \in \mathcal{T}$, hence, let $1 < i \le d$, and assume that $(A_{i-1}, B_{i-1}) \in \mathcal{T}$. Suppose to the contrary that $(B_i, A_i) \in \mathcal{T}$. Since $(A_{i-1}, B_{i-1}) \in \mathcal{T}$ and $(G_{y_i x}, G_{x_i y} - E(G_{y_i x}) \in \mathcal{T}$ by (T2), $A_{i-1} \cup G_{y_i x} \cup B_i \ne G$, which is false since $A_i = A_{i-1} \cup G_{y_i x}$, and yields $(A_i, B_i) \in \mathcal{T}$.

The above in particular, implies that $(A_d, B_d) \in \mathcal{T}$. However, since every vertex in $U$ is in at least two bags, we have $V(G) = \bigcup_{z \in V(T) - \{x\}} W_z = V(A)$, which contradicts (T3), and shows that there is no tree decomposition of $(G, S)$ of width at most $k - 2$. $\square$

## 7. A LOWER BOUND FOR COROLLARIES 3 AND 4

Let $G$ be a graph. Recall that the radius of a graph is the minimum over all vertices $u \in V(G)$ of $\max_{v \in V(G)} \text{dist}_G(u, v)$ and that it is at least half of the diameter of $G$.

**Theorem 20.** Let $\ell$ and $r$ be integers such that $\ell \ge 2$ and $r \ge 0$. There is a fan $X$ on at least $\ell + 1$ vertices and an $X$-minor-free graph $G$ with radius at least $r$ such that

$$ \text{td}(G) - 1 \ge \text{pw}(G) \ge \lfloor \frac{\ell}{2} \rfloor \left( r - \lfloor \frac{\ell}{2} \rfloor \right). $$

*Proof.* Let $X$ be the graph obtained from the path on $\ell$ vertices by adding a universal vertex $x$. Let $k$ be an integer such that $k \ge \frac{1}{2}\ell r$, and let $T$ be a rooted complete ternary tree of vertex-height $k + 1$. Let $G = T$ when $\ell < 4$. When $\ell \ge 4$, let $G$ be obtained from $T$ in the following way. For every integer $i$ such that $0 \le i \le (1/\lfloor \frac{\ell}{2} \rfloor)k - 1$, for every vertex $u$ at depth $1 + \lfloor \frac{\ell}{2} \rfloor$ $i$ and every vertex $v$ at depth $1 + \lfloor \frac{\ell}{2} \rfloor$ $(i + 1)$ such that $u$ is an ancestor of $v$, we add the edge $uv$. See Figure 8.

First, we show that $G$ is $X$-minor-free. If $\ell < 4$, then $X$ contains a cycle and $G$ is a tree, which cannot have $X$ as a minor. Thus, we assume that $\ell \ge 4$. Suppose to the contrary that $G$ contains a model of $X$, and let $\mathcal{X}$ be such a model that is inclusion-wise minimal. Since $X$ is 2-connected, $\mathcal{X}$ must be contained in a 2-connected subgraph of $G$. Consider a maximal 2-connected subgraph $H$ of $G$ containing $\mathcal{X}$. Let $u$ be the vertex in $V(H)$ with minimum depth in $T$. By construction of $G$, $H - u$ is a rooted complete ternary tree $T'$ with vertex-height $\lfloor \frac{\ell}{2} \rfloor$, the root of $T'$ is the only child of $u$ in $V(H)$, and $uv$ is an edge of $H$ for every leaf $v$ of $T'$. The branch set of $x$ in $\mathcal{X}$ must contain $u$, as otherwise, $H - u = T'$ does not contain a model of $K_3$. Therefore, $T'$ must contain a model of a path on $\ell$ vertices, but the longest path in $T'$ has only $2 \lfloor \frac{\ell}{2} \rfloor - 1 < \ell$ vertices. This is a contradiction, thus, $G$ is $X$-minor-free.

By symmetry of the construction, the radius of $G$ is witnessed by the root of $G$. Let $t$ be the root of $G$, and let $v$ be a vertex in $T$ of depth $i$ for some integer $i$ with $1 \le i \le k + 1$. We have, $\text{dist}_G(t, v) \le (1/\lfloor \frac{\ell}{2} \rfloor)(i - 1) + \lfloor \frac{\ell}{2} \rfloor \le (1/\lfloor \frac{\ell}{2} \rfloor)k + \lfloor \frac{\ell}{2} \rfloor$, hence, the radius of $G$ is at most $(1/\lfloor \frac{\ell}{2} \rfloor)k + \lfloor \frac{\ell}{2} \rfloor$. On the other hand, when $v$ is a leaf, $\text{dist}_G(t, v) \ge (1/\lfloor \frac{\ell}{2} \rfloor)k \ge r$ by definition of $k$. So, the radius of $G$ is at least $r$. We obtain $r \le (1/\lfloor \frac{\ell}{2} \rfloor)k + \lfloor \frac{\ell}{2} \rfloor$.

Since $G$ contains a rooted complete ternary tree of vertex-height $k + 1$ as a subgraph, $\text{pw}(G) \ge k$. Moreover, $\text{td}(G) - 1 \ge \text{pw}(G)$. Therefore $G$ is an $X$-minor-free graph $G$ with radius of at least $r$ witnessing the assertion of the theorem. $\square$
<figure><img src="image_9.png" /><figcaption>FIGURE 8. The construction of $G$ in the proof of Theorem 20, for $l = k = 4$ and $r = 2$.</figcaption></figure>

## 8. Erdős-Pósa PROPERTY

In this section, we discuss the applications of our techniques to Erdős-Pósa properties for rooted models. We start with a classical statement by Robertson and Seymour on families of connected subgraphs in graphs of bounded treewidth.

**Lemma 21** ([11], Statement (8.7)). Let $G$ be a graph, let $\mathcal{W} = (T, (W_x | x \in V(T)))$ be a tree decomposition of $G$, and let $\mathcal{F}$ be a family of connected subgraphs of $G$. For every positive integer $k$, either

(i) there are $k$ pairwise vertex-disjoint subgraphs in $\mathcal{F}$ or

(ii) there is a set $Z \subseteq V(G)$ that is the union of at most $k-1$ bags of $\mathcal{W}$ such that $V(F) \cap Z \neq \emptyset$ for every $F \in \mathcal{F}$.

It turns out that the analog version for treewidth focused on a prescribed set of vertices holds.

**Lemma 22.** Let $G$ be a graph, let $S \subseteq V(G)$, let $\mathcal{W} = (T, (W_x | x \in V(T)))$ be a tree decomposition of $(G, S)$, and let $\mathcal{F}$ be a family of connected subgraphs of $G$ each of them intersecting $S$. For every positive integer $k$, either

(i) there are $k$ pairwise vertex-disjoint subgraphs in $\mathcal{F}$ or

(ii) there is a set $Z \subseteq V(G)$ that is the union of at most $k-1$ bags of $\mathcal{W}$ such that $V(F) \cap Z \neq \emptyset$ for every $F \in \mathcal{F}$.

*Proof.* Let $k$ be a positive integer, and suppose that (i) does not hold. For every $F \in \mathcal{F}$, let $T_F = T[\{x \in V(T) | W_x \cap V(F) \neq \emptyset\}]$. It follows that for every $F \in \mathcal{F}$, $T_F$ is a non-empty subtree of $T$.

We claim that if $F_1, F_2 \in \mathcal{F}$ and $V(F_1) \cap V(F_2) \neq \emptyset$, then $V(T_{F_1}) \cap V(T_{F_2}) \neq \emptyset$. Indeed, if $u \in V(F_1) \cap V(F_2)$, then either $u \in W_x$ for some $x \in V(T)$ and so $x \in V(T_{F_1}) \cap V(T_{F_2})$, or $u \in V(C)$ for some component $C$ of $G - \bigcup_{x \in V(T)} W_x$. Then, since $\mathcal{W}$ is a tree decomposition
of $(G, S)$, there exists $x \in V(T)$ such that $N(V(C)) \subseteq W_x$. Moreover, $V(F_i) \cap S \neq \emptyset$, and so, $V(F_i) \cap N(V(C)) \neq \emptyset$, for each $i \in \{1, 2\}$. Hence $x \in V(T_{F_1}) \cap V(T_{F_2})$.

Since (i) is false, we deduce that there are no $k$ disjoint members of $\{T_F \mid F \in \mathcal{F}\}$. Then by Helly property for subtrees of $T$, there are $k-1$ bags of $\mathcal{W}$ whose union $Z$ intersects every member of $\mathcal{F}$. Therefore, (ii) holds. $\square$

Lemma 22 with Theorem 8 yield that outer-rooted models of a fixed connected plane graph admit the Erdős-Pósa property.

**Corollary 23.** For every connected plane graph $H$, there exists a positive integer $d_H$ such that for every graph $G$, for every $S \subseteq V(G)$, and for every positive integer $k$, either

(i) $G$ has $k$ vertex-disjoint $S$-outer-rooted models of $H$ or

(ii) there exists a set $Z \subseteq G$ such that $|Z| \le d_H(k-1)$ and $G-Z$ has no $S$-outer-rooted model of $H$.

*Proof.* Let $H$ be a connected plane graph. For every positive integer $k$, let $k \cdot H$ denote the plane graph consisting of $k$ disjoint copies of $H$ drawn in the plane in such a way that the outer face of each copy belongs to the outer face. Let $c_{k \cdot H}$ be the constant given by Theorem 8 applied to $k \cdot H$. Suppose that $G, S, k$ are like in the statement. Assume that (i) does not hold. In other words, $G$ has no $S$-outer-rooted model of $k \cdot H$. Therefore, $\mathrm{tw}(G, S) \le c_{k \cdot H}$. Then by Lemma 22 applied to the family of all the connected subgraphs of $G$ containing an $S$-outer-rooted model of $H$, there exists a set $Z$ of at most $(c_{k \cdot H} + 1)(k-1)$ vertices in $G$ such that $G-Z$ has no $S$-outer-rooted-model of $H$. $\square$

Recently, Dujmović, Joret, Micek, and Morin [5] showed that for every tree $T$, for every graph $G$, for every positive integer $k$, either $G$ has $k$ disjoint models of $T$, or there is a set $Z$ of at most $|V(T)| (k-1)$ vertices such that $G-Z$ is $T$-minor-free. Theorem 7 and Lemma 22 imply the following Erdős-Pósa property for rooted models of trees.

**Corollary 24.** For every tree $T$, for every graph $G$, for every $S \subseteq V(G)$, and for every positive integer $k$, either

(i) $G$ has $k$ vertex-disjoint $S$-rooted models of $T$ or

(ii) there exists a set $Z \subseteq G$ such that $|Z| \le (2k|V(T)| - 1)(k-1)$ and $G-Z$ has no $S$-rooted model of $T$.

## 9. OPEN PROBLEMS

Some of the bounds that we provided are not tight, we summarize potential improvements below.

*Problem A.* Within Theorem 6, we show that for every positive integer $\ell$, for every graph $G$, and for every $S \subseteq V(G)$, if $G$ has no $S$-rooted model of $P_\ell$, then $\mathrm{td}(G, S) \le \binom{\ell}{2}$. Is there a better bound? Perhaps linear in $\ell$?

*Problem B.* Within Theorem 7 we show that for every forest $F$ with at least one vertex, for every graph $G$, for every $S \subseteq V(G)$, if $G$ has no $S$-rooted model of $F$, then $\mathrm{pw}(G, S) \le 2|V(F)| - 2$. Is there a better bound? Perhaps $|V(F)| - 2$?

*Problem C.* Within Corollary 24 we show the Erdős-Pósa property for $S$-rooted trees with a bound $(2k|V(T)| - 1)(k-1) = \mathcal{O}(k^2)|V(T)|$. Perhaps $\mathcal{O}(k)|V(T)|$?
REFERENCES

[1] Dan Bienstock, Neil Robertson, Paul Seymour, and Robin Thomas. Quickly excluding a forest. *Journal of Combinatorial Theory, Series B*, 52(2):274–283, 1991.

[2] Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, Pat Morin, and David R. Wood. Separating layered treewidth and row treewidth. *Discrete Mathematics & Theoretical Computer Science*, 24(1), 2022. arXiv:2105.01230v3.

[3] Reinhard Diestel. Graph Minors I: A Short Proof of the Path-width Theorem. *Combinatorics, Probability and Computing*, 4(1):27–30, 1995.

[4] Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, and David R. Wood. Minor-closed graph classes with bounded layered pathwidth. *SIAM Journal on Discrete Mathematics*, 34(3):1693–1709, 2020. arXiv:1810.08314.

[5] Vida Dujmović, Gwenaël Joret, Piotr Micek, and Pat Morin. Tight bound for the Erdős-Pósa property of tree minors. *arXiv preprint*, 2024. arXiv:2403.06370.

[6] Vida Dujmović, Pat Morin, and David R. Wood. Layered separators in minor-closed graph classes with applications. *Journal of Combinatorial Theory, Series B*, 127:111–147, 2017. arXiv:1306.1595.

[7] Daniel Marx, Paul Seymour, and Paul Wollan. Rooted grid minors. *Journal of Combinatorial Theory, Series B*, 122:428–437, 2017. arXiv:1307.8138.

[8] Jaroslav Nešetřil and Patrice Ossona de Mendez. *Sparsity*, volume 28 of *Algorithms and Combinatorics*. Springer, 2012.

[9] Christophe Paul, Evangelos Protopapas, and Dimitrios M. Thilikos. Universal obstructions of graph parameters. *arXiv preprint*, 2023. arXiv:2304.14121.

[10] Neil Robertson and Paul Seymour. Graph minors. I. Excluding a forest. *Journal of Combinatorial Theory, Series B*, 35(1):39–61, 1983.

[11] Neil Robertson and Paul Seymour. Graph minors. V. Excluding a planar graph. *Journal of Combinatorial Theory, Series B*, 41(1):92–114, 1986.

[12] Paul Seymour. A shorter proof of the path-width theorem. *arXiv preprint*, 2023. arXiv:2309.05100.