#  Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-
Equivalent

Akanksha Agrawal Indian Institute of Technology Madras, Chennai, India.
<EMAIL_ADDRESS>Lawqueen Kanesh National University of Singapore,
Singapore, Singapore<EMAIL_ADDRESS>Daniel Lokshtanov University of
California Santa Barbara, USA<EMAIL_ADDRESS>Fahad Panolan Indian
Institute of Technology, Hyderabad, India<EMAIL_ADDRESS>M. S.
Ramanujan University of Warwick, Coventry, UK, R.Maadapuzhi-
<EMAIL_ADDRESS>Saket Saurabh The Institute of Mathematical Sciences,
HBNI, Chennai, India, and University of Bergen, Bergen, Norway.
<EMAIL_ADDRESS>Meirav Zehavi Ben-Gurion University of the Negev, Beersheba,
Israel<EMAIL_ADDRESS>
###### Abstract

Vertex-deletion problems have been at the heart of parameterized complexity
throughout its history. Here, the aim is to determine the minimum size
(denoted by $\mathbf{mod}_{\mathcal{H}}$) of a modulator to a graph class
$\mathcal{H}$, i.e., a set of vertices whose deletion results in a graph in
$\mathcal{H}$. Recent years have seen the development of a research programme
where the complexity of modulators is measured in ways other than size. For
instance, for a graph class $\mathcal{H}$, the graph parameters elimination
distance to $\mathcal{H}$ (denoted by $\mathbf{ed}_{\mathcal{H}}$) [Bulian and
Dawar, Algorithmica, 2016], and $\mathcal{H}$-treewidth (denoted by
$\mathbf{tw}_{\mathcal{H}}$) [Eiben et al. JCSS, 2021] aim to minimize the
treedepth and treewidth, respectively, of the “torso” of the graph induced on
a modulator to the graph class $\mathcal{H}$. Here, the torso of a vertex set
$S$ in a graph $G$ is the graph with vertex set $S$ and an edge between two
vertices $u,v\in S$ if there is a path between $u$ and $v$ in $G$ whose
internal vertices all lie outside $S$.

In this paper, we show that from the perspective of (non-uniform) fixed-
parameter tractability (FPT), the three parameters described above give
equally powerful parameterizations for every hereditary graph class
$\mathcal{H}$ that satisfies mild additional conditions. In fact, we show that
for every hereditary graph class $\mathcal{H}$ satisfying mild additional
conditions, with the exception of $\mathbf{tw}_{\mathcal{H}}$ parameterized by
$\mathbf{ed}_{\mathcal{H}}$, for every pair of these parameters, computing one
parameterized by itself or any of the others is FPT-equivalent to the standard
vertex-deletion (to $\mathcal{H}$) problem. As an example, we prove that an
FPT algorithm for the vertex-deletion problem implies a non-uniform FPT
algorithm for computing $\mathbf{ed}_{\mathcal{H}}$ and
$\mathbf{tw}_{\mathcal{H}}$.

The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory,
we essentially prove that if $\mathcal{H}$ is hereditary, union-closed, CMSO-
definable, and (a) the canonical equivalence relation (or any refinement
thereof) for membership in the class can be efficiently computed, or (b) the
class admits a “strong irrelevant vertex rule”, then there exists a uniform
FPT algorithm for $\mathbf{ed}_{\mathcal{H}}$. Using these sufficient
conditions, we obtain uniform FPT algorithms for computing
$\mathbf{ed}_{\mathcal{H}}$, when $\mathcal{H}$ is defined by excluding a
finite number of connected (a) minors, or (b) topological minors, or (c)
induced subgraphs, or when $\mathcal{H}$ is any of bipartite, chordal or
interval graphs. For most of these problems, the existence of a uniform FPT
algorithm has remained open in the literature. In fact, for some of them, even
a non-uniform FPT algorithm was not known. For example, Jansen et al. [STOC
2021] ask for such an algorithm when $\mathcal{H}$ is defined by excluding a
finite number of connected topological minors. We resolve their question in
the affirmative.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Motivation
    2. 1.2 Answering Questions 3 and 4: FPT-equivalence of deletion, elimination and decomposition
      1. 1.2.1 Implications of Theorem 1.1
      2. 1.2.2 Modulators to Scattered Families
    3. 1.3 New Results on Cross Parameterizations
    4. 1.4 Answering Question 5: Towards Uniform FPT Algorithms
  2. 2 Preliminaries
    1. 2.1 Generic Notations
    2. 2.2 Graph Classes and Decompositions
    3. 2.3 Counting Monadic Second Order Logic
    4. 2.4 Parameterized graph problems
    5. 2.5 Boundaried Graphs
    6. 2.6 Finite Integer Index
    7. 2.7 Replacement lemma
  3. 3 Structural Results
    1. 3.1 Bounded Modulators on Unbreakable Graphs
    2. 3.2 Computing $\mathcal{H}$-Elimination Decomposition Using its Decision Oracle
    3. 3.3 Computing $\mathcal{H}$-Tree Decomposition Using its Decision Oracle
  4. 4 Equivalences Among Deletion, Decomposition and Elimination
    1. 4.1 Proof of Lemma 4.2
    2. 4.2 Prove of Lemma 4.3
    3. 4.3 Proof of Lemma 4.4
  5. 5 Applications of Theorem 1.1 – Beyond Graphs
  6. 6 Cross Parameterizations
  7. 7 Uniform FPT Algorithm
    1. 7.1 Proof of Lemma 7.19
    2. 7.2 Proof of Lemma 7.20
      1. 7.2.1 Proof of Lemma 7.25
  8. 8 Applications of the Uniform Algorithm
  9. 9 Conclusion
  10. A Problem Definitions

##  1 Introduction

Delineating borders of fixed-parameter tractability (FPT) is arguably the
biggest quest of parameterized complexity. Central to this goal is the class
of vertex-deletion problems (to a graph class $\mathcal{H}$). In the Vertex
Deletion to $\mathcal{H}$ problem, the goal is to compute a minimum set of
vertices to delete from the input graph, in order to obtain a graph contained
in $\mathcal{H}$. For a graph $G$, $\mathbf{mod}_{\mathcal{H}}(G)$ denotes the
size of a smallest vertex set $S$ such that $G-S\in{\cal H}$. If
$G-S\in\mathcal{H}$, then $S$ is called a modulator to $\cal H$. The
parameterized complexity of vertex-deletion problems has been extensively
studied for numerous choices of $\mathcal{H}$, e.g., when ${\cal H}$ is
planar, bipartite, chordal, interval, acyclic or edgeless, respectively, we
get the classical Planar Vertex Deletion, Odd Cycle Transversal, Chordal
Vertex Deletion, Interval Vertex Deletion, Feedback Vertex Set, and Vertex
Cover problems (see, for example, [23]).

In the study of the parameterized complexity of vertex-deletion problems,
solution size and various graph-width measures have been the most frequently
considered parameterizations, and over the past three decades their power has
been well understood. In particular, numerous vertex-deletion problems are
known to be fixed-parameter tractable (i.e., can be solved in time
$f(k)n^{\mathcal{O}(1)}$, where $k$ is the parameter and $n$ is the input
size) under these parameterizations. In light of this state of the art, recent
efforts have shifted to the goal of identifying and exploring “hybrid”
parameters such that:

  1. (a)

they are upper bounded by the solution size as well as certain graph-width
measures,

  2. (b)

they can be arbitrarily (and simultaneously) smaller than both the solution
size and graph-width measures, and

  3. (c)

a significant number of the problems that are in the class FPT when
parameterized by solution size or graph-width measures, can be shown to be in
the class FPT also when parameterized by these new parameters.

Two recently introduced parameters in this line of research are: (a)
$\mathcal{H}$-elimination distance and (b) $\mathcal{H}$-treewidth of $G$. The
$\mathcal{H}$-elimination distance of a graph $G$ to $\mathcal{H}$ (denoted
$\mathbf{ed}_{\mathcal{H}}(G)$) was introduced by Bulian and Dawar [11] and
roughly speaking, it expresses the number of rounds needed to obtain a graph
in $\mathcal{H}$ by removing one vertex from every connected component in each
round. We refer the reader to Section 2 for a more formal definition. The
reader familiar with the notion of treedepth [64] will be able to see that
this closely follows the recursive definition of treedepth. That is, if
$\mathcal{H}$ is the class of empty graphs, then the $\mathcal{H}$-elimination
distance of $G$ is nothing but the treedepth of $G$. In fact, if $\mathcal{H}$
is union-closed (as will be the case for all graph classes we consider in this
paper), then one gets the following equivalent perspective on this notion. The
$\mathcal{H}$-elimination distance of $G$ is defined as the minimum possible
treedepth of the torso of a modulator of $G$ to $\mathcal{H}$. Here, the torso
of a vertex set $S$ in a graph $G$ is the graph with vertex set $S$ and an
edge between two vertices $u,v\in S$ if there is a path between $u$ and $v$ in
$G$ whose internal vertices all lie outside $S$. Consequently, it is easy to
see that $\mathcal{H}$-elimination distance of $G$ is always upper bounded by
both the size of the smallest modulator of $G$ to $\mathcal{H}$ (i.e.,
$\mathbf{mod}_{\mathcal{H}}(G)$) as well as the treedepth of $G$111For this,
we always assume that $\mathcal{H}$ contains the empty graph and so $V(G)$ is
a trivial modulator to $\mathcal{H}$..

The second parameter of interest for us is $\mathcal{H}$-treewidth which,
roughly speaking, aims to “generalize” treewidth and solution size, the same
way that elimination distance aims to generalize treedepth and solution size.
This notion was recently introduced by Eiben et al. [27] and builds on a
similar hybrid parameterization which was first developed in the context of
solving CSPs [38] and found applications also in algorithms for SAT [37] and
Mixed ILPs [36]. Specifically, a tree $\mathcal{H}$-decomposition of a graph
$G$ of width $\ell$ is a tree decomposition of $G$ along with a set
$L\subseteq V(G)$ (called base vertices), such that (i) each base vertex
appears in exactly one bag, (ii) the base vertices in a bag induce a subgraph
belonging to $\mathcal{H}$, and (iii) the number of non-base vertices in any
bag is at most $\ell+1$. The value of $\mathcal{H}$-treewidth of $G$ (denoted
$\mathbf{tw}_{\mathcal{H}}(G)$) is the minimum width taken over all tree
$\mathcal{H}$-decompositions of $G$. The utility of this definition arises
from the fact that $\mathcal{H}$-treewidth of $G$ is always upper bounded by
the treewidth of $G$ (indeed, one could simply take a tree-decomposition of
$G$ attaining the treewidth of $G$ and set $L=\emptyset$) and moreover, one
can design fixed-parameter algorithms for several problems parameterized by
the $\mathbf{tw}_{\mathcal{H}}$ of the graph [27, 47]. On the other hand, for
union-closed graph classes $\mathcal{H}$, the $\mathcal{H}$-treewidth of $G$
is nothing but the minimum possible treewidth of the torso of a modulator of
$G$ to $\mathcal{H}$. This immediately implies that the
$\mathcal{H}$-treewidth of $G$ is always upper bounded by both the treewidth
of $G$ as well as the size of the smallest modulator of $G$ to $\mathcal{H}$
(i.e., $\mathbf{mod}_{\mathcal{H}}(G)$).

It is fairly easy to see that $\mathbf{ed}_{\mathcal{H}}(G)$ (respectively,
$\mathbf{tw}_{\mathcal{H}}(G)$) can be arbitrarily smaller than both
$\mathbf{mod}_{\mathcal{H}}(G)$ and the treedepth of $G$ (respectively, the
treewidth of $G$). Similarly, $\mathbf{tw}_{\mathcal{H}}(G)$ itself can be
arbitrarily smaller than $\mathbf{ed}_{\mathcal{H}}(G)$. We refer the reader
to [39, 48] for some illustrative examples of this fact. As both these
parameters satisfy Properties (a) and (b) listed above, there has been a
sustained effort in the last few years to investigate the extent to which
Property (c) is satisfied by these two parameters. In this effort, one
naturally encounters the following two fundamental algorithmic questions:

Question 1: For which families $\mathcal{H}$ of graphs is Elimination Distance
to $\mathcal{H}$ (Treewidth Decomposition to $\mathcal{H}$) FPT when
parameterized by $\mathbf{ed}_{\mathcal{H}}$ (respectively,
$\mathbf{tw}_{\mathcal{H}}$)? Question 2: For which families $\mathcal{H}$ of
graphs is Vertex Deletion to $\mathcal{H}$ parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$ ($\mathbf{tw}_{\mathcal{H}}(G)$) FPT?

In Elimination Distance to $\mathcal{H}$ (Treewidth Decomposition to
$\mathcal{H}$), the input is a graph $G$ and integer $k$ and the goal is to
decide whether $\mathbf{ed}_{\mathcal{H}}(G)$ (respectively,
$\mathbf{tw}_{\mathcal{H}}(G)$) is at most $k$. The parameter in both problems
is $k$. Both the questions listed above are extremely wide-ranging and
challenging. Indeed, for Question 1, notice that not even an XP algorithm
(running in time $n^{\mathcal{O}(g(k))}$, where $k$ is
$\mathbf{ed}_{\mathcal{H}}$ or $\mathbf{tw}_{\mathcal{H}}$) is obvious even
for well-understood graph classes $\mathcal{H}$, such as bipartite graphs. On
the other hand, Vertex Deletion to $\mathcal{H}$ in this case has a trivial
$n^{\mathcal{O}(k)}$-time algorithm where one simply guesses the minimum
modulator to $\mathcal{H}$ and checks whether the graph induced by the rest of
the vertices is bipartite, in linear time. In the absence of a resolution to
Question 1, Question 2 then brings with it the challenge of solving Vertex
Deletion to $\mathcal{H}$ (or indeed, any problem) without necessarily being
able to efficiently compute $\mathbf{ed}_{\mathcal{H}}$ or
$\mathbf{tw}_{\mathcal{H}}$.

##### State of the art for Question 1.

In their work, Bulian and Dawar [12] showed that the Elimination Distance to
$\mathcal{H}$ problem is FPT, when $\mathcal{H}$ is a minor-closed class of
graphs and asked whether it is FPT, when $\mathcal{H}$ is the family of graphs
of degree at most $d$. In a partial resolution to this question, Lindermayr et
al. [56] showed that Elimination Distance to $\mathcal{H}$ is FPT when we
restrict the input graph to be planar. Finally, Agrawal et al. [2], resolved
this question completely by showing that the problem is (non-uniformly) FPT
(we refer the reader to Section 1.4 for a definition of non-uniform FPT). In
fact, they obtained their result for all $\mathcal{H}$ that are characterized
by a finite family of induced subgraphs. Recently, Jansen and de Kroon [46]
extended the aforementioned result of Agrawal et al. [2] further, and showed
that Treewidth Decomposition to $\mathcal{H}$ is also (non-uniformly) FPT for
$\mathcal{H}$ that are characterized by a finite family of induced subgraphs.
In the same paper they also showed that Treewidth Decomposition to
$\mathcal{H}$ (Elimination Distance to $\mathcal{H}$) is non-uniformly FPT for
$\mathcal{H}$ being the family of bipartite graphs. Even more recently, Fomin
et al. [30] showed that for every graph family $\mathcal{H}$ expressible by a
first order-logic formula Elimination Distance to $\mathcal{H}$ is (non-
uniformly) FPT. Since a family of graphs characterized by a finite set of
forbidden induced subgraphs is expressible in this fragment of logic, this
result also generalizes the result of Agrawal et al. [2]. Until this result of
Fomin et al., the research on Question 1 has essentially proceeded on a case-
by-case basis, where each paper considers a specific choice of $\mathcal{H}$.

##### State of the art for Question 2.

In a recent paper, Jansen et al. [48] provide a general framework to design
FPT-approximation algorithms for $\mathbf{ed}_{\mathcal{H}}$ and
$\mathbf{tw}_{\mathcal{H}}$ for various choices of $\mathcal{H}$. For
instance, when $\mathcal{H}$ is bipartite or characterized by a finite set of
forbidden (topological) minors, they give FPT algorithms (parameterized by
$\mathbf{tw}_{\mathcal{H}}$) that compute a tree $\mathcal{H}$-decomposition
of $G$ whose width is not necessarily optimal, but polynomially bounded in the
$\mathcal{H}$-treewidth of the input, i.e., an approximation. These
approximation algorithms enable them to address Question 2 for various classes
$\mathcal{H}$ without having to exactly compute $\mathbf{ed}_{\mathcal{H}}(G)$
or $\mathbf{tw}_{\mathcal{H}}(G)$ (i.e., without resolving Question 1 for
these classes). Towards answering Question $2$, they give the following FPT
algorithms for Vertex Deletion to $\mathcal{H}$ parameterized by
$\mathbf{tw}_{\mathcal{H}}$. Let $\mathcal{H}$ be a hereditary class of graphs
that is defined by a finite number of forbidden connected (a) minors, or (b)
induced subgraphs, or (c)
$\mathcal{H}\in\\{\mathsf{bipartite~{}graphs},\mathsf{chordal~{}graphs}\\}$.
There is an algorithm that, given an $n$-vertex graph $G$, computes a minimum
vertex set $X$ such that $G-X\in\mathcal{H}$ in time
$f(\mathbf{tw}_{\mathcal{H}}(G))\cdot n^{\mathcal{O}(1)}$. Note that all of
these FPT algorithms are uniform.

###  1.1 Our Motivation

The starting point of our work lies in the aforementioned recent advances made
by Agrawal et al. [2], Fomin et al. [30] and Jansen et al. [48]. A closer look
at these algorithms shows an interesting property of these algorithms: known
algorithms for Elimination Distance to $\mathcal{H}$ and Treewidth
Decomposition to $\mathcal{H}$ utilize the corresponding (known) algorithms
for Vertex Deletion to $\mathcal{H}$ in a non-trivial manner. This fact, plus
the recent successes in designing (typically, non-uniform) FPT algorithms for
Elimination Distance to $\mathcal{H}$ and Treewidth Decomposition to
$\mathcal{H}$ naturally raises the following questions.

Question 3: When (if at all) is the parameterized complexity of Elimination
Distance to $\mathcal{H}$ or Treewidth Decomposition to $\mathcal{H}$
different from that of Vertex Deletion to $\mathcal{H}$? Question 4: When (if
at all) is the parameterized complexity of Vertex Deletion to $\mathcal{H}$ is
different from that of Vertex Deletion to $\mathcal{H}$ parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$, or that of Vertex Deletion to $\mathcal{H}$
parameterized by $\mathbf{tw}_{\mathcal{H}}(G)$? Question 5: Could one obtain
uniform FPT algorithms for Elimination Distance to $\mathcal{H}$ and Treewidth
Decomposition to $\mathcal{H}$ for natural families of graphs?

The main objective of the paper is to provide satisfactory answers to
Questions $3$, $4$ and $5$.

###  1.2 Answering Questions 3 and 4: FPT-equivalence of deletion, elimination
and decomposition

Roughly speaking, we show:

For Question 3: If $\mathcal{H}$ has certain properties which are also
possessed by numerous well-studied graph classes, then there is no difference
in the parameterized complexity of Elimination Distance to $\mathcal{H}$,
Treewidth Decomposition to $\mathcal{H}$, and Vertex Deletion to
$\mathcal{H}$. This explains, unifies and extends almost all known results
aimed at Question 1 in the literature. For Question 4: If $\mathcal{H}$ has
the properties referred to above, then there is no difference in the
parameterized complexity of Vertex Deletion to $\mathcal{H}$, Vertex Deletion
to $\mathcal{H}$ parameterized by $\mathbf{ed}_{\mathcal{H}}(G)$, and Vertex
Deletion to $\mathcal{H}$ parameterized by $\mathbf{tw}_{\mathcal{H}}(G)$.
This explains, unifies and extends almost all known results aimed at Question
2 in the literature. For Question 5: There are several fundamental graph
classes $\mathcal{H}$ for which we are able to give sufficiency conditions
that imply the first uniform FPT algorithms for Elimination Distance to
$\mathcal{H}$. In some of these cases, not even a non-uniform FPT algorithm
was previously known.

In what follows, we formally state our results and go into more detail about
their implications and significance. Towards that we first define a notion of
FPT-equivalence. We say that two parameterized problems are (non-uniformly)
FPT-equivalent if, given an FPT algorithm for any one of the two problems we
can obtain a (non-uniform) FPT algorithm for the other problem. Let
$\mathcal{H}$ be a family of graphs. Then, by parameterizing Vertex Deletion
to $\mathcal{H}$, Elimination Distance to $\mathcal{H}$, and Treewidth
Decomposition to $\mathcal{H}$, by any of $\mathbf{mod}_{\mathcal{H}}(G)$,
$\mathbf{ed}_{\mathcal{H}}(G)$, and $\mathbf{tw}_{\mathcal{H}}(G)$ we get nine
different problems. Our first result shows FPT-equivalences among eight of
these.

######  Theorem 1.1.

$\mathcal{H}$ be a hereditary family of graphs that is CMSO 222In this paper,
when we say CMSO, we refer to the fragment that is sometimes referred to as
${{\sf CMSO}}_{2}$ in the literature. We refer the reader to Section 2.3 for
the formal description of this fragment. definable and closed under disjoint
union. Then the following problems are (non-uniformly) FPT-equivalent.

  1. 1.

Vertex Deletion to $\mathcal{H}$ parameterized by
$\mathbf{mod}_{\mathcal{H}}(G)$

  2. 2.

Vertex Deletion to $\mathcal{H}$ parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$

  3. 3.

Vertex Deletion to $\mathcal{H}$ parameterized by
$\mathbf{tw}_{\mathcal{H}}(G)$

  4. 4.

Elimination Distance to $\mathcal{H}$ parameterized by
$\mathbf{mod}_{\mathcal{H}}(G)$

  5. 5.

Elimination Distance to $\mathcal{H}$ parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$

  6. 6.

Treewidth Decomposition to $\mathcal{H}$ parameterized by
$\mathbf{mod}_{\mathcal{H}}(G)$

  7. 7.

Treewidth Decomposition to $\mathcal{H}$ parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$

  8. 8.

Treewidth Decomposition to $\mathcal{H}$ parameterized by
$\mathbf{tw}_{\mathcal{H}}(G)$

Notice that because
$\mathbf{tw}_{\mathcal{H}}(G)\leq\mathbf{ed}_{\mathcal{H}}(G)\leq\mathbf{mod}_{\mathcal{H}}(G)$,
an FPT algorithm for one problem parameterized by a smaller parameter also
implies an FPT algorithm for the problem parameterized by the larger
parameter. However, the implications in the other direction are surprising and
insightful.

####  1.2.1 Implications of Theorem 1.1

We now describe the various applications and consequences of our first main
theorem (Theorem 1.1).

##### As a classification tool that unifies and extends many known results.

Theorem 1.1 is a powerful classification tool which states that as far as the
(non-uniform) fixed-parameter tractability of computing any of the parameters
$\mathbf{mod}_{\mathcal{H}}(G)$, $\mathbf{ed}_{\mathcal{H}}(G)$ and
$\mathbf{tw}_{\mathcal{H}}(G)$ is concerned, they are essentially the “same
parameter” for many frequently considered graph classes $\mathcal{H}$. In
other words, to obtain an FPT algorithm for any of the problems mentioned in
Theorem 1.1, it is sufficient to design an FPT algorithm for the standard
vertex-deletion problem, namely, Vertex Deletion to $\mathcal{H}$. This
implication unifies several known results in the literature.

For example, let $\mathcal{H}$ be the family of graphs of degree at most $d$
and recall that it was only recently that Agrawal et al. [5] and Jansen et al.
[46] showed that Elimination Distance to $\mathcal{H}$ and Treewidth
Decomposition to $\mathcal{H}$ are (non-uniformly) FPT, respectively. However,
using Theorom 1.1, the fixed-parameter tractability of these two problems and
in fact, even the fixed-parameter tractability of Vertex Deletion to
$\mathcal{H}$ parameterized by $\mathbf{ed}_{\mathcal{H}}(G)$ (or
$\mathbf{tw}_{\mathcal{H}}(G)$), is implied by the straightforward
$d^{k}n^{\mathcal{O}(1)}$-time branching algorithm for Vertex Deletion to
$\mathcal{H}$ (i.e., the problem of deleting at most $k$ vertices to get a
graph of degree at most $d$).

Moreover, for various well-studied families of $\mathcal{H}$, we immediately
derive FPT algorithms for all combinations of Vertex Deletion to
$\mathcal{H}$, Elimination Distance to $\mathcal{H}$, Treewidth Decomposition
to $\mathcal{H}$ parameterized by any of $\mathbf{mod}_{\mathcal{H}}(G)$
$\mathbf{ed}_{\mathcal{H}}(G)$ and $\mathbf{tw}_{\mathcal{H}}(G)$, which are
covered in Theorem 1.1. For instance, we can invoke this theorem using well-
known FPT algorithms for Vertex Deletion to $\mathcal{H}$ for several families
of graphs that are CMSO definable and closed under disjoint union, such as
families defined by a finite number of forbidden connected (a) minors, or (b)
topological minors, or (c) induced subgraphs, or (d) $\mathcal{H}$ being
bipartite, chordal, proper-interval, interval, and distance-hereditary; to
name a few [73, 14, 15, 13, 28, 33, 31, 49, 58, 63, 70, 71, 72, 54]. Thus,
Theorem 1.1 provides a unified understanding of many recent results and
resolves the parameterized complexity of several questions left open in the
literature.

Of particular significance among the new results is the case where, invoking
Theorem 1.1 and taking $\mathcal{H}$ to be a class defined by a finite number
of forbidden connected topological minors gives the first FPT algorithms for
computing $\mathbf{ed}_{\mathcal{H}}$ and $\mathbf{tw}_{\mathcal{H}}$,
resolving an open problem posed by Jansen et al. [48].

##### Deletion to Families of Bounded Rankwidth.

We observe that Theorem 1.1 can be invoked by taking $\mathcal{H}$ to be the
class of graphs of bounded rankwidth, extending a result of Eiben et al. [27].

Rankwidth is a graph parameter introduced by Oum and Seymour [69] to
approximate yet another graph parameter called Cliquewidth. The notion of
cliquewidth was defined by Courcelle and Olariu [21] as a measure of how
“clique-like” the input graph is. One of the main motivations was that several
NP-complete problems become tractable on the family of cliques (complete
graphs), the assumption was that these algorithmic properties extend to
“clique-like” graphs [20]. However, computing cliquewidth and the
corresponding cliquewidth decomposition seems to be computationally
intractable. This then motivated the notion of rankwidth, which is a graph
parameter that approximates cliquewidth well while also being algorithmically
tractable [69, 66]. For more information on cliquewidth and rankwidth, we
refer to the surveys by Hlinený et al. [43] and Oum [68].

For a graph $G$, we will use $\mathbf{rwd}(G)$ to denote the rankwidth of $G$.
Let $\eta\geq 1$ be a fixed integer and let $\mathcal{H}_{\eta}$ denote the
class of graphs of rankwidth at most $\eta$. It is known that Vertex Deletion
to $\mathcal{H}_{\eta}$ is FPT [22]. The algorithm is based on the fact that
for every integer $\eta$, there is a finite set ${\cal C}_{\eta}$ of graphs
such that for every graph $G$, $\mathbf{rwd}(G)\leq\eta$ if and only if no
vertex-minors of $G$ are isomorphic to a graph in ${\cal C}_{\eta}$ [65, 67].
Further, it is known that vertex-minors can be expressed in CMSO, this
together with the fact that we can test whether a graph $H$ is a vertex-minor
of $G$ or not in $f(|H|)n^{\mathcal{O}(1)}$ time on graphs of bounded
rankwidth leads to the desired algorithm [22, Theorem 6.11]. It is also
important to mention that for Vertex Deletion to $\mathcal{H}_{1}$, also known
as the Distance-Hereditary Vertex-Deletion problem, there is a dedicated
algorithm running in time $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ [28]. For us,
two properties of $\mathcal{H}_{\eta}$ are important: (a) expressibility in
CMSO and (b) being closed under disjoint union. These two properties, together
with the result in [22] imply that Theorem 1.1 is also applicable to
$\mathcal{H}_{\eta}$. Thus, we are able to generalize and extend the result of
Eiben et al. [27], who showed that for every $\eta$, computing
$\mathbf{tw}_{\mathcal{H}_{\eta}}$ is FPT. Since we do not need the notion of
rankwidth and vertex-minors in this paper beyond this application, we refer
the reader for further details to [43, 68].

##### Beyond graphs: Cut problems.

Notice that in the same spirit as we have seen so far, one could also consider
the parameterized complexity of other classical problems such as cut problems
(e.g., Multiway Cut) as long as the parameter is smaller than the standard
parameter studied so far. With this view, we obtain the first such results for
several cut problems such as Multiway Cut, Subset FVS and Subset OCT. That is,
we obtain FPT algorithms for these problems that is parameterized by a
parameter whose value is upper bounded by the standard parameter (i.e.,
solution size) and which can be arbitrarily smaller. For instance, consider
the Multiway Cut problem, where one is given a graph $G$ and a set of vertices
$S$ (called terminals) and an integer $\ell$ and the goal is to decide whether
there is a set of at most $\ell$ vertices whose deletion separates every pair
of these terminals. The standard parameterization for this problem is the
solution size $\ell$. Jansen et al. [48] propose to consider annotated graphs
(i.e., undirected graphs with a distinguished set of terminal vertices) and
study the parameterized complexity of Multiway Cut parameterized by the
elimination distance to a graph where each component has at most one terminal.
Notice that this new parameter is always upper bounded by the size of a
minimum solution.

Thus, an FPT algorithm for Multiway Cut with such a new parameter would
naturally extend the boundaries of tractability for the problem. We are able
to obtain such an algorithm by using Theorem 1.1. We then proceed to obtain
similar FPT algorithms for the other cut problems mentioned in this paragraph.
Recall that in the Subset FVS problem, one is given a graph $G$, a set $S$ of
terminals and an integer $\ell$ and the goal is to decide whether there is a
set of at most $\ell$ vertices that hits every cycle in $G$ that contains a
terminal. Similarly, in the Subset OÇT problem, one is given a graph $G$, a
set $S$ of terminals and an integer $\ell$ and the goal is to decide whether
there is a set of at most $\ell$ vertices that hits every odd cycle in $G$
that contains a terminal.

Building on our new result for Multiway Cut, we obtain an FPT algorithm for
Subset FVS parameterized by the elimination distance to a graph where no
terminal is part of a cycle, and an FPT algorithm for Subset OCT parameterized
by the elimination distance to a graph where no terminal is part of an odd
cycle. We summarize all three results as follows:

######  Theorem 1.2 (Informal version of Theorem 5.1).

The following problems are FPT:

  1. 1.

Multiway Cut parameterized by elimination distance to an annotated graph where
each component has at most one terminal.

  2. 2.

Subset Feedback Vertex Set parameterized by elimination distance to an
annotated graph where no terminal occurs in a cycle.

  3. 3.

Subset Odd Cycle Transversal parameterized by elimination distance to an
annotated graph where no terminal occurs in an odd cycle.

In fact, we also strengthen the parameterization to an analogue of
$\mathcal{H}$-treewidth in the natural way and obtain corresponding results.
The details can be found in Section 5. To achieve these results, we use
Theorem 1.1. However, note that that Theorem 1.1 is defined only when
$\mathcal{H}$ is a family of graphs. In order to capture problems such as
Multiway Cut, Subset FVS and Subset OCT, we express our problems in terms of
appropriate notions of structures and then give a reduction to a pure graph
problem on which Theorem 1.1 can be invoked.

These results make concrete advances in the direction proposed by Jansen et
al. [48] to develop FPT algorithms for Multiway cut parameterized by the
elimination distance to a graph where each component has at most one terminal.

####  1.2.2 Modulators to Scattered Families

Recent years have seen another new direction of research on Vertex Deletion to
$\mathcal{H}$ – instead of studying the computation of a modulator to a single
family of graphs $\mathcal{H}$, one can aim to compute small vertex sets whose
deletion leaves a graph where each connected component comes from a particular
pre-specified graph class [40, 45, 44]. As an example of problems in this line
of research, consider the following. Given a graph $G$, and a number $k$, find
a modulator $S$ of size at most $k$ (or decide whether one exists) such that
in $G-S$, each connected component is either chordal, or bipartite or planar.
Let us call such an $S$, a scattered modulator. Such scattered modulators (if
small) can be used to design new FPT algorithms for certain problems by taking
separate FPT algorithms for the problems on each of the pre-specified graph
classes and then combining them in a non-trivial way “through” the scattered
modulator. However, the quality of the modulators considered in this line of
research so far has been measured in the traditional way, i.e., in terms of
the size. In this paper, by using Theorem 1.1, we initiate a new line of
research where, again, it is not the modulator size that is the measure of
structure, but in some sense, the treedepth or treewidth of the torso of the
graph induced by the modulator. That is, we introduce the first extensions of
“scattered modulators” to “scattered elimination distance” and “scattered
$\mathcal{H}$-tree decompositions” and obtain results regarding the
computation of the corresponding modulators as well as their role in the
design of FPT algorithms for other problems (i.e., cross parameterization).

The first study of scattered modulators was undertaken by Ganian et al. [40],
who introduced this notion in their work on constraint satisfaction problems.
Recently, Jacob et al. [44, 45] initiated the study of scattered modulators
explicitly for “scattered” families of graphs. In particular, let
$\mathcal{H}_{1},\ldots,\mathcal{H}_{d}$ be families of graphs. Then, the
scattered family of graphs $\otimes(\mathcal{H}_{1},\ldots,\mathcal{H}_{d})$
is defined as the set of all graphs $G$ such that every connected component of
$G$ belongs to $\bigcup_{i=1}^{d}\mathcal{H}_{i}$. That is, each connected
component of $G$ belongs to some $\mathcal{H}_{i}$. As their main result,
Jacob et al. [44] showed that Vertex Deletion to $\mathcal{H}$ is FPT whenever
Vertex Deletion to $\mathcal{H}_{i}$, $i\in\\{1,\ldots,d\\}$, is FPT, and each
of $\mathcal{H}_{i}$ is CMSO expressible. Here, $\mathcal{H}$ is the scattered
family $\otimes(\mathcal{H}_{1},\ldots,\mathcal{H}_{d})$. Notice that if each
of $\mathcal{H}_{i}$ is CMSO expressible then so is $\mathcal{H}$. Further, it
is easy to observe that if each of $\mathcal{H}_{i}$ is closed under disjoint
union then so is $\mathcal{H}$. The last two properties together with the
result of Jacob et al. [44] enable us to invoke Theorem 1.1 even when
$\mathcal{H}$ is a scattered graph family. The effect can be formalized as
follows.

######  Theorem 1.3.

Let $\mathcal{H}_{1},\ldots,\mathcal{H}_{d}$ be hereditary, union-closed, CMSO
expressible families of graphs such that Vertex Deletion to $\mathcal{H}_{i}$
is FPT for every $i\in[d]$. Let
$\mathcal{H}=\otimes(\mathcal{H}_{1},\dots,\mathcal{H}_{d})$ and
$\mathcal{H}^{\prime}=\bigcup_{i=1}^{d}\mathcal{H}_{i}$. Then, Elimination
Distance to $\mathcal{H}$ and Treewidth Decomposition to $\mathcal{H}$ are
also FPT.

Notice in the above statement that if we take
$\mathcal{H}^{\prime}=\bigcup_{i=1}^{d}\mathcal{H}_{i}$, then the size of a
modulator to $\mathcal{H}$ is different from that of a smallest modulator to
$\mathcal{H}^{\prime}$, whereas the elimination distance to $\mathcal{H}$ and
$\mathcal{H}^{\prime}$ are the same.

###  1.3 New Results on Cross Parameterizations

Another popular direction of research in Parameterized Complexity is cross
parameterizations: that is parameterization of one problem with respect to
alternate parameters. For an illustration, consider Odd Cycle Transversal
(OCT) on chordal graphs. Let $\mathcal{H}$ denote the family of chordal
graphs. It is well known that OCT is polynomial-time solvable on chordal
graphs. Further, given a graph $G$ and a modulator to chordal graphs of size
$\mathbf{mod}_{\mathcal{H}}(G)$, OCT admits an algorithm with running time
$2^{\mathcal{O}(\mathbf{mod}_{\mathcal{H}}(G)))}n^{\mathcal{O}(1)}$. It is
therefore natural to ask whether OCT admits an algorithm with running time
$f(\mathbf{ed}_{\mathcal{H}}(G))n^{\mathcal{O}(1)}$ or
$f(\mathbf{tw}_{\mathcal{H}}(G))n^{\mathcal{O}(1)}$, given an
$\mathcal{H}$-elimination forest of $G$ of depth
$\mathbf{ed}_{\mathcal{H}}(G)$ and an $\mathcal{H}$-decomposition of $G$ of
width $\mathbf{tw}_{\mathcal{H}}(G)$, respectively. The question is also
relevant, in fact more challenging, when an $\mathcal{H}$-elimination forest
of $G$ of depth $\mathbf{ed}_{\mathcal{H}}(G)$ or an
$\mathcal{H}$-decomposition of $G$ of width $\mathbf{tw}_{\mathcal{H}}(G)$ is
not given. Jansen et al. [48] specifically asked to consider this research
direction in their paper. Quoting them:

“…the elimination distance can also be used as a parameterization away from
triviality for solving other parameterized problems $\Pi$, when using classes
$\mathcal{H}$ in which $\Pi$ is polynomial-time solvable. This can lead to
interesting challenges of exploiting graph structure. For problems which are
FPT parameterized by deletion distance to $\mathcal{H}$, does the tractability
extend to elimination distance to $\mathcal{H}$? For example, is Undirected
Feedback Vertex Set FPT when parameterized by the elimination distance to a
subcubic graph or to a chordal graph? The problem is known to be FPT
parameterized by the deletion distance to a chordal graph [51] or the edge-
deletion distance to a subcubic graph [61].”

A step in this direction can be seen in the work of Eiben et al. [27, Thm. 4].
They present a meta-theorem that yields non-uniform FPT algorithms when $\Pi$
satisfies several conditions, which require a technical generalization of an
FPT algorithm for $\Pi$ parameterized by deletion distance to $\mathcal{H}$.
Here, we avoid resorting to such requirements and instead, provide sufficient
conditions on the problem itself, which are usually very easily checked and
which enables us to obtain fixed-parameter algorithms for vertex-deletion
problems (or edge-deletion problems) parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$ ($\mathbf{tw}_{\mathcal{H}}(G)$) when given an
$\mathcal{H}$-elimination forest of $G$ of depth
$\mathbf{ed}_{\mathcal{H}}(G)$ (respectively, an $\mathcal{H}$-decomposition
of $G$ of width $\mathbf{tw}_{\mathcal{H}}(G)$). As a consequence, we resolve
the aforementioned open problem of Jansen et al. [48] on the parameterized
complexity of Undirected Feedback Vertex Set parameterized by the elimination
distance to a chordal graph.

Let us now state an informal version of our result so that we can convey the
main message and highlight some consequences without delving into excessive
detail at this point. We refer the reader to Section 6 for the formal
statement and full proof.

######  Theorem 1.4 (Informal version of Theorem 6.1).

Let $\cal H$ be a hereditary family of graphs and $\Pi$ be a parameterized
graph problem satisfying the following properties.

  1. 1.

$\Pi$ has the property of finite integer index (FII).

  2. 2.

$\Pi$ is FPT parameterized by $\mathbf{mod}_{\mathcal{H}}(G)$.

  3. 3.

Either, a $\mathcal{H}$-decomposition of $G$ of width
$\mathbf{tw}_{\mathcal{H}}(G)$ (or a $\mathcal{H}$-elimination forest of $G$
of depth $\mathbf{ed}_{\mathcal{H}}(G)$) is given; or $\mathcal{H}$ is CMSO
definable, closed under disjoint union and Vertex Deletion to $\mathcal{H}$ is
FPT.

Then, $\Pi$ is FPT parameterized by $\mathbf{ed}_{\mathcal{H}}(G)$ or
$\mathbf{tw}_{\mathcal{H}}(G)$.

FII is a technical property satisfied by numerous graph problems and often
easily verified. The term FII first appeared in the works of [9, 25] and is
similar to the notion of finite state [1, 10, 18]. An intuitive way (though,
formally, not correct) to understand FII is as follows. Let $\Pi$ be a graph
problem. Further, for a graph $G$, let ${\sf opt}_{\Pi}(G)$ denote the optimum
(minimum or maximum) value of solution to $\Pi$. For example, if $\Pi$ is
Dominating Set then ${\sf opt}_{\Pi}(G)$ denotes the size of a minimum
dominating set; and if $\Pi$ is Cycle Packing then ${\sf opt}_{\Pi}(G)$
denotes the cardinality of a set containing maximum number of pairwise vertex
disjoint cycles. In a simplistic way we can say that a graph problem has FII,
if for every graph $G$, and a separation $(L,R)$ ($L\cup R=V(G)$) we have
that:

${\sf opt}_{\Pi}(G)={\sf opt}_{\Pi}(G[L\setminus R])+{\sf
opt}_{\Pi}(G[R\setminus L])\pm h(|L\cap R|).$

Here, $h$ is a function of the order of separation ($|L\cap R|$) only. This
immediately implies that problems such as Dominating Set and Cycle Packing
have FII. In the context of this work, it is sufficient for the reader to know
that Vertex Deletion to $\mathcal{H}$ has FII, whenever $\mathcal{H}$ is
hereditary, CMSO definable, and closed under disjoint union. We refer the
reader to [9, 25, 8] for more details on FII.

Now as a corollary to Theorem 1.4 we get that Undirected Feedback Vertex Set
is FPT parameterized by $\mathbf{ed}_{\mathcal{H}}(G)$ or
$\mathbf{tw}_{\mathcal{H}}(G)$, where $\mathcal{H}$ is a family of chordal
graphs, answering the problem posed by Jansen et al. [48]. Similarly, we can
show that Dominating Set is FPT parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$ or $\mathbf{tw}_{\mathcal{H}}(G)$, where
$\mathcal{H}$ is a family of interval graphs.

###  1.4 Answering Question 5: Towards Uniform FPT Algorithms

The FPT algorithms obtained via Theorems 1.1 and 1.4 and the extension to
families of structures are non-uniform. In fact, to the best of our knowledge,
all of the current known FPT algorithms for Elimination Distance to
$\mathcal{H}$ or Treewidth Decomposition to $\mathcal{H}$, are non-uniform;
except for Elimination Distance to $\mathcal{H}$, when $\mathcal{H}$ is the
family of empty graphs (which, as discussed earlier, is simply the problem of
computing treedepth). However, we note that the FPT-approximation algorithms
in Jansen et al. [48] (in fact, all the algorithms obtained in [48]) are
uniform.

For the sake of clarity, we formally define the notion of uniform and non-
uniform FPT algorithms [26, Definition $2.2.1$].

######  Definition 1.1 (Uniform and non-uniform FPT).

Let $\Pi$ be a parameterized problem.

  1. (i)

We say that $\Pi$ is uniformly FPT if there is an algorithm ${\cal A}$, a
constant $c$, and an arbitrary function $f:\mathbb{N}\to\mathbb{N}$ such that:
the running time of ${\cal A}(\langle x,k\rangle)$ is at most $f(k)|x|^{c}$
and $\langle x,k\rangle\in\Pi$ if and only if ${\cal A}(\langle
x,k\rangle)=1$.

  2. (ii)

We say that $\Pi$ is non-uniformly FPT if there is collection of algorithms
$\\{{\cal A}_{k}:k\in\mathbb{N}\\}$, a constant $c$, and an arbitrary function
$f:\mathbb{N}\to\mathbb{N}$, such that : for each $k\in\mathbb{N}$, the
running time of ${\cal A}_{k}(\langle x,k\rangle)$ is $f(k)|x|^{c}$ and
$\langle x,k\rangle\in\Pi$ if and only if ${\cal A}_{k}(\langle
x,k\rangle)=1$.

Towards unification, we first present a general set of demands that, if
satisfied, shows that Elimination Distance to $\mathcal{H}$ parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$ is uniformly FPT. Like before, we consider a
hereditary family $\cal H$ of graphs such that $\mathcal{H}$ is CMSO
definable, closed under disjoint union and Vertex Deletion to $\mathcal{H}$ is
FPT. However, we strengthen the last two demands. To explain the new
requirements, we briefly (and informally) discuss a few notions concerning
boundaried graphs and equivalence classes. Essentially, a boundaried graph (a
$t$-boundaried graph) is a graph with an injective labelling of some of its
vertices by positive integers (upper bounded by $t$). When gluing two
boundaried graphs $G$ and $H$, denoted by $G\oplus H$, we just take their
disjoint union, and unify vertices having the same label. Concerning some
$\cal H$, two boundaried graphs $G_{1}$ and $G_{2}$ are equivalent (under the
canonical equivalence relation) if, for any boundaried graph $H$, $G_{1}\oplus
H\in{\cal H}$ if and only if $G_{2}\oplus H\in{\cal H}$. A refinement of the
canonical equivalence relation (or just a refinement, for short) is an
equivalence relation where any two boundaried graphs considered equivalent,
are equivalent according to the canonical equivalence relation (but not vice
versa).

Now, the new requirements are to define a refinement $\mathsf{R}$ whose number
of equivalence classes for $t$-boundaried graphs is a function of $t$ only,
here called a finite (per $t$) refinement, such that:

  * •

$\mathsf{R}$ is closed under disjoint union: That is, if we have a boundaried
graph that belongs to some equivalence class $R\in\mathsf{R}$, then the
disjoint union of that boundaried graph and a non-boundaried graph from ${\cal
H}$ also belongs to $R$. [Strengthens the closeness under disjoint union
property of $\cal H$.]

  * •

Vertex Deletion to $\mathsf{R}$ is FPT: We have a uniform FPT-algorithm (with
parameters $t$ and $k$) that, given a $t$-boundaried graph $G$, an equivalence
class $R\in\mathsf{R}$, and $k\in\mathbb{N}$, decides whether there exists
$S\subseteq V(G)$ of size at most $k$ such that $G-S$ belongs to an
equivalence class “at least as good as” $R$. [Strengthens that Vertex Deletion
to $\mathcal{H}$ is FPT.]

We prove the following.

######  Theorem 1.5 (Informal).

Let $\cal H$ be a hereditary family of graphs and a finite (per $t$)
refinement $\mathsf{R}$ satisfying the following properties.

  1. 1.

$\mathcal{H}$ is CMSO definable.

  2. 2.

$\mathsf{R}$ is closed under disjoint union.

  3. 3.

Vertex Deletion to $\mathsf{R}$ is FPT (parameterized by boundary and solution
sizes).

Then, Elimination Distance to $\mathcal{H}$ is uniformly FPT parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$.

We also give two conditions that seem easier to implement. Together with
$\mathcal{H}$ being CMSO definable and closed under disjoint union, the
satisfaction of the two new condition yields the conditions of Theorem 1.5. In
particular, they allow the user to not deal with equivalence classes at all,
and to deal with boundaried graphs only with respect to a condition posed on
obstructions. Roughly speaking, the simpler conditions are as follows.

  * •

Finite Boundaried Partial-Obstruction Witness Set: $\mathcal{H}$ admits a
characterization by a (possibly infinite) set $\mathbb{O}$ of obstructions as
induced subgraphs.333Even if the more natural characterization is by forbidden
minors/topological minors/subgraphs, we can translate this characterization to
one by induced subgraphs (which can make a finite obstruction set become
infinite). Let ${\cal O}_{t}$ be the set of $t$-boundaried graphs that are
subgraphs of obstructions from $\mathbb{O}$. Then, there exists ${\cal
O}^{\prime}_{t}\subseteq{\cal O}_{t}$ of finite size (depending only on $t$)
such that: for any boundaried graph $G$, if there exists $O\in{\cal O}_{t}$
such that $G\oplus O\notin{\cal H}$, then there exists $O^{\prime}\in{\cal
O}^{\prime}_{t}$ such that $G\oplus O^{\prime}\notin{\cal H}$.

  * •

A “Strong” Irrelevant Vertex Rule: There exist families of graphs $\cal X$ and
$\cal Y$ (possibly ${\cal X}={\cal Y}$), such that: (i) Each “large” graph in
$\cal X$ contains a “large” graph from $\cal Y$ as an induced (or not)
subgraph. (ii) Given a (not boundaried) graph of “large” treewidth, it
contains a “large” graph in $\cal X$ as an induced subgraph. (iii) Given
$k\in\mathbb{N}$ and a (not boundaried) graph that contains a “large” graph in
$\cal X$ as an induced subgraph, which, in turn, (by condition (i)), contains
a “large” graph $Y$ in $\cal Y$ as an induced subgraph, “almost all”
(depending on $k$) of the vertices in $Y$ are $k$-irrelevant.444A vertex $v$
in $G$ is $k$-irrelevant if the answers to $(G,k)$ and $(G-v,k)$ are the same
(as instances of Vertex Deletion to $\mathcal{H}$).

The reason why we claim that these conditions are “simple” is that known
algorithms (for the problems considered here) already implicitly yield them as
part of their analysis. So, the satisfaction of these conditions do not seem
(in various cases) to require much “extra” work compared to the design of an
FPT algorithm (or a kernel) to the problem at hand. Using these sufficient
conditions, we obtain uniform FPT algorithms for computing
$\mathbf{ed}_{\mathcal{H}}$, when $\mathcal{H}$ is defined by excluding a
finite number of connected (a) minors, or (b) topological minors, or (c)
induced subgraphs, or when $\mathcal{H}$ is any of bipartite, chordal or
interval graphs. For most of these problems, the existence of a uniform FPT
algorithm has remained open in the literature. In fact, for some of them, even
a non-uniform FPT algorithm was not known.

##  2 Preliminaries

###  2.1 Generic Notations

We begin by giving all the basic notations we use in this paper. For a graph
$G$, we use $V(G)$ and $E(G)$ to denote its vertex set and edge set,
respectively. For a graph $G$, whenever the context is clear, we use $n$ and
$m$ to denote $|V(G)|$ and $|E(G)|$, respectively. Consider a graph $G$. For
$X\subseteq V(G)$, $G[X]$ denotes the graph with vertex set $X$ and the edge
set $\\{\\{x,y\\}\in E(G)\mid x,y\in X\\}$. By $G-X$, we denote the graph
$G[V(G)\setminus X]$. For a vertex $v\in V(G)$, $N_{G}(v)$ and $N_{G}[v]$
denote the set of open neighbors and closed neighbors of $v$ in $G$. That is,
$N_{G}(v)=\\{u\in V(G)\mid\\{u,v\\}\in E(G)\\}$ and
$N_{G}[v]=N_{G}(v)\cup\\{v\\}$. For a set $U\subseteq V(G)$,
$N_{G}(U)=\bigcup_{u\in U}N_{G}(u)\setminus U$ and $N_{G}[U]=N_{G}(U)\cup U$.
For a vertex set $C\subseteq V(G)$, by slightly abusing the notation, we use
$N_{G}(C)$, and $N_{G}[C]$ to denote $N(V(C))$, and $N[V(C)]$, respectively.
In all the notations above, we drop the subscript $G$ whenever the context is
clear.

A _path_ $P=(v_{1},v_{2},\cdots,v_{\ell})$ in $G$ is a subgraph of $G$ where
$V(P)=\\{v_{1},v_{2},\cdots,v_{\ell}\\}\subseteq V(G)$ is a set of distinct
vertices and $E(P)=\\{\\{v_{i},v_{i+1}\\}\mid i\in[\ell-1]\\}\subseteq E(G)$,
where $|V(P)|=\ell$ for some $\ell\in[|V(G)|]$. The above defined path $P$ is
called as $v_{1}-v_{\ell}$ path. We say that the graph $G$ is _connected_ if
for every $u,v\in V(G)$, there exists a $u-v$ path in $G$. A _connected
component_ of $G$ is an inclusion-wise maximal connected induced subgraph of
$G$.

A _rooted tree_ is a tree with a special vertex designated to be the _root_.
Let $T$ be a rooted tree with root $r\in V(T)$. We say that a vertex $v\in
V(T)\setminus\\{r\\}$ is a _leaf_ of $T$ if $v$ has exactly one neighbor in
$T$. Moreover, if $V(T)=\\{r\\}$, then $r$ is the leaf (as well as the root)
of $T$.555A root is not a leaf in a tree, if the tree has at least two
vertices. A vertex which is not a leaf, is called a _non-leaf_ vertex. Let
$t,t^{\prime}\in V(T)$ such that $\\{t,t^{\prime}\\}\in E(T)$ and $t^{\prime}$
is not contained in the $t-r$ path in $T$, then we say that $t$ is the
_parent_ of $t^{\prime}$ and $t^{\prime}$ is a _child_ of $t$. A vertex
$t^{\prime}\in V(T)$ is a _descendant_ of $t$ ($t^{\prime}$ can possibly be
the same as $t$), if there is a $t-t^{\prime}$ path in $T-\\{{\sf
par}_{T}(t)\\}$, where ${\sf par}_{T}(t)$ is the parent of $t$ in $T$. Note
that when $t=r$, then $T-\\{{\sf par}_{T}(t)\\}=T$, as the parent of $r$ does
not exist. That is, every vertex in $T$ is a descendant of $r$.

A rooted forest is a forest where each of its connected component is a rooted
tree. For a rooted forest $F$, a vertex $v\in V(F)$ that is not a root of any
of its rooted trees is a _leaf_ if it is of degree exactly one in $F$. The
_depth_ of a rooted tree $T$ is the maximum number of edges in a root to leaf
path in $T$. The _depth_ of a rooted forest is the maximum depth among its
rooted trees.

###  2.2 Graph Classes and Decompositions

We always assume that $\mathcal{H}$ is a hereditary class of graphs, that is,
closed under taking induced subgraphs. A set $X\subseteq V(G)$ is called an
$\mathcal{H}$-deletion set if $G-X\in\mathcal{H}$. The task of finding a
smallest $\mathcal{H}$-deletion set is called the $\mathcal{H}$-deletion
problem (also referred to as $\mathcal{H}$-vertex deletion but we abbreviate
it since we do not consider edge deletion problems). Next, we give the notion
of _elimination-distance_ introduced by Bulian and Dawar [11]. We rephrase
their definition, and our definition is (almost) in-line with the equivalent
definition given by Jansen et al. [48].

Figure 1: Let $\cal H$ be the family of triangle-free graphs. The figure shows
a graph $G$ with a modulator to $\cal H$ of size $12$ (in red), an $\cal
H$-elimination decomposition of depth $6$, an $\cal H$-tree decomposition of
width $2$.

######  Definition 2.1.

For a graph class $\mathcal{H}$, an $\mathcal{H}$-elimination decomposition of
graph $G$ is pair $(T,\chi,L)$ where $T$ is a rooted forest and $\chi\colon
V(T)\to 2^{V(G)}$ and $L\subseteq V(G)$, such that:

  1. 1.

For each internal node $t$ of $T$ we have $|\chi(t)|\leq 1$ and
$\chi(t)\subseteq V(G)\setminus L$.

  2. 2.

The sets $(\chi(t))_{t\in V(T)}$ form a partition of $V(G)$.

  3. 3.

For each edge $uv\in E(G)$, if $u\in\chi(t_{1})$ and $v\in\chi(t_{2})$ then
$t_{1},t_{2}$ are in ancestor-descendant relation in $T$.

  4. 4.

For each leaf $t$ of $T$, we have $\chi(t)\subseteq L$ and the graph
$G[\chi(t)]$, called a base component, belongs to $\mathcal{H}$.

The _depth_ of $T$ is the maximum number of edges on a root-to-leaf path (see
Figure 1). We refer to the union of base components as the set of base
vertices. The $\mathcal{H}$-elimination distance of $G$, denoted
$\mathbf{ed}_{\mathcal{H}}(G)$, is the minimum depth of an
$\mathcal{H}$-elimination forest for $G$. A pair $(T,\chi)$ is a (standard)
elimination forest if $\mathcal{H}$ is the class of empty graphs, i.e., the
base components are empty. The treedepth of $G$, denoted $\mathbf{td}(G)$, is
the minimum depth of a standard elimination forest.

It is straight-forward to verify that for any $G$ and $\mathcal{H}$, the
minimum depth of an $\mathcal{H}$-elimination forest of $G$ is equal to the
$\mathcal{H}$-elimination distance as defined recursively in the introduction.
(This is the reason we have defined the depth of an $\mathcal{H}$-elimination
forest in terms of the number of edges, while the traditional definition of
treedepth counts vertices on root-to-leaf paths.) The following definition
captures the relaxed notion of tree decomposition.

######  Definition 2.2 ([48]).

For a graph class $\mathcal{H}$, an $\mathcal{H}$-tree decomposition of graph
$G$ is a triple $(T,\chi,L)$ where $L\subseteq V(G)$, $T$ is a rooted tree,
and $\chi\colon V(T)\to 2^{V(G)}$, such that:

  1. 1.

For each $v\in V(G)$ the nodes $\\{t\mid v\in\chi(t)\\}$ form a non-empty
connected subtree of $T$.

  2. 2.

For each edge $\\{u,v\\}\in E(G)$ there is a node $t\in V(G)$ with
$\\{u,v\\}\subseteq\chi(t)$.

  3. 3.

For each vertex $v\in L$, there is a unique $t\in V(T)$ for which
$v\in\chi(t)$, with $t$ being a leaf of $T$.

  4. 4.

For each node $t\in V(T)$, the graph $G[\chi(t)\cap L]$ belongs to
$\mathcal{H}$.

The _width_ of a tree $\mathcal{H}$-decomposition is defined as
$\max(0,\max_{t\in V(T)}|\chi(t)\setminus L|-1)$. The $\mathcal{H}$-treewidth
of a graph $G$, denoted $\mathbf{tw}_{\mathcal{H}}(G)$, is the minimum width
of a tree $\mathcal{H}$-decomposition of $G$. The connected components of
$G[L]$ are called base components and the vertices in $L$ are called base
vertices.

A pair $(T,\chi)$ is a (standard) _tree decomposition_ if $(T,\chi,\emptyset)$
satisfies all conditions of an $\mathcal{H}$-decomposition; the choice of
$\mathcal{H}$ is irrelevant.

In the definition of width, we subtract one from the size of a largest bag to
mimic treewidth. The maximum with zero is taken to prevent graphs
$G\in\mathcal{H}$ from having $\mathbf{tw}_{\mathcal{H}}(G)=-1$.

Topological minors: Roughly speaking, a graph $H$ is a _topological minor_ of
$G$ if $G$ contains a subgraph $G^{\prime}$ on $|V(H)|$ vertices, where the
edges in $H$ correspond to (vertex disjoint) paths in $G^{\prime}$. We now
formally define the above. Let ${\sf Paths}(G)$ be the set of all paths in
$G$. We say that a graph $H$ is a topological minor of $G$ if there are
injective functions $\phi:V(H)\rightarrow V(G)$ and
$\varphi:E(H)\rightarrow{\sf Paths}(G)$ such that $(i)$ for all
$e=\\{h,h^{\prime}\\}\in E(H)$, $\phi(h)$ and $\phi(h^{\prime})$ are the
endpoints of $\varphi(e)$, $(ii)$ for distinct $e,e^{\prime}\in E(H)$, the
paths $\varphi(e)$ and $\varphi(e^{\prime})$ are internally vertex-disjoint,
and $(iii)$ there does not exist a vertex $v$ such that $v$ is in the image of
$\phi$ and there is an edge $e\in E(H)$ where $v$ is an internal vertex in the
path $\varphi(e)$.

Unbreakable Graphs. To formally introduce the notion of unbreakability, we
rely on the definition of a separation:

######  Definition 2.3.

[Separation] A pair $(X,Y)$ where $X\cup Y=V(G)$ is a separation if
$E(X\setminus Y,Y\setminus X)=\emptyset$. The order of $(X,Y)$ is $|X\cap Y|$.

Roughly speaking, a graph is breakable if it is possible to “break” it into
two large parts by removing only a small number of vertices. Formally,

######  Definition 2.4.

[$(s,c)$-Unbreakable graph] Let $G$ be a graph. If there exists a separation
$(X,Y)$ of order at most $c$ such that $|X\setminus Y|\geq s$ and $|Y\setminus
X|\geq s$, called an $(s,c)$-witnessing separation, then $G$ is
$(s,c)$-breakable. Otherwise, $G$ is $(s,c)$-unbreakable.

We next state an observation which immediately follows from the above
definition.

######  Observation 2.5.

Consider a graph $G$, an integer $k$ and a set $S\subseteq V(G)$ of size at
most $k$, where $G$ is $({\alpha(k)},k)$-unbreakable graph with
$|V(G)|>2{\alpha(k)}+k$. Then, there is exactly one connected component
$C^{*}$ in $G-S$ that has at least ${\alpha(k)}$ vertices and $|V(G)\setminus
V(C^{*})|<{\alpha(k)}+k$.

###  2.3 Counting Monadic Second Order Logic

The syntax of Monadic Second Order Logic (MSO) of graphs includes the logical
connectives $\vee,$ $\land,$ $\neg,$ $\Leftrightarrow,$ $\Rightarrow,$
variables for vertices, edges, sets of vertices and sets of edges, the
quantifiers $\forall$ and $\exists$, which can be applied to these variables,
and five binary relations:

  1. 1.

$u\in U$, where $u$ is a vertex variable and $U$ is a vertex set variable;

  2. 2.

$d\in D$, where $d$ is an edge variable and $D$ is an edge set variable;

  3. 3.

$\mathbf{inc}(d,u),$ where $d$ is an edge variable, $u$ is a vertex variable,
and the interpretation is that the edge $d$ is incident to $u$;

  4. 4.

$\mathbf{adj}(u,v),$ where $u$ and $v$ are vertex variables, and the
interpretation is that $u$ and $v$ are adjacent;

  5. 5.

equality of variables representing vertices, edges, vertex sets and edge sets.

Counting Monadic Second Order Logic (CMSO) extends MSO by including atomic
sentences testing whether the cardinality of a set is equal to $q$ modulo $r,$
where $q$ and $r$ are integers such that $0\leq q<r$ and $r\geq 2$. That is,
CMSO is MSO with the following atomic sentence:
$\mathbf{card}_{q,r}(S)=\mathbf{true}$ if and only if $|S|\equiv q\pmod{r}$,
where $S$ is a set. We refer to [6, 18, 19] for a detailed introduction to
CMSO.

We will crucially use the following result of Lokshtanov et al. [60] that
allows one to obtain a (non-uniform) FPT algorithm for CMSO-expressible graph
problems by designing an FPT algorithm for the problem on unbreakable graphs.

######  Proposition 2.6 (Theorem 1, [60]).

Let $\psi$ be a CMSO sentence and let $d>4$ be a positive integer. There
exists a function $\alpha:\mathbb{N}\rightarrow\mathbb{N}$, such that for
every $c\in\mathbb{N}$ there is an $\alpha(c)\in\mathbb{N}$, if there exists
an algorithm that solves CMSO$[\psi]$ on $(\alpha(c),c)$-unbreakable graphs in
time $\mathcal{O}(n^{d})$, then there exists an algorithm that solves
CMSO$[\psi]$ on general graphs in time $\mathcal{O}(n^{d})$.

###  2.4 Parameterized graph problems

A parameterized graph problem $\Pi$ is usually defined as a subset of
$\Sigma^{*}\times\mathbb{Z}^{+}$ where, in each instance $(x,k)$ of $\Pi,$ $x$
encodes a graph and $k$ is the parameter (we denote by $\mathbb{Z}^{+}$ the
set of all non-negative integers). In this paper we use an extension of this
definition (also used by Bodlaender et al. [8] and Fomin et al. [34]) that
permits the parameter $k$ to be negative with the additional constraint that
either all pairs with non-positive values of the parameter are in $\Pi$ or
that no such pair is in $\Pi$. Formally, a parametrized problem $\Pi$ is a
subset of $\Sigma^{*}\times\mathbb{Z}$ where for all
$(x_{1},k_{1}),(x_{2},k_{2})\in\Sigma^{*}\times\mathbb{Z}$ with
$k_{1},k_{2}<0$ it holds that $(x_{1},k_{1})\in\Pi$ if and only if
$(x_{2},k_{2})\in\Pi$. This extended definition encompasses the traditional
one and is needed for technical reasons (see Subsection 2.6). In an instance
of a parameterized problem $(x,k),$ the integer $k$ is called the parameter.

###  2.5 Boundaried Graphs

Here we define the notion of boundaried graphs and various operations on them.

######  Definition 2.7.

[Boundaried Graphs] A boundaried graph is a graph $G$ with a set $B\subseteq
V(G)$ of distinguished vertices and an injective labelling $\lambda_{G}$ from
$B$ to the set $\mathbb{Z}^{+}$. The set $B$ is called the boundary of $G$ and
the vertices in $B$ are called boundary vertices or terminals. Given a
boundaried graph $G,$ we denote its boundary by ${\delta(G)},$ we denote its
labelling by $\lambda_{G}$, and we define its label set by
$\Lambda(G)=\\{\lambda_{G}(v)\mid v\in\delta(G)\\}$. Given a finite set
$I\subseteq\mathbb{Z}^{+}$, we define ${{\cal F}_{I}}$ to denote the class of
all boundaried graphs whose label set is $I$. We also denote by ${{\cal F}}$
the class of all boundaried graphs. Finally we say that a boundaried graph is
a $t$-boundaried graph if $\Lambda(G)\subseteq\\{1,\ldots,t\\}$.

######  Definition 2.8.

[Gluing by $\oplus$] Let $G_{1}$ and $G_{2}$ be two boundaried graphs. We
denote by $G_{1}{\oplus}G_{2}$ the graph (not boundaried) obtained by taking
the disjoint union of $G_{1}$ and $G_{2}$ and identifying equally-labeled
vertices of the boundaries of $G_{1}$ and $G_{2}.$ In $G_{1}\oplus G_{2}$
there is an edge between two vertices if there is an edge between them either
in $G_{1}$ or in $G_{2}$, or both.

We remark that if $G_{1}$ has a label which is not present in $G_{2}$, or
vice-versa, then in $G_{1}\oplus G_{2}$ we just forget that label.

######  Definition 2.9.

[Gluing by $\oplus_{\delta}$] The boundaried gluing operation
$\oplus_{\delta}$ is similar to the normal gluing operation, but results in a
boundaried graph rather than a graph. Specifically $G_{1}\oplus_{\delta}G_{2}$
results in a boundaried graph where the graph is $G=G_{1}\oplus G_{2}$ and a
vertex is in the boundary of $G$ if it was in the boundary of $G_{1}$ or of
$G_{2}$. Vertices in the boundary of $G$ keep their label from $G_{1}$ or
$G_{2}$.

Let ${\cal G}$ be a class of (not boundaried) graphs. By slightly abusing
notation we say that a boundaried graph belongs to a graph class ${\cal G}$ if
the underlying graph belongs to ${\cal G}.$

######  Definition 2.10.

[Replacement] Let $G$ be a $t$-boundaried graph containing a set $X\subseteq
V(G)$ such that $\partial_{G}(X)=\delta(G).$ Let $G_{1}$ be a $t$-boundaried
graph. The result of replacing $X$ with $G_{1}$ is the graph $G^{\star}\oplus
G_{1},$ where $G^{\star}=G\setminus(X\setminus\partial(X))$ is treated as a
$t$-boundaried graph with $\delta(G^{\star})=\delta(G).$

###  2.6 Finite Integer Index

######  Definition 2.11.

[Canonical equivalence on boundaried graphs.] Let $\Pi$ be a parameterized
graph problem whose instances are pairs of the form $(G,k).$ Given two
boundaried graphs $G_{1},G_{2}~{}\in{\cal F},$ we say that
$G_{1}\\!\equiv_{\Pi}\\!G_{2}$ if $\Lambda(G_{1})=\Lambda(G_{2})$ and there
exists a transposition constant $c\in\mathbb{Z}$ such that

$\displaystyle\forall(F,k)\in{\cal F}\times\mathbb{Z}$
$\displaystyle(G_{1}\oplus F,k)\in\Pi\Leftrightarrow(G_{2}\oplus
F,k+c)\in\Pi.$

Here, $c$ is a function of the two graphs $G_{1}$ and $G_{2}$.

Note that the relation $\equiv_{\Pi}$ is an equivalence relation. Observe that
$c$ could be negative in the above definition. This is the reason we allow the
parameter in parameterized problem instances to take negative values.

Next we define a notion of “transposition-minimality” for the members of each
equivalence class of $\equiv_{\Pi}.$

######  Definition 2.12.

[Progressive representatives [8]] Let $\Pi$ be a parameterized graph problem
whose instances are pairs of the form $(G,k)$ and let ${\cal C}$ be some
equivalence class of $\equiv_{\Pi}$. We say that $J\in{\cal C}$ is a
progressive representative of ${\cal C}$ if for every $H\in{\cal C}$ there
exists $c\in\mathbb{Z}^{-},$ such that

$\displaystyle\forall(F,k)\in{\cal F}\times\mathbb{Z}\ \ \ (H\oplus
F,k)\in\Pi\Leftrightarrow(J\oplus F,k+c)\in\Pi.$ (1)

The following lemma guarantees the existence of a progressive representative
for each equivalence class of $\equiv_{\Pi}$.

######  Lemma 2.13 ([8]).

Let $\Pi$ be a parameterized graph problem whose instances are pairs of the
form $(G,k)$. Then each equivalence class of $\equiv_{\Pi}$ has a progressive
representative.

Notice that two boundaried graphs with different label sets belong to
different equivalence classes of $\equiv_{\Pi}.$ Hence for every equivalence
class ${\cal C}$ of $\equiv_{\Pi}$ there exists some finite set
$I\subseteq\mathbb{Z}^{+}$ such that ${\cal C}\subseteq{\cal F}_{I}$. We are
now in position to give the following definition.

######  Definition 2.14.

[Finite Integer Index] A parameterized graph problem $\Pi$ whose instances are
pairs of the form $(G,k)$ has Finite Integer Index (or is FII), if and only if
for every finite $I\subseteq\mathbb{Z}^{+},$ the number of equivalence classes
of $\equiv_{\Pi}$ that are subsets of ${\cal F}_{I}$ is finite. For each
$I\subseteq\mathbb{Z}^{+},$ we define ${\cal S}_{I}$ to be a set containing
exactly one progressive representative of each equivalence class of
$\equiv_{\Pi}$ that is a subset of ${\cal F}_{I}$. We also define ${\cal
S}_{\subseteq I}=\bigcup_{I^{\prime}\subseteq I}{\cal S}_{I^{\prime}}$.

The proof of next lemma is identical to the one given for [8, Lemma $8.4$]

######  Lemma 2.15 ([8]).

Let $\mathcal{H}$ family of graphs that is CMSO definable and union closed.
Then, Vertex Deletion to $\mathcal{H}$ has FII.

######  Lemma 2.16.

([46, Lemma $2$]). Let $\mathcal{H}$ family of graphs that is CMSO definable
and union closed. Then, Elimination Distance to $\mathcal{H}$ and Treewidth
Decomposition to $\mathcal{H}$ is CMSO definable.

###  2.7 Replacement lemma

This subsection is verbatim taken from Fomin et al. [34, Section $3.3$] and is
provided here only for completion. We only need to make few simple
modifications to suit our need.

######  Definition 2.17.

Let $\cal G$ denote the set of all graphs. A graph parameter is a function
$\Psi\colon\cal G\to\mathbb{Z}^{+}$. That is, $\Psi$ associates a non-negative
integer to a graph $G\in\cal G$. The parameter $\psi$ is called monotone, if
for every $G\in\cal G$, and for every $V_{1}\subseteq V_{2}$,
$\Psi(G[V_{2}])\geq\Psi(G[V_{1}])$.

We can use $\Psi$ to define several graph parameters such as treewidth, or
given a family $\cal F$ of graphs, a minimum sized vertex subset $S$ of $G$,
called modulator, such that $G-S\in{\cal F}$. Next we define a notion of
monotonicity for parameterized problems.

######  Definition 2.18.

([34, Definition $3.9$]). We say that a parameterized graph problem $\Pi$ is
positive monotone if for every graph $G$ there exists a unique
$\ell\in\mathbb{N}$ such that for all $\ell^{\prime}\in\mathbb{N}$ and
$\ell^{\prime}\geq\ell$, $(G,\ell^{\prime})\in\Pi$ and for all
$\ell^{\prime}\in\mathbb{N}$ and $\ell^{\prime}<\ell$,
$(G,\ell^{\prime})\notin\Pi$. A parameterized graph problem $\Pi$ is negative
monotone if for every graph $G$ there exists a unique $\ell\in\mathbb{N}$ such
that for all $\ell^{\prime}\in\mathbb{N}$ and $\ell^{\prime}\geq\ell$,
$(G,\ell^{\prime})\notin\Pi$ and for all $\ell^{\prime}\in\mathbb{N}$ and
$\ell^{\prime}<\ell$, $(G,\ell^{\prime})\in\Pi$. $\Pi$ is monotone if it is
either positive monotone or negative monotone. We denote the integer $\ell$ by
Threshold($G,\Pi$) (in short Thr($G,\Pi$)).

We first give an intuition for the next definition. We are considering
monotone functions and thus for every graph $G$ there is an integer $k$ where
the answer flips. However, for our purpose we need a corresponding notion for
boundaried graphs. If we think of the representatives as some “small
perturbation”, then it is the max threshold over all small perturbations
(“adding a representative = small perturbation”). This leads to the following
definition.

######  Definition 2.19.

([34, Definition $3.10$]). Let $\Pi$ be a monotone parameterized graph problem
that has FII and $\Psi$ be a graph parameter. Let ${\cal S}_{t}$ be a set
containing exactly one progressive representative of each equivalence class of
$\equiv_{\Pi}$ that is a subset of ${\cal F}_{I}$, where $I=\\{1,\ldots,t\\}$.
For a $t$-boundaried graph $G$, we define

$\displaystyle\iota(G)$ $\displaystyle=$
$\displaystyle\max_{G^{\prime}\in{\cal S}_{t}}\mbox{{\sc Thr($G\oplus
G^{\prime},\Pi$)}},$ $\displaystyle\mu(G)$ $\displaystyle=$
$\displaystyle\max_{G^{\prime}\in{\cal S}_{t}}\Psi(G\oplus G^{\prime})$

The next lemma says the following. Suppose we are dealing with some FII
problem and we are given a boundaried graph with boundary size $t$. We know it
has a representative of size $h(t)$ and we want to find this representative.
In general finding a representative for a boundaried graph is more difficult
than solving the corresponding problem. The next lemma says basically that if
we can find the “OPT” of a boundaried graph efficiently then we can
efficiently find its representative. Here by “OPT” we mean $\iota(G)$, which
is a robust version of the threshold function (under adding a representative).
And by efficiently we mean as efficiently as solving the problem on normal
(unboundaried) graphs.

######  Lemma 2.20.

([34, Lemma $3.11$]). Let $\Pi$ be a monotone parameterized graph problem that
has FII and $\Psi$ be a graph parameter. Furthermore, let $\cal A$ be an
algorithm for $\Pi$ that, given a pair $(G,k)$, decides whether it is in $\Pi$
in time $f(|V(G)|,\Psi(G))$. Then for every $t\in\mathbb{N},$ there exists a
$\xi_{t}\in\mathbb{Z}^{+}$ (depending on $\Pi$ and $t$), and an algorithm
that, given a $t$-boundaried graph $G$ with $|V(G)|>\xi_{t},$ outputs, in
$\mathcal{O}(\iota(G)(f(|V(G)|+\xi_{t},\mu(G)))$ steps, a $t$-boundaried graph
$G^{\star}$ such that $G\equiv_{\Pi}G^{\star}$ and $|V(G^{\star})|<\xi_{t}$.
Moreover we can compute the translation constant $c$ from $G$ to $G^{\star}$
in the same time.

###### Proof.

We give prove the claim for positive monotone problems $\Pi$; the proof for
negative monotone problems is identical. Let ${\cal S}_{t}$ be a set
containing exactly one progressive representative of each equivalence class of
$\equiv_{\Pi}$ that is a subset of ${\cal F}_{I}$, where $I=\\{1,\ldots,t\\}$,
and let $\xi_{t}=\max_{Y\in{\cal S}_{t}}|V(Y)|.$ The set ${\cal S}_{t}$ is
hardwired in the description of the algorithm. Let $Y_{1},\ldots,Y_{\rho}$ be
the set of progressive representatives in ${\cal S}_{t}$. Let ${\cal
F}_{t}={\cal F}_{I}$. Our objective is to find a representative $Y_{\ell}$ for
$G$ such that

$\displaystyle\forall(F,k)\in{\cal F}_{t}\times\mathbb{Z}$
$\displaystyle(G\oplus F,k)\in\Pi\Leftrightarrow(Y_{\ell}\oplus
F,k-\vartheta(X,Y_{\ell}))\in\Pi.$ (2)

Here, $\vartheta(X,Y_{\ell})$ is a constant that depends on $G$ and
$Y_{\ell}$. Towards this we define the following matrix for the set of
representatives. Let

$A[Y_{i},Y_{j}]=\mbox{{\sc Thr($Y_{i}\oplus Y_{j},\Pi$)}}$

The size of the matrix $A$ only depends on $\Pi$ and $t$ and is also hardwired
in the description of the algorithm. Now given $G$ we find its representative
as follows.

  * •

Compute the following row vector ${\cal X}=[\mbox{{\sc Thr($G\oplus
Y_{1},\Pi$)}},\ldots,\mbox{{\sc Thr($G\oplus Y_{\rho},\Pi$)}})]$. For each
$Y_{i}$ we decide whether $(G\oplus Y_{i},k)\in\Pi$ using the assumed
algorithm for deciding $\Pi$, letting $k$ increase from $1$ until the first
time $(G\oplus Y_{i},k)\in\Pi$. Since $\Pi$ is positive monotone this will
happen for some $k\leq\iota(G)$. Thus the total time to compute the vector
${\cal X}$ is $\mathcal{O}(\iota(G)(f(|V(G)|+\xi_{t},\mu(G)))$.

  * •

Find a translate row in the matrix $A(\Pi)$. That is, find an integer $n_{o}$
and a representative $Y_{\ell}$ such that

$\displaystyle[\mbox{{\sc Thr($G\oplus Y_{1},\Pi$)}},\mbox{{\sc Thr($G\oplus
Y_{2},\Pi$)}},\ldots,\mbox{{\sc Thr($G\oplus Y_{\rho},\Pi$)}}]$
$\displaystyle=[\mbox{{\sc Thr($Y_{\ell}\oplus Y_{1},\Pi$)}}+n_{0},\mbox{{\sc
Thr($Y_{\ell}\oplus Y_{2},\Pi$)}}+n_{0},\ldots,\mbox{{\sc Thr($Y_{\ell}\oplus
Y_{\rho},\Pi$)}}+n_{0}]$

Such a row must exist since ${\cal S}_{t}$ is a set of representatives for
$\Pi$; the representative $Y_{\ell}$ for the equivalence class to which $G$
belongs, satisfies the condition.

  * •

Set $Y_{\ell}$ to be $G^{\star}$ and the translation constant to be $-n_{0}$.

From here it easily follows that $G\equiv_{\Pi}G^{\star}$. This completes the
proof. ∎

We remark that the algorithm whose existence is guaranteed by the Lemma 2.20
assumes that the set ${\cal S}_{t}$ of representatives are hardwired in the
algorithm. In its full generality we currently donot known of a procedure that
for problems having FII outputs such a representative set. Thus, the
algorithms using Lemma 2.20 are not uniform.

Next we illustrate a situation in which one can can apply Lemma 2.20 to reduce
a portion of a graph. Let $\cal F$ be a family of interval graphs. Further,
let $\Pi$ be the Dominating Set problem and $\Psi$ denote the modulator to
$\cal F$. That is, given a graph $G$,

$\Psi(G)=\min_{S\subseteq V(G),G-S\in{\cal F}}|S|.$

It is possible to show that Dominating Set parameterized by $\Psi(G)$ is FPT.
That is, we can design an algorithm that can decide whether an instance
$(G,k)$ of Dominating Set is an Yes-instance in time $f(\Psi(G))\cdot
n^{\mathcal{O}(1)}$. In fact, in time
$2^{\mathcal{O}(\Psi(G))}n^{\mathcal{O}(1)}$. This implies that if we have a
$t$-boundaried graph $G$, then we can find a representative of it with respect
to Dominating Set in time $2^{\mathcal{O}(\mu(G))}n^{\mathcal{O}(1)}$. We will
see its uses in this way in Section 6.

##  3 Structural Results

###  3.1 Bounded Modulators on Unbreakable Graphs

In this section we show that for any $({\alpha(k)},k)$-unbreakable graph $G$
that has more than $3({\alpha(k)}+k)$ vertices and its
$\mathcal{H}$-elimination decomposition (resp. $\mathcal{H}$-tree
decomposition), $(T,\chi,L)$ of depth at most $k$, we have $|V(G)\setminus
L|\leq{\alpha(k)}+k$ and there is a large connected component in $G[L]$, by
proving the following two lemmas.

######  Lemma 3.1.

Consider a graph $G$, an integer $k$, and any $\mathcal{H}$-elimination
decomposition (resp. $\mathcal{H}$-tree decomposition) $(T,\chi,L)$ of depth
(resp. width) at most $k$ (resp. $k-1$), where $G$ is
$({\alpha(k)},k)$-unbreakable graph. Then, one of the following holds:

  1. 1.

$|V(G)|\leq 3({\alpha(k)}+k)$, or

  2. 2.

there is exactly one connected component $C^{*}$ in $G[L]$ that has at least
${\alpha(k)}$ vertices, and $|V(G)\setminus V(C^{*})|\leq{\alpha(k)}+k$.

Towards proving the lemma, we begin by stating a folklore result regarding
weighted trees (an explicit proof can be found, for instance, in the full
version of [5]).

######  Proposition 3.2.

Consider a tree $T$ and a weight function $w:V(T)\rightarrow\mathbb{N}$,
$\tau=\sum_{t\in V(T)}w(t)$ such that $1\leq w(t)\leq 2\tau/5$, for each $t\in
V(T)$. Then, there exists a non-leaf vertex $\widehat{t}$ in $T$ such that the
connected components of $T-\\{\widehat{t}\\}$ can be partitioned into two sets
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$, with
$\sum_{C\in\mathcal{C}_{1}}w(C)\leq 2\tau/3$ and
$\sum_{C\in\mathcal{C}_{2}}w(C)\leq 2\tau/3$, where $w(C)=\sum_{t\in
V(C)}w(t)$.

Next we prove useful lemma(s) about unbreakable graphs.

######  Lemma 3.3.

Consider a family of hereditary graphs $\mathcal{H}$. Furthermore, consider an
integer $k$, an $({\alpha(k)},k)$-unbreakable graph $G$ with more than
$3({\alpha(k)}+k)$ vertices, and an $\mathcal{H}$-elimination decomposition
$(T,\chi,L)$ of depth at most $k$ for $G$. Then, $G[L]$ has a connected
component with at least ${\alpha(k)}$ vertices.

###### Proof.

As $\mathcal{H}$ is hereditary, note that $G$ must also admit an
$\mathcal{H}$-elimination decomposition $(T^{\prime},\chi^{\prime},L)$, such
that: i) for each $t\in V(T^{\prime})$ we have $|\chi(t)|\geq 1$, ii) for each
$t\in V(T^{\prime})$, if $\chi(t)\cap L\neq\emptyset$, then $G[\chi(t)\cap L]$
is connected, and iii) the depth of $T^{\prime}$ is at most the depth of $T$.
Hereafter, we will consider an $\mathcal{H}$-elimination decomposition
$(T^{\prime},\chi^{\prime},L)$ for $G$ that satisfies the above conditions.
Towards a contradiction we suppose that the size of each connected component
in $G[L]$ is strictly less than ${\alpha(k)}$. With the above assumption, we
will exhibit an $({\alpha(k)},k)$-witnessing separation, which will contradict
that $G$ is $({\alpha(k)},k)$-unbreakable.

Let $T^{*}$ be the tree obtained from $T^{\prime}$, by arbitrarily connecting
one of the roots in $T^{\prime}$ to all the other roots. Formally, let
$\\{r_{1},r_{2},\cdots,r_{p}\\}$ be the set of roots in $T^{\prime}$ (note
that $p$ must be the number of connected components in $T^{\prime}$). We let
$V(T^{*})=V(T^{\prime})$ and
$E(T^{*})=E(T^{\prime})\cup\\{\\{r_{1},r_{i}\\}\mid
i\in[p]\setminus\\{1\\}\\}$. Also, let ${\sf
wht}:V(T^{*})\rightarrow\mathbb{N}$, such that for $t\in
V(T^{*})=V(T^{\prime})$, we have ${\sf wht}(t)=\chi(t)$.

By the construction of $T^{*}$ and ${\sf wht}$, we can obtain that for each
$t\in V(T^{*})$, $1\leq{\sf wht}(t)<{\alpha(k)}$ and $\tau=\sum_{t\in
V(T^{*})}{\sf wht}(t)=n$, where $n=|V(G)|$. As $n\geq 3({\alpha(k)}+k)$, we
have $2\tau/5>({\alpha(k)}+k)$, and hence for each $t\in V(T^{*})$, $1\leq{\sf
wht}(t)\leq 2\tau/5$. The tree $T^{*}$ and the weight function ${\sf wht}$,
satisfies the premises of Proposition 3.2. Thus, using the proposition, there
is a non-leaf node $t^{*}$ in $T^{*}$ such that connected components in
$T^{*}-\\{t^{*}\\}$ can be partitioned into two sets $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$, such that for each $j\in[2]$, ${\sf
wht}(\mathcal{C}_{j})=\sum_{C\in\mathcal{C}_{j}}{\sf wht}(C)\leq 2\tau/3\leq
2n/3\leq 2({\alpha(k)}+k)$, where ${\sf wht}(C)=\sum_{t\in V(C)}{\sf wht}(t)$.

For $i\in[2]$, let $Z_{i}=\bigcup_{C\in\mathcal{C}_{i}}V(C)$ and
$\widehat{V}_{i}=\\{v\in V(G)\setminus L\mid\mbox{ for some }t\in
Z_{i},\chi(t)=\\{v\\}\\}$. For $i\in[2]$, let $\widehat{U}_{i}=\cup_{t\in
Z_{i}}(\chi(t)\cap L)$. Let $V_{i}=\widehat{V}_{i}\cup\widehat{U}_{i}$, for
each $i\in[2]$. From construction of $T^{*}$ and ${\sf wht}$, we obtain that
$|V_{1}|\leq 2({\alpha(k)}+k)$. As $n>3({\alpha(k)}+k)$, we have
$|V_{2}|>{\alpha(k)}+k$. By similar arguments, we obtain
$|V_{1}|>{\alpha(k)}+k$. Observe that $V_{1}\cup
V_{2}=V(G)\setminus\chi(t^{*})$. Let $S$ be the set containing each vertex
$v\in V(G)\setminus L$, such that $t_{v}\in V(T^{*})$, where
$\chi(t_{v})=\\{v\\}$, $t_{v}$ is an ancestor of $t^{*}$ (possibly
$t_{v}=t^{*}$). Note that $|S|\leq k$.

Let $Y_{1}=V_{1}\cup S$ and $Y_{2}=V_{2}\cup S$. Note that $S=Y_{1}\cap
Y_{2}$, $|Y_{1}\setminus Y_{2}|=|Y_{1}\setminus S|\geq{\alpha(k)}$,
$|Y_{2}\setminus Y_{1}|=|Y_{2}\setminus S|\geq{\alpha(k)}$, $|S|\leq k$, and
$Y_{1}\cup Y_{2}=V(G)$. Moreover, by the construction of $Y_{1}$ and $Y_{2}$,
we have that there is no edge $\\{u,v\\}\in E(G)$, such that $u\in
Y_{1}\setminus S$ and $v\in Y_{2}\setminus S$. This implies that
$(Y_{1},Y_{2})$ is a separation of order $k$ in $G$ such that $|Y_{1}\setminus
Y_{2}|\geq{\alpha(k)}$, $|Y_{2}\setminus Y_{2}|\geq{\alpha(k)}$ This
contradicts the assumption that $G$ is $({\alpha(k)},k)$-unbreakable. ∎

Analogous to the above, we can prove a result regarding $\mathcal{H}$-tree
decompositions.

######  Lemma 3.4.

Consider a family of hereditary graphs $\mathcal{H}$. Furthermore, consider an
integer $k\geq 2$, an $({\alpha(k)},k)$-unbreakable graph $G$ with more than
$3({\alpha(k)}+k)$ vertices, and an $\mathcal{H}$-tree decomposition
$(T,\chi,L)$ of width at most $k-1$ for $G$. Then, $G[L]$ has a connected
component with at least ${\alpha(k)}$ vertices.

###### Proof.

If $L=V(G)$, then note $G$ must have a connected component that have exactly
one connected component with at least ${\alpha(k)}$ vertices, as $G$ is
$({\alpha(k)},k)$-unbreakable. Hereafter we assume that $V(G)\setminus
L\neq\emptyset$. As $\mathcal{H}$ is hereditary, $G$ must also admit an
$\mathcal{H}$-tree decomposition $(T^{\prime},\chi^{\prime},L)$, such that:

  1. 1.

for every distinct vertices $t,t^{\prime}\in V(T^{\prime})$ with $\chi(t)\cap
L=\emptyset$ and $\chi(t^{\prime})\cap L=\emptyset$, we have
$\chi(t)\not\subseteq\chi(t^{\prime})$,

  2. 2.

for each $t\in V(T^{\prime})$ with $\chi(t)\cap L\neq\emptyset$,
$\chi(t)\setminus L\subseteq\chi(t_{\sf par})$, where $t_{\sf par}$ is the
parent of $t$ in $T^{\prime}$.

  3. 3.

for each $t\in V(T^{\prime})$, if $\chi(t)\cap L\neq\emptyset$, then
$G[\chi(t)\cap L]$ is connected,

  4. 4.

the width of $T^{\prime}$ is at most the width of $T$, and

  5. 5.

$T^{\prime}$ is connected.

Hereafter, we will consider an $\mathcal{H}$-tree decomposition
$(T^{\prime},\chi^{\prime},L)$ for $G$ that satisfies the above conditions.
Towards a contradiction we suppose that the size of each connected component
in $G[L]$ is strictly less than ${\alpha(k)}$ vertices. We define a
(partition) function $\rho:V(T^{\prime})\rightarrow 2^{V(G)}$ using $\chi$ and
the properties of $(T^{\prime},\chi^{\prime},L)$ as follows. For each $t\in
V(T^{\prime})$, where: i) $\chi^{\prime}(t)\cap L\neq\emptyset$, we set
$\rho(t)=\chi^{\prime}(t)\cap L$, and ii) otherwise, we set
$\rho(t)=\chi^{\prime}(t)\setminus\chi^{\prime}(t_{\sf par})$, where $t_{\sf
par}$ is the parent (if it exists) of $t$ in $T^{\prime}$.666If $t$ is a root,
then $\rho(t)=\chi^{\prime}(t)$. Notice that for each $t\in V(T^{\prime})$,
$\rho(t)\neq\emptyset$ (recall $V(G)\setminus L\neq\emptyset$) and
$\\{\rho(t)\mid t\in V(T^{\prime})\\}$ is a partition of $V(G)$. We define the
weight function ${\sf wht}:V(T^{\prime})\rightarrow\mathbb{N}$, by setting,
for each $t\in V(T^{\prime})$, ${\sf wht}(t)=|\rho(t)|$. By the construction
of ${\sf wht}$ we can obtain that, for each $t\in V(T)$, $1\leq{\sf
wht}(t)\leq\max\\{{\alpha(k)}-1+k\\}\leq{\alpha(k)}+k$ (recall our assumption
that each connected component in $G[L]$ has less than ${\alpha(k)}$ vertices).
Furthermore, we have $\tau=\sum_{t\in V(T^{\prime})}{\sf wht}(t)=n=|V(G)|$.

As $n\geq 3({\alpha(k)}+k)$, we have $2\tau/5>({\alpha(k)}+k)$, and hence for
each $t\in V(T^{\prime})$, $1\leq{\sf wht}(t)\leq 2\tau/5$. The tree
$T^{\prime}$ and the weight function ${\sf wht}$, satisfies the premises of
Proposition 3.2. Thus, there is a non-leaf node $t^{*}$ in $T^{\prime}$ such
that connected components in $T^{\prime}-\\{t^{*}\\}$ can be partitioned into
two sets $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$, such that for each
$j\in[2]$, ${\sf wht}(\mathcal{C}_{j})=\sum_{C\in\mathcal{C}_{j}}{\sf
wht}(C)\leq 2\tau/3=2n/3$, where ${\sf wht}(C)=\sum_{t\in V(C)}{\sf wht}(t)$.
Moreover, ${\sf wht}(\mathcal{C}_{1}),{\sf wht}(\mathcal{C}_{2})\geq
n/3\geq{\alpha(k)}+k$. Let $S=\chi^{\prime}(t^{*})$, and note that as $t^{*}$
is a non-leaf node, we have $|S|\leq k$. For $i\in[2]$,
$V_{i}=\cup_{t\in\mathcal{C}_{i}}\rho(t)$. Notice that $(S\cup V_{1},S\cup
V_{2})$ is a separation of order $k$, where $|V_{1}\setminus
S|,|V_{2}\setminus S|\geq{\alpha(k)}$, which contradicts that $G$ is
$({\alpha(k)},k)$-unbreakable. ∎

Using the above two lemmas we obtain the desired result (Lemma 3.1).

###### Proof of Lemma 3.1.

Consider an integer $k$, an $({\alpha(k)},k)$-unbreakable graph $G$, and an
$\mathcal{H}$-elimination decomposition (resp. $\mathcal{H}$-tree
decomposition) $(T,\chi,L)$ for $G$, of depth (resp. width) $k$ (resp. $k-1$).
If $|V(G)|\leq 3({\alpha(k)}+k)$, then the condition required by the lemma is
trivially satisfied. Now consider the case when $|V(G)|>3({\alpha(k)}+k)$.
Note that $G$ must also admit an $\mathcal{H}$-elimination decomposition
(resp. $\mathcal{H}$-tree decomposition), say, $(T^{\prime},\chi^{\prime},L)$
such that for each $t\in V(T^{\prime})$, $G[\chi^{\prime}(t)\cap L]$ is
connected. From Lemma 3.3, $G[L]$ has a connected component of size at least
${\alpha(k)}$, and let $D$ be such a connected component, and $t^{*}\in
V(T^{\prime})$ be a vertex such that $V(D)\subseteq\chi^{\prime}(t^{*})$. Let
$S=\\{v\in V(G)\setminus L\mid\mbox{ for some }t\in
V(T^{\prime})\setminus\\{t^{*}\\},\chi^{\prime}(t)=\\{v\\},\mbox{ where $t$ is
an ancestor of }t^{*}\\}$ (resp., let $S=\chi^{\prime}(t^{*})\setminus L$).
Note that $|S|\leq k$, and $N_{G}(D)\subseteq S$. The above, together with the
assumption that $G$ is $({\alpha(k)},k)$-unbreakable implies that
$V(G)\setminus(S\cup V(D))<{\alpha(k)}$. From the above we can obtain that
$|V(G)\setminus L|\leq{\alpha(k)}+k$ and there is exactly one connected
component in $G[L]$ that has more than ${\alpha(k)}$ vertices. This concludes
the proof. ∎

###  3.2 Computing $\mathcal{H}$-Elimination Decomposition Using its Decision
Oracle

The objective of this section is to prove the following lemma.

######  Lemma 3.5.

Consider an algorithm $\mathscr{A}$, for Elimination Distance to
$\mathcal{H}$, that runs in time $f(\ell^{\prime})\cdot g(|V(G^{\prime})|)$,
for an instance $(G^{\prime},\ell^{\prime})$ of the problem.777We will use the
standard assumption from Parameterized Complexity that the functions $f$ and
$g$ are non-decreasing. For more details on this, please see Chapter 1 of the
book [23]. Then, for any given graph $G$ on $n$ vertices, we can compute an
$\mathcal{H}$-elimination decomposition for $G$ of depth
$\ell=\mathbf{ed}_{\mathcal{H}}(G)$, in time bounded by $f(\ell)\cdot
g(n)\cdot n^{\mathcal{O}(1)}$.

Consider a family of graphs $\mathcal{H}$, for which Treewidth Decomposition
to $\mathcal{H}$ admits an algorithm, say, $\mathscr{M}_{\sf elm}$, which
given a graph $G$ on $n$ vertices and an integer $k$, runs in time $f(k)\cdot
g(n)$, and output $1$ if $\mathbf{ed}_{\mathcal{H}}(G)\leq k$ and $0$,
otherwise. We design a recurive algorithm that given a graph $G$ and an
integer $k$, and returns an $\mathcal{H}$-elimination decomposition of depth
at most $k$, or returns that no such decomposition exists.

Consider a given graph $G$ and an integer $k$. We assume that the graph $G$ is
connected, as otherwise, we can apply our algorithm for each of its connected
components. We will explicitly ensure that, while making recursive calls, we
maintain the connectivity requirement. We now state the base cases of our
recursive algorithm.

Base Case 1. If $G\in\mathcal{H}$ and $k\geq 0$, then the algorithm returns
$(T=(\\{r\\},\emptyset),\chi:\\{r\\}\rightarrow 2^{V(G)},V(G))$, where
$\chi(r)=V(G)$, as the $\mathcal{H}$-elimination decomposition of $G$.

Base Case 2. If Base Case 1 is not applicable and $k\leq 0$, then return that
$\mathbf{ed}_{\mathcal{H}}(G)>k$.

For each $v\in V(G)$, let $\mathcal{C}_{v}$ be the set of connected components
in $G-\\{v\\}$

Base Case 3. If Base Case 1 and 2 are not applicable, and there is no $v\in
V(G)$, such that for every $C\in\mathcal{C}_{v}$, $(C,k-1)$ is a yes-instance
of Elimination Distance to $\mathcal{H}$, then return that
$\mathbf{ed}_{\mathcal{H}}(G)>k$.

The correctnesses of Base Case 1 and 2 are immediate from their descriptions.
If the first two base cases are not applicable, then $k\geq 1$ and
$\mathbf{ed}_{\mathcal{H}}(G)\geq 1$ must hold. Thus, for any
$\mathcal{H}$-elimination decomposition, say, $(T,\chi,L)$ for $G$, $T$ must
have at least one vertex which is not a leaf. The third base case precisely
returns that $\mathbf{ed}_{\mathcal{H}}(G)>k$, when the above condition cannot
be satisfied, thus its correctness follows. Using $\mathscr{M}_{\sf elm}$, we
can test if $(G,0)$ is a yes-instance of Elimination Distance to $\mathcal{H}$
in time bounded by $f(k)\cdot g(n)$. Thus, we can test/apply Base Case 1, 2
and 3 in time bounded by $f(k)\cdot g(n)\cdot n^{\mathcal{O}(1)}$. Hereafter
we assume that the base cases are not applicable.

Recursive Step. Find a vertex $v^{*}\in V(G)$, such that for every
$C\in\mathcal{C}_{v^{*}}$, $(C,k-1)$ is a yes-instance of Elimination Distance
to $\mathcal{H}$, using $\mathscr{M}_{\sf elm}$. Such a $v^{*}$ exists as Base
Case 3 is not applicable.

Recursively obtain an $\mathcal{H}$-elimination decomposition
$(T_{C},\chi_{C},L_{C})$ for the instance $(C,k-1)$, for each
$C\in\mathcal{C}_{v^{*}}$. Let $L^{*}=\bigcup_{C\in\mathcal{C}_{v^{*}}}L_{C}$,
and let $T^{*}$ be the forest defined as follows. We have
$V(T^{*})=\\{r^{*}\\}\cup(\bigcup_{C\in\mathcal{C}_{v^{*}}}V(T_{C}))$, where
$r^{*}$ is a new vertex, and $E(T^{*})$ contains all edges in $E(T_{C})$, for
each $C\in\mathcal{C}_{v^{*}}$, and for each root $r$ in some forest in
$T_{C}$, for some $\mathcal{C}_{v^{*}}$, the edge $\\{r^{*},r\\}$ belongs to
$E(T^{*})$. Finally, let $\chi^{*}:V(T^{*})\rightarrow 2^{V(G)}$ be the
function such that $\chi^{*}(r^{*})=\\{v^{*}\\}$, and for each
$C\in\mathcal{C}_{v^{*}}$ and $a\in V(T_{C})$, we have
$\chi^{*}(a)=\chi_{C}(a)$. Return $(T^{*},\chi^{*},L^{*})$ as the
$\mathcal{H}$-elimination decomposition for $G$.

The correctness of the above recursive step follows from its description.
Moreover, it can be execute in time bounded by $f(k)\cdot g(n)\cdot
n^{\mathcal{O}(1)}$, using $\mathscr{E}_{\sf mod}$.

The overall correctness of the algorithm follows from the correctness of each
of its base cases and recursive step. Moreover, as we can always assume that
$k\leq n$ and the depth of the recursion tree can be bounded by $k+1$, we can
obtain that our algorithm runs in time $f(k)\cdot g(n)\cdot
n^{\mathcal{O}(1)}$, using $\mathscr{E}_{\sf mod}$. By exhibiting the above
algorithm, we have obtained a proof of Lemma 3.5.

###  3.3 Computing $\mathcal{H}$-Tree Decomposition Using its Decision Oracle

The objective of this section is to prove the following lemma.

######  Lemma 3.6.

Consider an algorithm $\mathscr{A}$, for Treewidth Decomposition to
$\mathcal{H}$, that runs in time $f(\ell^{\prime})\cdot g(|V(G^{\prime})|)$,
for an instance $(G^{\prime},\ell^{\prime})$ of the problem.888Again, we
assume that the functions $f$ and $g$ are non-decreasing. Then, for any given
graph $G$ on $n$ vertices, we can compute an $\mathcal{H}$-tree decomposition
for $G$ of width $\ell=\mathbf{tw}_{\mathcal{H}}$, in time bounded by
$\big{(}f(\ell)\cdot g(n)+\ell^{\mathcal{O}(\ell^{2})}\big{)}\cdot
n^{\mathcal{O}(1)}+h(\mathcal{F})$, where $h(\mathcal{F})$ depends only on the
family $\mathcal{H}$.

Consider a family of graphs $\mathcal{H}$, for which Treewidth Decomposition
to $\mathcal{H}$ admits an algorithm, say, $\mathscr{T}_{\sf tw}$, which given
a graph $G$ on $n$ vertices and an integer $k$, runs in time $f(k)\cdot g(n)$,
and output $1$ if $\mathbf{tw}_{\mathcal{H}}(G)\leq k$ and $0$, otherwise. We
will assume that $\mathcal{H}$ is not the family of all graphs, otherwise, the
problem is trivial, i.e., we can return $(T=(\\{t\\},\emptyset),\chi,V(G))$,
where $\chi(t)=V(G)$, as the $\mathcal{H}$-tree decomposition of width $0$.

We will design an algorithm $\mathscr{D}_{\sf tw}$ which, for given a graph
$G$ on $n$ vertices, will construct an $\mathcal{H}$-tree decomposition for
$G$ of $\mathcal{H}$-treewidth $\ell=\mathbf{tw}_{\mathcal{H}}$, in time
bounded by $\ell^{\mathcal{O}(\ell^{3})}\cdot
f(\ell)\cdot|V(G)|^{\mathcal{O}(1)}+h(\mathcal{F})$, where $h(\mathcal{F})$ is
a number depending on the family $\mathcal{F}$. Intuitively speaking, we will
attach a flower of obstructions on each vertex and check if the resulting
graph has its $\mathcal{H}$-treewidth exactly the same as
$\mathbf{tw}_{\mathcal{H}}(G)$. If the $\mathcal{H}$-treewidth does not
increase, then we will be able to obtain that this vertex can be part of the
modulator. We repeat this procedure to identify the vertices $S\subseteq V(G)$
that go the the modulator. After this, we take the torso of $G[S]$ in $G$, to
obtain the graph (to be denoted by) $\widetilde{G}_{S}$. Then using the known
algorithm of Bodlaender [7], we compute a tree decomposition for
$\widetilde{G}_{S}$, using which we construct an $\mathcal{H}$-tree
decomposition for $G$.

We next state an observation that will be useful in constructing an
obstruction, i.e., a graph outside $\mathcal{H}$.

######  Observation 3.7.

There exists a number $h=h(\mathcal{H})$,999That is, $h$ depends on the family
$\mathcal{H}$. such that we can find a graph $H\notin\mathcal{H}$ in $h$ many
steps, where each step can be execute in constant time.

###### Proof.

We initialize $i=1$ and do following steps:

  1. 1.

Construct the set, $\mathcal{G}_{i}$, that contains all graph on exactly $i$
vertices.

  2. 2.

For each $H\in\mathcal{G}_{i}$, check if $(H^{\prime},0)$ is a no-instance of
Treewidth Decomposition to $\mathcal{H}$, using the algorithm
$\mathscr{T}_{\sf tw}$, and if it is a no-instance, then return the graph $H$
(and exit). Otherwise, increment $i$ by $1$ and go to Step $1$.

Let $q\geq 1$, such that $\mathcal{H}$ does not contain some graph on
(exactly) $q$ vertices. Note that $q$ is well-defined, as $\mathcal{H}$ is not
the family of all graphs by our assumption. Notice that at the iteration where
$i=q$, we will be able to output a graph that is not in $\mathcal{H}$. Also
the number of steps executed by the procedure we described depends only on $q$
(which in turn depends only on $\mathcal{H}$). This concludes the proof. ∎

We next state an easy observation using which we can compute
$\ell=\mathbf{tw}_{\mathcal{H}}(G)$ with the help of the algorithm
$\mathscr{T}_{\sf tw}$.

######  Observation 3.8.

For a given graph $G$ on $n$ vertices, we can compute (using $\mathscr{T}_{\sf
tw}$) $\ell=\mathbf{tw}_{\mathcal{H}}(G)$ in time bounded by
$\mathcal{O}(n)\cdot f(\mathbf{tw}_{\mathcal{H}}(G))\cdot g(n)$.

###### Proof.

We iterate over $i\in\mathbb{N}$ (starting from $0$) and check whether $(G,i)$
is a yes-instance of Treewidth Decomposition to $\mathcal{H}$ using
$\mathscr{T}_{\sf tw}$, and stop at the iteration where the instance is a yes-
instance. Note that, the iteration $i$ at which we stop, it must hold that
$i=\mathbf{tw}_{\mathcal{H}}(G)$. As $\mathbf{tw}_{\mathcal{H}}(G)\leq n$ and
$f$ is a non-decreasing function by our assumption, our procedure achieves the
claimed running time bound. ∎

We now move to formal description of our algorithm. We fix an arbitrary
ordering of vertices in $G$, and let $V(G)=\\{v_{1},v_{2},\cdots,v_{n}\\}$. We
compute $\ell=\mathbf{tw}_{\mathcal{H}}(G)$, using Observation 3.8. Let
$H^{*}$ be the graph returned by Observation 3.7, and let
$V(H^{*})=\\{u^{*}_{1},u^{*}_{2},\cdots,u^{*}_{q}\\}$. We will construct a
graph $G^{\prime}_{i}$ and a set $S_{i}\subseteq V(G)$, for each $i\in[n]$,
where we add a flower of obstruction at $v_{i}$ (and add $v_{i}$ to $S_{i}$)
if and only if after adding such obstructions, the $\mathcal{H}$-treewidth of
the resulting graph doesn’t change. Formally, we do the following.

  1. 1.

Set $G^{\prime}_{0}=G$ and $S_{0}=\emptyset$.

  2. 2.

For each $i\in[n]$ (in increasing order), we do the following:

    1. (a)

Initialize $G^{\prime}_{1}=G^{\prime}_{i-1}$ and $S_{i}=S_{i-1}$.

    2. (b)

We obtain the graph $\widehat{G}_{i}$ obtained from $G^{\prime}_{i-1}$ by
adding $k+2$ copies of $H$ at $v$ as follows. For $j\in[k+2]$, let $H^{*}_{j}$
be the graph such that
$E(H^{*}_{j})=\\{u^{*}_{1,j},u^{*}_{2,j},\cdots,u^{*}_{q,j}\\}$ and
$E(H^{*}_{j})=\\{\\{u^{*}_{p,j},u^{*}_{r,j}\\}\mid
p,r\in[q],\\{u^{*}_{p},u^{*}_{r}\\}\in E(H)\\}$. Furthermore, let
$H^{\prime}_{j}=H^{*}_{j}-\\{u^{*}_{1j}\\}$. We let $\widehat{G}_{i}$ be the
graph with
$V(\widehat{G}_{i})=V(G^{\prime}_{i-1})\bigcup\big{(}\cup_{j\in[k+2]}V(H^{\prime}_{j})\big{)}$
and
$E(\widehat{G}_{i})=E(G^{\prime}_{i-1})\bigcup\big{(}\cup_{j\in[k+2]}E(H^{\prime}_{j})\big{)}\bigcup\big{\\{}\\{v_{i},u^{*}_{p,j}\\}\mid
j\in[k+2],p\in[q]\mbox{ and }\\{u^{*}_{1},u^{*}_{p}\\}\in E(H)\big{\\}}$.

    3. (c)

Check if $(\widehat{G}_{i},\ell)$ is a yes-instance of Treewidth Decomposition
to $\mathcal{H}$ using $\mathscr{T}_{\sf tw}$. If the above is true, then set
$G^{\prime}_{i}=\widehat{G}_{i}$ and $S_{i}=S_{i-1}\cup\\{v_{i}\\}$, and
otherwise, set $G^{\prime}_{i}=G^{\prime}_{i-1}$ and $S_{i}=S_{i-1}$.

Next we show that, there is an $\mathcal{H}$-tree decomposition of optimal
width for $G$ which puts exactly the vertices in $S_{n}$ in the modulator.

######  Lemma 3.9.

There is an $\mathcal{H}$-tree decomposition, $(T,\chi,V(G)\setminus S_{n})$,
for $G$ of width $\ell=\mathbf{tw}_{\mathcal{H}}(G)$.

###### Proof.

For each $i\in[n]_{0}$, the construction of $G^{\prime}_{i}$ implies that
$G^{\prime}_{i}$ must admit an $\mathcal{H}$-tree decomposition
$(T^{\prime}_{i},\chi^{\prime}_{i},L^{\prime}_{i})$ of width
$\mathbf{tw}_{\mathcal{H}}(G)$, such that $S_{i}=(V(G^{\prime}_{i})\setminus
L^{\prime}_{i})\cap\\{v_{1},v_{2},\cdots,v_{i}\\}$.101010Here we use the fact
that $H^{*}$ is a graph that has smallest number of vertices, which does not
belong to $\mathcal{H}$. Thus, deletion of $v_{i}$ from $G^{\prime}_{i}$ would
imply that each of the newly attached obstructions at $v_{i}$ (if any) are
intersected. As $\mathcal{H}$ is a hereditary family of graphs, we can obtain
that for each $i\in[n]$ and $\chi_{i}:V(T^{\prime}_{i})\rightarrow 2^{V(G)}$,
where for $t\in V(T^{\prime}_{i})$, $\chi_{i}(t)=\chi^{\prime}_{i}(t)\cap
V(G)$, $(T^{\prime}_{i},\chi_{i},L^{\prime}_{i}\cap V(G))$ is an
$\mathcal{H}$-tree decomposition for $G$ of width
$\mathbf{tw}_{\mathcal{H}}(G)$, such that $S_{i}=V(G)\setminus
L^{\prime}_{i}$. The above in particular implies that,
$(T^{\prime}_{n},\chi_{n},V(G)\setminus S_{n})$ is an $\mathcal{H}$-tree
decomposition for $G$ of width $\mathbf{tw}_{\mathcal{H}}(G)$. This concludes
the proof. ∎

Let $S=S_{n}$ and $L=V(G)\setminus S$. Let $\widetilde{G}$ be the graph
obtained from $G$ with vertex set $V(G)$, by taking a torso with respect to
the connected components in $G[L]$. That is, $V(\widetilde{G})=V(G)$ and for
$u,v\in V(\widetilde{G})$, $\\{u,v\\}$ is an edge in $\widetilde{G}$ if and
only if one of the following holds: i) $\\{u,v\\}\in E(G)$, or ii) there is a
connected component $C$ in $G-S$ ($=G[L]$), such that $u,v\in N_{G}(C)$ and
$u\neq v$. We let $\widetilde{G}_{S}=\widetilde{G}[S]$

We have the following observation regarding $\widetilde{G}$, which follows
from its construction and Lemma 3.9.

######  Observation 3.10.

The following properties hold:

  1. 1.

A tuple $(T,\chi,V(G)\setminus S)$ is either an $\mathcal{H}$-tree
decomposition for both $G$ and $\widetilde{G}$, or none. Moreover, there is at
least one such $\mathcal{H}$-tree decomposition of width
$\mathbf{tw}_{\mathcal{H}}(G)$ for $\widetilde{G}$.

  2. 2.

Treewidth of $\widetilde{G}_{S}$ is $\mathbf{tw}_{\mathcal{H}}(G)$.

Due to the above observation, it is now enough to compute a tree decomposition
of $\widetilde{G}$ of width $\mathbf{tw}_{\mathcal{H}}(G)$, to obtain an
$\mathcal{H}$-tree decomposition for $G$ of width
$\mathbf{tw}_{\mathcal{H}}(G)$. We next use the following result, which
immediately follows as a corollary from the result of Bodlaender et al. [7].

######  Proposition 3.11 (see, [7] or Theorem 7.17 [23]).

There is an algorithm, which given a graph $G$ on $n$ vertices, in time
bounded by ${\sf tw}(G)^{\mathcal{O}({\sf tw}(G)^{2})}\cdot n$, computes a
tree decomposition of $G$ of width ${\sf tw}(G)$.

We are now ready to prove Lemma 3.6.

###### Proof of Lemma 3.6.

Consider a graph $G$ on $n$ vertices. We construct the graph $\widetilde{G}$
(and $\widetilde{G}_{S}$) as described previously. From Observation 3.7 and
the constructions of $G^{\prime}_{i}$ and $S_{i}$, for $i\in[n]$, implies that
$\widetilde{G}$ (and $\widetilde{G}_{S}$) can be constructed in time bounded
by $f(\ell)\cdot g(n)\cdot n^{\mathcal{O}(1)}+h(\mathcal{F})$, where
$\ell=\mathbf{tw}_{\mathcal{H}}(G)$. Then using Proposition 3.11 we can
compute a tree decomposition,
$(\widetilde{T}_{S},\widetilde{\chi}_{S}:V(\widetilde{T}_{S})\rightarrow
2^{V(\widetilde{G}_{S})})$ of width $\ell$, for $\widetilde{G}_{S}$ in time
bounded by $\ell^{\mathcal{O}(\ell^{2})}\cdot n^{\mathcal{O}(1)}$ (see item 2
of Observation 3.10). Recall that $S=V(\widetilde{G}_{S})$. For each connected
component $C$ in $G-S$, the construction of $\widetilde{G}_{S}$ implies that
$N_{G}(C)$ ($\subseteq S$) induces a clique in $\widetilde{G}_{S}$. Thus there
must exist $t\in V(\widetilde{T}_{S})$ such that
$N_{G}(C)\subseteq\widetilde{\chi}_{S}(t)$. We construct a tree from
$\widetilde{T}_{S}$ and a function $\chi:V(T)\rightarrow 2^{V(G)}$ as follows.
Initialize $T=\widetilde{T}_{S}$ and $\chi=\widetilde{\chi}_{S}$. For each
connected component $C$ in $G-S$, we add a new node $t_{C}$ and add the edge
$\\{t_{C},t^{*}_{C}\\}$ to $E(T)$, where $t^{*}_{C}$ is an arbitrary selected
node (if it exists) in $\widetilde{T}_{S}$, such that
$N_{G}(C)\subseteq\widetilde{\chi}_{S}(t^{*}_{C})$.111111If $t^{*}_{C}$ does
not exist, in particular, when $S=\emptyset$, then we just add the node
$t_{C}$. Furthermore, we set $\chi(t_{C})=N_{G}(C)\cup V(C)$. The above
construction together with Observation 3.10 implies that
$(T,\chi,V(G)\setminus S)$ is an $\mathcal{H}$-tree decomposition for $G$.
Note that we can construct $(T,\chi,V(G)\setminus S)$ in time bounded by
$\big{(}f(\ell)\cdot g(n)+\ell^{\mathcal{O}(\ell^{2})}\big{)}\cdot
n^{\mathcal{O}(1)}+h(\mathcal{F})$. This concludes the proof. ∎

##  4 Equivalences Among Deletion, Decomposition and Elimination

The overall schema of proof of the theorem is presented in Figure 2. Notice
that ones the implications depicted in the figure are obtained, we can
conclude the proof of Theorem 1.1. We will next discuss the results that are
used to obtain the proof, and we begin with a simple observation which
directly follows from the fact that
$\mathbf{tw}_{\mathcal{H}}(G)\leq\mathbf{ed}_{\mathcal{H}}(G)\leq\mathbf{mod}_{\mathcal{H}}(G)$.

Figure 2: Implications used to obtain proof of Theorem 1.1.

######  Observation 4.1.

The following implications hold:

  1. 1.

Statement 3 $\Rightarrow$ Statement 2 $\Rightarrow$ Statement 1.

  2. 2.

Statement 6 $\Rightarrow$ Statement 5 $\Rightarrow$ Statement 4.

  3. 3.

Statement 9 $\Rightarrow$ Statement 8 $\Rightarrow$ Statement 7.

We prove that Statement 1 implies Statement 5 and 9 in Section 4.1, by proving
the following lemma.

######  Lemma 4.2.

Consider a family $\mathcal{H}$ of graphs that is CMSO definable and is closed
under disjoint union and induced subgraphs. If Vertex Deletion to
$\mathcal{H}$ parameterized by $\mathbf{mod}_{\mathcal{H}}(G)$ is FPT, then i)
Elimination Distance to $\mathcal{H}$ parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$ is FPT, and ii) Treewidth Decomposition to
$\mathcal{H}$ parameterized by $\mathbf{tw}_{\mathcal{H}}(G)$ is FPT.

Intuitively speaking, we obtain the proof of the above lemma as follows.
Suppose that Vertex Deletion to $\mathcal{H}$, parameterized by
$\mathbf{mod}_{\mathcal{H}}(G)$, admits an FPT algorithm, say,
$\mathscr{M}_{\sf mod}$.121212For ease in readability, as much as possible, we
will use the letters $\mathscr{M},\mathscr{E}$ and $\mathscr{T}$ for
algorithms for the problems Vertex Deletion to $\mathcal{H}$, Elimination
Distance to $\mathcal{H}$ and Treewidth Decomposition to $\mathcal{H}$,
respectively. Moreover, the subscripts ${\sf mod}$, ${\sf elm}$ and ${\sf tw}$
will denote the parameterizations $\mathbf{mod}_{\mathcal{H}}(G)$,
$\mathbf{ed}_{\mathcal{H}}(G)$ and $\mathbf{tw}_{\mathcal{H}}(G)$,
respectively. We note that we aren’t fixing such algorithms, but whenever a
need to assume/obtain such algorithms arises, we will be using the above
letters/subscripts. We will intuitively explain how we obtain an FPT algorithm
for Elimination Distance to $\mathcal{H}$ parameterized by
$\mathbf{ed}_{\mathcal{H}}(G)$, using $\mathscr{M}_{\sf mod}$. Consider an
$\mathcal{H}$-elimination decomposition $(T,\chi,L)$ of depth at most $k$ for
$G$ (if it exists). From Lemma 3.1, either the number of vertices in $G$ is
bounded by $3({\alpha(k)}+k)$, in which we can resolve the instance by a
brute-force procedure, or $G[L]$ has exactly one large connected component,
denoted by $D^{*}$, and $V(G)\setminus V(D^{*})$ has size bounded by
${\alpha(k)}+k$. Let $t$ be the parent (if it exists) of $t^{*}$, where
$t^{*}$ is the leaf containing $V(D^{*})$. Roughly speaking, we will try to
determine the large component $D^{*}$ completely, and then resolve the
remaining instance. To this end, we will maintain a subset, $A^{*}\subseteq
V(G)$, which will also be the subset of vertices from $G$ that are associated
with the root-to-$t$ path in $T$, and thus, we will always have $|S|\leq k$.
We will look at the unique large connected component $C^{*}$ in $G-A^{*}$ (see
Observation 2.5), and try to fix it as much as possible in the following
sense. We will (roughly speaking) show that either an arbitrary solution for
$(C^{*},k)$ as an instance for Vertex Deletion to $\mathcal{H}$, obtained
using the assumed algorithm $\mathscr{M}_{\sf mod}$, is enough for us to
completely determine $D^{*}$, or we will be able to find a small connected set
contained in $C^{*}$, with small neighborhood containing an obstruction to
$\mathcal{H}$. In the latter case, we will further be able to show that any
such maximal connected set (with bounded neighborhood) must have a non-empty
intersection with the set of vertices in $G$ associated with the root-to-$t$
path in $T$. Thus, we will either be able to “grow” our set $A^{*}$ (upto size
at most $k$), or resolve the instance by brute-force. The above will give us
an algorithm as required by the lemma. We note that the algorithm for the case
of Treewidth Decomposition to $\mathcal{H}$ parameterized by
$\mathbf{tw}_{\mathcal{H}}(G)$ can be obtained in a very similar fashion, but
for this case, we will maintain that the set $S$ is the subset of vertices
present in the bag of $\mathcal{H}$-tree decomposition, that contains all the
vertices in the large component in $G[L]$.

In Section 4.2 we show that Statement 1 implies Statement 3, assuming that
Lemma 4.2 holds, by proving the following result.

######  Lemma 4.3.

Consider a family $\mathcal{H}$ of graphs that is CMSO definable and is closed
under disjoint union and induced subgraphs. If Vertex Deletion to
$\mathcal{H}$ parameterized by $\mathbf{mod}_{\mathcal{H}}(G)$ is FPT, then
the problem is also FPT when parameterized by $\mathbf{tw}_{\mathcal{H}}(G)$.

Intuitively speaking, we obtain a proof of the above lemma as follows. Suppose
that Vertex Deletion to $\mathcal{H}$ parameterized by
$\mathbf{mod}_{\mathcal{H}}(G)$ admits an FPT algorithm, say,
$\mathscr{M}_{\sf mod}$. Consider an instance $(G,k)$ of the problem Vertex
Deletion to $\mathcal{H}$. From Lemma 4.2, we can obtain that Treewidth
Decomposition to $\mathcal{H}$ parameterized by $\mathbf{tw}_{\mathcal{H}}(G)$
has an FPT algorithm, say, $\mathscr{T}_{\sf tw}$. Using the algorithm
$\mathscr{T}_{\sf tw}$ and Lemma 3.6, we compute an $\mathcal{H}$-tree
decomposition for $G$. For each leaf $t$ in $T$, where the graph
$G[\chi(t)\cap L]$ has large number of vertices, we replace $G[\chi(t)\cap L]$
by another graph, using Lemma 2.20, still maintaining equivalence without
increasing the parameter. After this, we are obtain to bound the (standard)
treewidth of the graph, and resolve the instance using Courcelle’s Theorem
[18]. The above gives us an FPT algorithm for Vertex Deletion to
$\mathcal{H}$, when parameterized by $\mathbf{tw}_{\mathcal{H}}$.

In Section 4.3 we prove that Statement 4 (resp. Statement 7) implies Statement
1, by proving the following lemma.

######  Lemma 4.4.

Consider a family $\mathcal{H}$ of graphs that is CMSO definable and is closed
under disjoint union and induced subgraphs. If Elimination Distance to
$\mathcal{H}$ (resp. Treewidth Decomposition to $\mathcal{H}$) parameterized
by $\mathbf{mod}_{\mathcal{H}}(G)$ is FPT, then Vertex Deletion to
$\mathcal{H}$ parameterized by $\mathbf{mod}_{\mathcal{H}}(G)$ is also FPT.

Roughly speaking, the above lemma is proved as follows. Consider an instance
$(G,k)$ of Vertex Deletion to $\mathcal{H}$. From Proposition 2.6, it is
enough for us to focus in $({\alpha(k)},k)$-unbreakable graphs, and thus we
assume that $G$ is such a graph. If $G$ has at most $2{\alpha(k)}+k$ vertices,
we resolve the instance by trying all possible subsets. Otherwise, using an
assumed FPT algorithm $\mathscr{X}_{\sf mod}$ for Elimination Distance to
$\mathcal{H}$ (resp. Treewidth Decomposition to $\mathcal{H}$) parameterized
by $\mathbf{mod}_{\mathcal{H}}(G)$, we compute an $\mathcal{H}$-elimination
decomposition (resp. $\mathcal{H}$-tree decomposition), say, $(T,\chi,L)$. Now
using Observation 2.5 we will to able to conclude that: i) there is exactly
one connected component $C^{*}$ in $G[L]$ which has more than ${\alpha(k)}$
vertices, ii) $S^{*}=N_{G}(C^{*})$ has size at most $k$, and iii)
$Z^{*}=V(G)\setminus V(C^{*})$ has size at most ${\alpha(k)}+k$. Using the
above, we are either able branch on vertices of $Z^{*}$, or conclude that
$S^{*}$ is already a solution for the given Vertex Deletion to $\mathcal{H}$
instance. The above gives us an algorithm for Vertex Deletion to
$\mathcal{H}$, when parameterized by $\mathbf{mod}_{\mathcal{H}}(G)$, using
the assumed FPT algorithm for Elimination Distance to $\mathcal{H}$ (resp.
Treewidth Decomposition to $\mathcal{H}$) parameterized by
$\mathbf{mod}_{\mathcal{H}}(G)$.

###  4.1 Proof of Lemma 4.2

The objective of this section is to prove Lemma 4.2. We will present the
result for Elimination Distance to $\mathcal{H}$, and later comment how we can
adapt exactly the same idea for Treewidth Decomposition to $\mathcal{H}$. Fix
any family $\mathcal{H}$ of graphs that is CMSO definable and is hereditary,
such that Vertex Deletion to $\mathcal{H}$ admits an FPT algorithm, say,
$\mathscr{M}_{\sf mod}$, which given an instance $(G^{\prime},\ell)$, where
$G^{\prime}$ is an $n$ vertex graph, correctly resolves the instance in time
bounded by $f_{\sf mod}(\ell)\cdot n^{\mathcal{O}(1)}$.

Let $(G,k)$ is an instance of the problem Elimination Distance to
$\mathcal{H}$. From Proposition 2.6, it is enough for us to design an
algorithm for $({\alpha(k)},k)$-unbreakable graphs, and thus, we assume that
$G$ is $({\alpha(k)},k)$-unbreakable. If $G$ has at most $3(ak+k)$ vertices,
then we can resolve the instance in FPT time, by brute force. Thus, the
interesting case is when $G$ has more than $3(ak+k)$ vertices and it is
$({\alpha(k)},k)$-unbreakable. We will begin by defining an extension version
of the problem for (large) unbreakable graphs, called $\alpha$-Extension
$\mathcal{H}$-Elimination Distance ($\alpha$-Ext $\mathcal{H}$-ED, for short),
which will lie at the heart of our FPT algorithm for Elimination Distance to
$\mathcal{H}$ (using $\mathscr{M}_{\sf mod}$ as a subroutine). Roughly
speaking, the problem $\alpha$-Ext $\mathcal{H}$-ED will (recursively) try to
compute (some of) the vertices that will be mapped to the root-to-leaf path
leading the the large connected component (see Lemma 3.1), which will be
enough for us to identify the large connected component in a decomposition.
Once we have the above set, we will be able to determine the unique large
connected component in the final decomposition, and then solve the remainder
of the problem using brute force as the number of vertices outside the large
connected component can be bounded by a function of $k$. We would like to
remark that, an intuitive level the above illustrates how the deletion and the
elimination problems coincide.

(Problem Definition) $\alpha$-Extension $\mathcal{H}$-Elimination Distance
($\alpha$-Ext $\mathcal{H}$-ED)
Input:  A graph $G$, an integer $k$, a set $A^{*}\subseteq V(G)$ of size at
most $k$, such that $G$ is an $({\alpha(k)},k)$-unbreakable graph and
$|V(G)|>3({\alpha(k)}+k)$.
Question:  Test if there is an $\mathcal{H}$-elimination decomposition
$(T,\chi,L)$, where $D^{*}$ is the unique connected component in $G[L]$ of
size at least ${\alpha(k)}$ (see Lemma 3.1) and $t^{*}\in V(T)$ is the vertex
with $V(D^{*})\subseteq\chi(t^{*})$, such that the following holds:

  1. 1.

$L\cap A^{*}=\emptyset$.

  2. 2.

For each $v\in N_{G}(D^{*})\cup A^{*}$, there is (unique non-leaf vertex)
$t\in V(T)\setminus\\{t^{*}\\}$, such that $\chi(t)=\\{v\\}$ and $t$ is an
ancestor of $t^{*}$ in $T$.

In the above, we say that $(T,\chi,L)$ is a solution to the $\alpha$-Ext
$\mathcal{H}$-ED instance $(G,k,A^{*})$.

The objective of the remainder of this section is to prove the following
lemma.

######  Lemma 4.5.

Equipped with the algorithm $\mathscr{M}_{\sf mod}$, we can design an
algorithm for $\alpha$-Ext $\mathcal{H}$-ED, that given an instance
$(G,k,A^{*})$, where $G$ is a graph on $n$ vertices, correctly decides whether
or not it is a yes-instance of the problem in time bounded by $(f_{\sf
mod}(k)+{({\alpha(k)}+k)}^{\mathcal{O}({\alpha(k)}+k)})\cdot
n^{\mathcal{O}(1)}$.

We prove the above lemma by exhibiting such an algorithm for $\alpha$-Ext
$\mathcal{H}$-ED. Let $(G,k,A^{*})$ be an instance of $\alpha$-Ext
$\mathcal{H}$-ED. As $|V(G)|\geq 3({\alpha(k)}+k)$, from Observation 2.5,
$G-A^{*}$ has a unique connected component of size at least ${\alpha(k)}$, we
denote that connected component by $C^{*}$. Note that from the observation we
also have $|V(G)\setminus V(C^{*})|<{\alpha(k)}+k$.

We design a branching algorithm for the problem, and we will use $k-|A^{*}|$
as the measure to analyse the running time of our algorithm. We start with
some simple cases, when we can directly resolve the given instance. (The time
required for the execution of our base cases and branching rules will be
provided in the runtime analysis of the algorithm.)

Notice that Elimination Distance to $\mathcal{H}$ is a special case of
$\alpha$-Ext-$\mathcal{H}$-Elimination Distance, namely, when
$A^{*}=\emptyset$. Thus to prove Lemma 4.2, it is sufficient to prove the more
general Lemma 4.5. Next, we give description of our branching algorithm for
the $\alpha$-Ext-$\mathcal{H}$-Elimination Distance problem.

Base Case 1: If $k-|A|=0$ and $C^{*}\notin\mathcal{H}$, then return that the
instance has no solution.

Notice that if the instance admits a solution, say, $(T,\chi,L)$, where
$D^{*}$ is the unique large connected component in $G[L]$, then
$V(D^{*})\subseteq V(C^{*})$ (see Observation 2.5). All the vertices in
$N_{G}(D^{*})\cup A^{*}$ must be mapped to non-leaf vertices in a single root-
to-leaf path. In Base Case 1, as $C^{*}\notin\mathcal{H}$, some neighbor of
$D^{*}$ in $G$ outside $A^{*}$ must also be mapped to (a non-leaf in) the same
root-to-leaf path. Thus the correctness of Base Case 1 follows.

Intuitively speaking, our next base case deals with the case when an arbitrary
deletion set for $C^{*}$ of size at most $k$ can be added to $A^{*}$ to make
the resulting $C^{*}$ belong to $\mathcal{H}$. We will later prove that if our
branching rules (to be described later) and Base Case 1 is not applicable,
then indeed we can obtain a solution to our instance using this base case.
Before formally describing our next base case, we state a simple observation
and introduce some notations.

The following observation uses the well-known self-reducibility property of
NP-complete problem, using which we can find a solution with the help of a
decision oracle.

######  Observation 4.6.

Given an instance $(G^{*},\ell)$ of Vertex Deletion to $\mathcal{H}$, using
the FPT algorithm $\mathscr{M}_{\sf mod}$ of Vertex Deletion to $\mathcal{H}$,
in time $f_{\sf mod}(\ell)\cdot n^{\mathcal{O}(1)}$ we can obtain a minimum
sized set $\widehat{S}\subseteq V(G^{*})$ of size at most $\ell$ such that
$G^{*}-\widehat{S}\in\mathcal{H}$ or return that no such set exists.

We define a boolean variable ${\sf bool}$ as follows. If $(C^{*},k-|A|)$ is a
no-instance of Vertex Deletion to $\mathcal{H}$, then we set ${\sf bool}=0$.
Otherwise, let $S^{*}$ be a minimum sized set computed using Observation 4.6.
If for any subset $Z\subseteq V(G)\setminus(V(C^{*})\cup A^{*})$, there is a
solution $(T,\chi,V(G)\setminus(A^{*}\cup S^{*}\cup Z))$, for the instance
$(G,k,A^{*}\cup S^{*})$, then set ${\sf bool}=1$, and otherwise, set ${\sf
bool}=0$. By Cayley’s Theorem [16], the number of distinct labelled forest on
$q$ vertices is bounded by $q^{\mathcal{O}(q)}$. Using the above together with
Observation 4.6 and the fact that $|V(G)\setminus(V(C^{*})\cup
A^{*})|<{\alpha(k)}+k$ (see Observation 2.5), allows us to construct ${\sf
bool}$ in time bounded by $(f_{\sf
mod}(k)+{({\alpha(k)}+k)}^{\mathcal{O}({\alpha(k)}+k)})\cdot
n^{\mathcal{O}(1)}$. We are now ready to state our next base case.

Base Case 2: If ${\sf bool}=1$, then return that $(G,k,A^{*})$ is a yes-
instance of the problem.

The correctness of the above base case follows from the fact that whenever
${\sf bool}$ is set to $1$, then we do have a solution for the instance
$(G,k,A^{*})$.

Roughly speaking, we will be able to say that, if we have a yes-instance, then
for any solution $(T,\chi,L)$ for the instance, when our base cases are not
applicable, there is a small connected subset $X^{*}\subseteq V(C^{*})$, with
bounded neighborhood containing an obstruction, that must be separated from
the large connected component in $G[L]$ (see Lemma 3.1). Moreover, as $X^{*}$
is contained in the large connected component $C^{*}$, we will be able to
guarantee that at least one vertex in the closed neighborhood of $X^{*}$ must
be mapped to some node in the root-to-leaf path of the node to which vertices
in $D^{*}$ are mapped. Before discussing further, we introduce some notations.

For a graph $\widehat{G}$ and integers $p,q\in\mathbb{N}$, a set $B\subseteq
V(\widehat{G})$ is a $(p,q)$-connected set in $\widehat{G}$, if
$\widehat{G}[B]$ is connected, $|B|\leq p$ and $|N_{\widehat{G}}(B)|\leq q$.
We say that a $(p,q)$-connected set $B$ in $\widehat{G}$ is maximal if there
does not exist another $(p,q)$-connected set $B^{*}$ in $\widehat{G}$, such
that $B\subset B^{*}$. Below we state a result regarding computation of
maximal $(p,q)$-connected sets in a graph, which directly follows from Lemma
3.1 of Fomin and Villanger [35].

######  Proposition 4.7.

For a graph $\widehat{G}$ on $n$ vertices and integers $p,q\in[n]$, the number
of $(p,q)$-connected sets in $\widehat{G}$ is bounded by $2^{p+q}\cdot n$.
Moreover, the set of all maximal $(p,q)$-connected sets in $\widehat{G}$ can
be computed in time bounded by $2^{p+q}\cdot n^{\mathcal{O}(1)}$.

We enumerate the set of all maximal $({\alpha(k)},k)$-connected sets in
$C^{*}$, and let $\mathcal{C}_{\sf conn}$ be the set containing all maximal
$({\alpha(k)}+k,k)$-connected sets $Q\subseteq V(C^{*})$, such that
$G[N_{C^{*}}[Q]]$ does not belong to $\mathcal{H}$. Note that using
$\mathscr{M}_{\sf mod}$ and Proposition 4.7, we can construct
$\mathcal{C}_{\sf conn}$ in time bounded by $f_{\sf mod}(0)\cdot
2^{\mathcal{O}({\alpha(k)}+k)}\cdot n^{\mathcal{O}(1)}$. We are now ready to
state our branching rule.

Branching Rule 1: If there is some $C\in\mathcal{C}_{\sf con}$, then for each
$v\in N_{G}[C]$ ($=N_{G}[C]\setminus A^{*}$), solve (recursively) the instance
$(G,k,A^{*}\cup\\{v\\})$. Moreover, return yes, if and only if one such
instance is a yes-instance of the problem.

The next lemma lies at the crux of our algorithm, which will help us establish
that one of the base cases or branching rule must be applicable. For the
following lemma, we suppose that $(G,A,k)$ has a solution and Base Case 1 and
2 are not applicable, and we consider a solution $(T,\chi,L)$ for the
instance, which maximizes $|V(G)\setminus L|$. As $G$ is
$({\alpha(k)},k)$-unbreakable, from Lemma 3.1 we can obtain that there is
exactly one connected component, say, $D^{*}$, in $G[L]$, that has at least
${\alpha(k)}$ vertices, and we let $t^{*}\in V(T)$ such that
$\chi(t^{*})\subseteq V(D^{*})$. We define let the set $S\subseteq
V(G)\setminus L$ contain all the vertices mapped to the root-to-$t^{*}$ path
in $T$, that is $S=\\{v\in V(G)\mid\chi(t)=\\{v\\},t\neq t^{*},t\text{ is an
ancestor of }t^{*}\mbox{ in }T\\}$.

######  Lemma 4.8.

We have $\mathcal{C}_{\sf conn}\neq\emptyset$, and for each
$C\in\mathcal{C}_{\sf conn}$, we have $S\cap N_{C^{*}}[C]\neq\emptyset$.

###### Proof.

As $C^{*}$ is the (unique) connected component in $G-A^{*}$ that has at least
${\alpha(k)}$ vertices, thus, we can obtain that $V(D^{*})\subseteq V(C^{*})$.
Let $Y$ be the set of vertices in $C^{*}$ that do not belong to the set $S\cup
V(D^{*})$, i.e., $Y=V(C^{*})\setminus(V(D^{*})\cup S)$. Let $\mathcal{Y}_{\sf
obs}$ be the set of connected components in $G[Y]$ that do not belong to
$\mathcal{H}$. We let $S_{\sf obs}\subseteq S\cap V(C^{*})$ be the set of
vertices in $S\cap V(C^{*})$ that are neighbors of some connected components
in $\mathcal{Y}_{\sf obs}$, i.e., $S_{\sf obs}=\\{v\in S\cap V(C^{*})\mid v\in
N_{G}(C)\mbox{ for some }C\in\mathcal{Y}_{\sf obs}\\}$. Furthermore, let
$S_{\sf rem}=(S\cap V(C^{*}))\setminus S_{\sf obs}$. Notice that
$V(D^{*}),S_{\sf rem},S_{\sf obs},Y$ is a partition of $V(C^{*})$ (possibly
with empty-sets).

Firstly consider the case when $S_{\sf obs}=\emptyset$, and we will argue that
Base Case 2 must be applicable, which will lead us to a contradiction. Note
that for the above case, $S_{\sf rem}=S\cap V(C^{*})$, where $|S|\leq k$, and
each connected component in $C^{*}-S_{\sf rem}=C^{*}-S$ must belong to
$\mathcal{H}$. As $(T,\chi,L)$ is a solution for the instance, we must have
$A^{*}\subseteq S$. From the above two statements we can obtain that
$(C^{*},k-|A^{*}|)$ is a yes-instance of Vertex Deletion to $\mathcal{H}$. Let
$S^{*}\subseteq V(C^{*})$ be the (same) minimum sized set computed using
Observation 4.6, while computation of ${\sf bool}$, such that each connected
component in $C^{*}-S^{*}$ is in $\mathcal{H}$. Note that $|S^{*}|\leq|S_{\sf
rem}|=|S\cap V(C^{*})|$ (recall that $S_{\sf obs}=\emptyset$). Let
$Z=V(G)\setminus(L\cup A^{*})\subseteq V(G)\setminus(V(C^{*})\cup A^{*})$. We
will argue that $(G,k,A^{*})$ admits a solution
$(T,\chi^{\prime},V(G)\setminus(A^{*}\cup S^{*}\cup Z))$, for an appropriately
constructed $\chi^{\prime}$, in which case ${\sf bool}=1$, contradicting that
Base Case 2 is not applicable. Set
$\chi(t^{*})=\chi(t^{*})\cup(V(C^{*})\setminus S^{*})$ and for each $t\in
V(T)\setminus\\{t^{*}\\}$, such that $t\cap L\neq\emptyset$, we set
$\chi^{\prime}(t)=\chi(t)\setminus V(C^{*})$. Let $S_{\sf
rem}=\\{u_{1},u_{2},\cdots,u_{p}\\}$ and
$S^{*}=\\{w_{1},w_{2},\cdots,w_{q}\\}$, where note that $q\leq p$. For each
$i\in[q]$, we set $\chi^{\prime}(t_{i})=\\{w_{i}\\}$, where $t_{i}$ is the
vertex in $T$, such that $\chi(t_{i})=\\{u_{i}\\}$. Notice that, as $C^{*}-S$
is in $\mathcal{H}$ and $\mathcal{H}$ is closed under disjoint union, we can
obtain that for each $t\in V(T)$, $G[\chi^{\prime}(t)]$ is in $\mathcal{H}$.
By the construction of $\chi^{\prime}$, note that
$(T,\chi^{\prime},V(G)\setminus(A^{*}\cup S^{*}\cup Z))$ satisfies item 1 to 3
of Definition 2.1. Thus we can conclude that
$(T,\chi^{\prime},V(G)\setminus(A^{*}\cup S^{*}\cup Z))$ is a solution for
$(G,k,A^{*})$.

We will next consider the case when $S_{\sf obs}\neq\emptyset$. As
$|V(G)\setminus V(D^{*})|<{\alpha(k)}+k$ (see Observation 3.1), we can obtain
that $|Y|$, and thus, the number of vertices in each connected component in
$\mathcal{Y}_{\sf obs}$ is less than ${\alpha(k)}+k$. Notice that for each
$C\in\mathcal{Y}_{\sf obs}$, $|N_{G}(C)|\leq|S|\leq k$, and thus, $C$ is an
$({\alpha(k)}+k,k)$-connected set in $G$. Thus, for each $C\in\mathcal{Y}_{\sf
obs}$, there must exists some $C^{\prime}\in\mathcal{C}_{\sf conn}$, such that
$V(C)\subseteq V(C^{\prime})$. The above together with the assumption $S_{\sf
obs}\neq\emptyset$ (and thus, $\mathcal{Y}_{\sf obs}\neq\emptyset$) we can
obtain that $\mathcal{C}_{\sf conn}\neq\emptyset$. By construction, for each
$C\in\mathcal{C}_{\sf conn}$, $V(C)\subseteq V(C^{*})$ and $N_{C^{*}}[C]$ is
not in $\mathcal{H}$. Moreover, as $C^{*}$ is connected and $C$ is a maximal
$({\alpha(k)}+k,k)$-connected set in $C^{*}$, we can obtain that
$N_{C^{*}}[C]\cap S\neq\emptyset$. This concludes the proof. ∎

We are now ready to prove Lemma 4.5.

###### Proof of Lemma 4.5..

From Proposition 2.6, it is enough for us to design an algorithm for
$({\alpha(k)},k)$-unbreakable graphs, therefore we design algorithm for case
when the input graph is $({\alpha(k)},k)$-unbreakable. Consider an instance
$(G,A^{*},k)$ of $\alpha$-Ext $\mathcal{H}$-ED, where $G$ is an
$({\alpha(k)},k)$-unbreakable graph. If the instance can be resolved using
Base Case 1 or 2, then the algorithm resolve it. Otherwise, from Lemma 4.8 we
know that the branching rule must be applicable. By our previous discussion,
the we can test/apply our base cases in time bounded by $(f_{\sf
mod}(k)+{({\alpha(k)}+k)}^{\mathcal{O}({\alpha(k)}+k)})\cdot
n^{\mathcal{O}(1)}$. Recall that for each set in $\mathcal{C}_{\sf conn}$, we
have $|N_{C^{*}}[C]|\leq{\alpha(k)}+2k$, and $\mathcal{C}_{\sf conn}$ can be
constructed in time bounded by $f_{\sf mod}(0)\cdot
2^{\mathcal{O}({\alpha(k)}+k)}\cdot n^{\mathcal{O}(1)}$. Also, the depth of
the recursion tree can be bounded by $k+1$ (see Base Case 1). Thus, the number
of nodes in the recursion tree can be bounded by
${({\alpha(k)}+2k)}^{\mathcal{O}({\alpha(k)}+2k)})$. Thus we can bound the
running time of our algorithm for $\alpha$-Ext $\mathcal{H}$-ED by $(f_{\sf
mod}(k)+f_{\sf mod}(0))\cdot({\alpha(k)}+k)^{\mathcal{O}({\alpha(k)}+k)}\cdot
n^{\mathcal{O}(1)}$. This concludes the proof. ∎

We will end this section with a remark regarding how we can obtain an FPT
algorithm for Treewidth Decomposition to $\mathcal{H}$ parameterized by
$\mathbf{tw}_{\mathcal{H}}(G)$, using $\mathscr{M}_{\sf mod}$. Consider an
instance $(G,k)$ of Treewidth Decomposition to $\mathcal{H}$, and an
$\mathcal{H}$-tree decomposition, $(T,\chi,L)$ for it, if it exists. For the
above case, we will define our extension version with respect to
$A^{*}\subseteq V(G)$ of size at most $k$, where we would want the unique
large connected component in $G[L]$ to have all its neighbors in $A^{*}$.
Notice that all our argument will work exactly with the above minor
modification. Thus, using exactly the same ideas as we presented for the case
of Elimination Distance to $\mathcal{H}$, we will be able to obtain an FPT
algorithm for Treewidth Decomposition to $\mathcal{H}$ parameterized by
$\mathbf{tw}_{\mathcal{H}}(G)$, as required by the lemma.

###  4.2 Prove of Lemma 4.3

Fix any family $\mathcal{H}$ of graphs that is CMSO definable and is closed
under disjoint union and taking induced subgraphs, such that Vertex Deletion
to $\mathcal{H}$ admits an FPT algorithm, say, $\mathscr{M}_{\sf mod}$, when
parameterized by $\mathbf{mod}_{\mathcal{H}}(G)$, running in time $f_{\sf
mod}(k)\cdot n^{\mathcal{O}(1)}$. From Lemma 4.2 (see Section 4.1), we can
obtain that Treewidth Decomposition to $\mathcal{H}$ admits an FPT algorithm,
say, $\mathscr{T}_{\sf tw}$, when parameterized by
$\mathbf{tw}_{\mathcal{H}}(G)$, running in time $f_{\sf tw}(k)\cdot
n^{\mathcal{O}(1)}$. We will design an FPT algorithm, $\mathscr{M}_{\sf tw}$,
for Vertex Deletion to $\mathcal{H}$, parameterized by
$\mathbf{tw}_{\mathcal{H}}(G)$, using $\mathscr{M}_{\sf mod}$ and
$\mathscr{T}_{\sf tw}$ as subroutines.

Let $\ell=\mathbf{tw}_{\mathcal{H}}(G)$. By instantiating Lemma 3.6 with the
algorithm $\mathscr{T}_{\sf tw}$, we can compute an $\mathcal{H}$-tree