# FPT Approximations for Packing and Covering Problems Parameterized by
Elimination Distance and Even Less

Tanmay Inamdar  Department of Informatics, University of Bergen, Norway.
Lawqueen Kanesh Indian Institute of Technology, Jodhpur Madhumita
Kundu-1-1footnotemark: -1 M. S. Ramanujan University of Warwick, United
Kingdom Saket Saurabh-2-2footnotemark: -2 Institute of Mathematical Sciences,
Chennai.
Tanmay Inamdar and Madhumita Kundu are supported by the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement No. 819416). M. S. Ramanujan is supported by
Engineering and Physical Sciences Research Council (EPSRC) grants EP/V007793/1
and EP/V044621/1. Saket Saurabh is supported by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement No. 819416), and Swarnajayanti Fellowship (No.
DST/SJF/MSA01/2017-18). y

###### Abstract

For numerous graph problems in the realm of parameterized algorithms, using
the size of a smallest deletion set (called a modulator) into well-understood
graph families as parameterization has led to a long and successful line of
research. Recently, however, there has been an extensive study of structural
parameters that are potentially much smaller than the modulator size. In
particular, recent papers [Jansen et al. STOC 2021; Agrawal et al. SODA 2022]
have studied parameterization by the size of the modulator to a graph family
$\mathcal{H}$ ($\mathbf{mod}_{\mathcal{H}}(\cdot)$), elimination distance to
$\mathcal{H}$ ($\mathbf{ed}_{\mathcal{H}}(\cdot)$), and
$\mathcal{H}$-treewidth ($\mathbf{tw}_{\mathcal{H}}(\cdot)$). These parameters
are related by the fact that $\mathbf{tw}_{\mathcal{H}}$ lower bounds
$\mathbf{ed}_{\mathcal{H}}$, which in turn lower bounds
$\mathbf{mod}_{\mathcal{H}}$. While these new parameters have been
successfully exploited to design fast exact algorithms their utility
(especially that of $\mathbf{ed}_{\mathcal{H}}$ and
$\mathbf{tw}_{\mathcal{H}}$) in the context of approximation algorithms is
mostly unexplored.

The conceptual contribution of this paper is to present novel algorithmic
meta-theorems that expand the impact of these structural parameters to the
area of FPT Approximation, mirroring their utility in the design of exact FPT
algorithms. Precisely, we show that if a covering or packing problem is
definable in Monadic Second Order Logic and has a property called Finite
Integer Index (FII), then the existence of an FPT Approximation Scheme (FPT-
AS, i.e., $(1\pm\epsilon)$-approximation) parameterized by
$\mathbf{mod}_{\mathcal{H}}(\cdot),\mathbf{ed}_{\mathcal{H}}(\cdot)$, and
$\mathbf{tw}_{\mathcal{H}}(\cdot)$ is in fact equivalent. As a consequence, we
obtain FPT-ASes for a wide range of covering, packing, and domination problems
on graphs with respect to these parameters. In the process, we show that
several graph problems, that are W[1]-hard parameterized by
$\mathbf{mod}_{\mathcal{H}}$, admit FPT-ASes not only when parameterized by
$\mathbf{mod}_{\mathcal{H}}$, but even when parameterized by the potentially
much smaller parameter $\mathbf{tw}_{\mathcal{H}}(\cdot)$. In the spirit of
[Agrawal et al. SODA 2022], our algorithmic results highlight a broader
connection between these parameters in the world of approximation. As concrete
exemplifications of our meta-theorems, we obtain FPT-ASes for well-studied
graph problems such as Vertex Cover, Feedback Vertex Set, Cycle Packing and
Dominating Set, parameterized by $\mathbf{tw}_{\mathcal{H}}(\cdot)$ (and
hence, also by $\mathbf{mod}_{\mathcal{H}}(\cdot)$ or
$\mathbf{ed}_{\mathcal{H}}(\cdot)$), where $\mathcal{H}$ is any family of
minor free graphs.

##  1 Introduction

One of the most widely studied graph problems in the area of parameterized
complexity is the $\mathcal{F}$-Vertex Deletion problem, where the input is a
graph $G$ and a number $k$ and the goal is – “Compute a set of at most $k$
vertices whose deletion places the resulting graph in the graph family $\cal
F$ or correctly conclude that such a set does not exist.” A solution to an
instance of $\mathcal{F}$-Vertex Deletion is called a modulator into
$\mathcal{F}$ and there are numerous results in parameterized complexity on
exploiting modulators into various graph families to design algorithms. Much
of this research has been motivated by the fact that inputs that have
modulators of small size into $\mathcal{F}$ turn out to be tractable for many
problems that are NP-complete in general while being polynomial-time solvable
on $\mathcal{F}$. In other words, it is possible to take efficient algorithms
for some problems on graphs in $\mathcal{F}$, and lift them to efficient
algorithms for these problems on graphs that are not necessarily in
$\mathcal{F}$, but have a small vertex modulator into $\mathcal{F}$, i.e.,
graphs that are “close” to $\mathcal{F}$. This leads to fixed-parameter
algorithms for these problems (i.e., running time bounded by $f(k)n^{O(1)}$,
where $k$ is the modulator size and $n$ is the input size) under these
parameterizations. Using the size of the smallest vertex modulator of a graph
into tractable graph families or “the distance from triviality” methodology
[17] has therefore become a rich source of interesting and useful parameters
for graph problems over the last two decades.

In light of the success of this line of research, recent years have seen a
shift towards identifying and exploring the power of “hybrid” parameters that
are upper bounded by the modulator size as well as certain graph-width
measures and can be arbitrarily (and simultaneously) smaller than both the
modulator size and these graph-width measures. Two specific parameters studied
in this line of research are: $\mathcal{H}$-elimination distance and
$\mathcal{H}$-treewidth of $G$. The $\mathcal{H}$-elimination distance of a
graph $G$ (denoted $\mathbf{ed}_{\mathcal{H}}(G)$) was introduced by Bulian
and Dawar [4] 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. Note 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$). For example, let $\mathcal{H}$ be the (infinite) family of
complete graphs, and let $G$ be a graph that contains a vertex $v$ that is
adjacent to some (non-empty) subset of vertices from a clique of size $t$, for
some $t\geq 1$. Then, $\mathbf{tw}(G)=t-1$, whereas
$\mathbf{tw}_{\mathcal{H}}(G)=0$ (in fact, even
$\mathbf{ed}_{\mathcal{H}}(G)=0$). Similarly, $\mathbf{tw}_{\mathcal{H}}(G)$
itself can be arbitrarily smaller than $\mathbf{ed}_{\mathcal{H}}(G)$ (see
[14, 19] for some examples).

Recent work by Agrawal et al. [1] and Jansen et al. [19] show that for many
basic graph problems in the literature and well-understood graph families
$\mathcal{F}$, one can indeed obtain FPT algorithms parameterized by
$\mathbf{ed}_{\mathcal{H}}$ and $\mathbf{tw}_{\mathcal{H}}$, thus expanding
the notion of useful distance from triviality to encompass these parameters as
well. Agrawal et al. [1] also showed a tight connection between
$\mathbf{mod}_{\mathcal{H}},\mathbf{ed}_{\mathcal{H}}$ and
$\mathbf{tw}_{\mathcal{H}}$ by showing that for these problems, having an FPT
algorithm parameterized by $\mathbf{mod}_{\mathcal{H}}$ was sufficient to
obtain FPT algorithms parameterized by the other two “smaller” parameters. In
addition to these results, there is also some recent work on computing
$\mathbf{ed}_{\mathcal{H}}$ and $\mathbf{tw}_{\mathcal{H}}$, where
$\mathcal{H}$ is the family of bipartite graphs [18], or a minor-closed family
[24].

Despite these leaps in our understanding of the parameterized complexity of
many problems, limitations remain. For instance, by requiring that the problem
be FPT parameterized by $\mathbf{mod}_{\mathcal{H}}$, we are implicitly
requiring that the problem be polynomial-time solvable on the class
$\mathcal{H}$. This rules out meaningful results for many basic problems and
established graph families $\mathcal{H}$. For instance, it is not interesting
to study Vertex Cover parameterized by $\mathbf{mod}_{\mathcal{H}}$ when
$\mathcal{H}$ is the class of planar graphs since Vertex Cover is NP-complete
on planar graphs [15]. However, it is efficiently approximable on planar
graphs (i.e., even has an Efficient PTAS) [11]. This state of the art brings
us to the following two natural questions and is the main motivation behind
this work.

Question 1: Can good approximation algorithms for a problem on the class
$\mathcal{H}$ be used to obtain good FPT approximation algorithms for the same
problem parameterized by $\mathbf{mod}_{\mathcal{H}}$? Question 2: Could we
obtain positive answers to the above question, but for the parameters
$\mathbf{ed}_{\mathcal{H}}$ and $\mathbf{tw}_{\mathcal{H}}$?

The notion of an FPT approximation algorithm is easily motivated by the
simultaneous existence of fixed-parameter intractability results as well as
polynomial-time inapproximability results for numerous problems in the
literature. Hence, the topic of FPT approximation, has been an extremely
active area of research in the last decade. For a comprehensive survey of the
state of the art, we refer the reader to the survey by Feldman et al. [9].

We note that we are not the first to study Question 1. In Marx’s classic
survey [23] on parameterized approximation, he outlines an FPT approximation
algorithm for Chromatic Number parameterized by the modulator to planar
graphs. More recently, Demaine et al. [7] studied this question
systematically, albeit restricted to polynomial-time approximation. They
developed a general theorem that gives sufficient conditions on the problem in
order to guarantee an affirmative answer to this question when the class
$\mathcal{H}$ has bounded treewidth or arboricity, but in their context, the
approximation ratio of the algorithms depends on $\mathbf{mod}_{\mathcal{H}}$.
However, Question 1 in the setting of FPT approximation is largely unexplored.
To the best of our knowledge, Question 2 has not been considered in the
literature and this is the main focus of our paper.

###  1.1 Our contributions

The main conceptual message of the paper is the following meta-result (stated
informally):

If a problem can be captured by a very expressible logic fragment (i.e,
Counting Monadic Second Order Logic (CMSO)) and has an appropriate graph
replacement subroutine (i.e., Finite Integer Index (FII)) and fulfils a few
other mild requirements, then the existence of an FPT-AS for the problem
parameterized by any of the three parameters
$\mathbf{mod}_{\mathcal{H}},\mathbf{ed}_{\mathcal{H}}$ and
$\mathbf{tw}_{\mathcal{H}}$ is equivalent to each other.

The formal version of our first meta-theorem in the context of the well-
studied family of vertex-deletion problems is given below. Say that a family
of graphs is well-behaved if it is hereditary and closed under disjoint union.

######  Theorem 1.

Let $\mathcal{H},\mathcal{F}$ be well-behaved families of graphs, where
$\mathcal{F}$ is CMSO-definable. Suppose
$\Pi=\textup{{Vertex}}\allowbreak\textup{{Deletion}}\allowbreak\textup{{ to
}}\allowbreak\text{$\mathcal{F}$}$ has FII. Then, the following statements are
equivalent.

  1. 1.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$
and $\epsilon$.

  2. 2.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{ed}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

  3. 3.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{tw}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

We also prove meta-theorems similar to Theorem 1 where $\Pi$ is ${\cal
F}$-Subgraph Packing (i.e., pack maximum number of vertex-disjoint subgraphs
isomorphic to graphs in $\mathcal{F}$) or $\mathcal{F}$-Minor Packing (i.e.,
pack maximum number of vertex-disjoint minor-models of graphs in
$\mathcal{F}$).

In order to invoke these equivalence theorems, we first show that a wide range
of graph problems, that are W[1]-hard (or para-NP hard) parameterized by
$\mathbf{mod}_{\mathcal{H}}$, admit FPT Approximation Schemes (FPT-ASes, i.e.,
$(1\pm\epsilon)$-approximation) when parameterized by
$\mathbf{mod}_{\mathcal{H}}$. Hence, as corollaries of our meta-results, we
also get the first FPT-ASes for the following (non-exhaustive list of)
problems parameterized by $\mathbf{tw}_{\mathcal{H}}$ (and hence, also by
$\mathbf{ed}_{\mathcal{H}}$). When $\mathcal{H}$ is apex-minor free, we obtain
this result for Independent Set, Triangle Packing. When $\mathcal{H}$ is minor
free, we are able to infer the same result for Vertex Cover, Feedback Vertex
Set, Cycle Packing (and more generally, $\mathcal{F}$-Minor Packing).

Finally, we identify Dominating Set and its connectivity constrained variant
along with Connected Vertex Cover as interesting special cases that are not
covered by the framework developed above and give purpose-built FPT-ASes for
them parameterized by $\mathbf{mod}_{\mathcal{H}}$ and then also prove an
equivalence theorem in the same spirit as Theorem 1.

In summary, our work highlights many natural problems for which the answer to
Question 2 is affirmative. Finally, we note that in Theorem 1 and its
variants, due to their generality, we only obtain _non-uniform_ FPT-ASes. In
Conclusion, we briefly discuss certain scenarios where it may be possible to
obtain uniform FPT-ASes.

###  1.2 Our techniques

We first summarize the technique behind our FPT-ASes parameterized by
$\mathbf{mod}_{\mathcal{H}}$, which we dub “Bucket vs Ocean”. Recall that this
is required in order to invoke Theorem 1 to get our eventual results, i.e.,
FPT-ASes parameterized by $\mathbf{tw}_{\mathcal{H}}$ and
$\mathbf{ed}_{\mathcal{H}}$. We remark that throughout the paper, we assume
that our FPT-AS parameterized by, say $\mathbf{mod}_{\mathcal{H}}$ (resp.
$\mathbf{ed}_{\mathcal{H}},\mathbf{tw}_{\mathcal{H}}$) is also provided with a
modulator to $\mathcal{H}$ (resp. $\mathcal{H}$-elimination/tree
decomposition) of the appropriate size (resp. width). For
$\mathbf{ed}_{\mathcal{H}}$ and $\mathbf{tw}_{\mathcal{H}}$, one can use
algorithms from [14, 19, 1, 18] to compute the appropriate decompositions
exactly. Alternatively, one can use the recent result of [20] to compute
constant approximations thereof.

Consider a special case of Vertex Deletion to  $\mathcal{F}$ , say Vertex
Cover. Consider an $H$-minor free graph family $\mathcal{H}$, where VC admits
an EPTAS. Consider a graph $G$ and $M\subseteq V(G)$ of size
$\mathbf{mod}_{\mathcal{H}}(G)$ such that $G-M\in\mathcal{H}$. We use the
known EPTAS on $G-M$ to compute an $(1+\epsilon/2)$-approximate solution to
VC, call it $S$. Next, we compare $|S|$ with $|M|$, and consider two cases. If
$|M|<\epsilon/3\cdot|S|\leq(1+\epsilon/2)\cdot\textup{{OPT}}(G-M)$, i.e.,
$\textup{{OPT}}(G-M)$ is like an “ocean”, compared to a “bucket” of water that
is $M$, then we can add the bucket to the ocean “for free”, i.e.,
$|S|+|M|\leq(1+\epsilon)\cdot\textup{{OPT}}(G-M)\leq(1+\epsilon)\cdot\textup{{OPT}}(G)$.
Otherwise, if $|M|$ and $|S|$ are comparable, then $\textup{{OPT}}(G)\leq
3\cdot\mathbf{mod}_{\mathcal{H}}(G)/\epsilon$, in which case we can use the
FPT algorithm for Vertex Cover, which is in fact in FPT in
$\mathbf{mod}_{\mathcal{H}}$ and $\epsilon$. This is the high level idea
behind our FPT-ASes parameterized by $\mathbf{mod}_{\mathcal{H}}$, although
one has to overcome several problem-specific challenges to make it work for
the other problems.

A more sophisticated version of the idea also turns out to be useful in
proving the equivalence theorem. Again, let us consider the example of Vertex
Cover and $\mathcal{H}$ being an $H$-minor free graph family. Having armed
ourselves with an FPT-AS parameterized by $\mathbf{mod}_{\mathcal{H}}$ as in
the previous paragraph, now our task is to generalize to
$\mathbf{tw}_{\mathcal{H}}$. To this end, we consider each bag $\chi(t)$
corresponding to a node $t$ in the $\mathcal{H}$-tree decomposition (defined
formally in the next section), which consists of
$\ell\leq\mathbf{tw}_{\mathcal{H}}(G)+1$ vertices, say $R_{t}$, which locally
act like a modulator to a disjoint “base graph”, say $G[H_{t}]\in\mathcal{H}$.
We use the same “Bucket vs Ocean” idea to classify each node as _good_ or
_bad_. A node $t$ is _good_ , if a $(1+\epsilon)$-approximate solution $S_{t}$
for $G[H_{t}]$ is like an “ocean” compared to $R_{t}$. In this case, we can
again add $R_{t}$ to $S_{t}$ “for free”. Otherwise, we say that a node $t$ is
bad, if $\textup{{OPT}}(G[H_{t}])$ is bounded by $3\ell/\epsilon$. From here,
our task is to reduce the treewidth of the graph induced by the vertices in
the bags of bad nodes. To this end, we use the FII property as well as the
FPT-AS to perform a series of “graph replacements” in each bad node, where in
each iteration, we replace the corresponding bag with an “equivalent subgraph”
of size bounded by a function of $\ell$ and $\epsilon$. At the end of this
procedure, the resulting graph has treewidth, and we can use the CMSO-
definability and Courcelle’s theorem [5] to find an optimal solution (that can
then be translated back to the original instance). It can be shown that the
resulting solution is a $(1+\epsilon)$-approximate solution for the entire
graph, and the whole algorithm runs in time FPT in $\mathbf{tw}_{\mathcal{H}}$
and $\epsilon$.

##  2 Preliminaries

For an instance $\mathcal{I}$ of an optimization problem $\Pi$, we denote the
value/size of an optimal solution by $\textup{{OPT}}_{\Pi}(\mathcal{I})$, and
may omit the subscript if the problem is clear from the context. An algorithm
that, for any feasible instance of minimization (resp. maximization) problem
$\Pi$, returns a solution of cost/size at most (resp. at least)
$\alpha\cdot\textup{{OPT}}$, is called an $\alpha$-approximation. We say that
a minimization (resp. maximization) problem $\Pi$ admits an FPT-AS (FPT-
Approximation Scheme) parameterized by a parameter $t$ and $\epsilon$, if
there exists an $(1+\epsilon)$-approximation (resp.
$(1-\epsilon)$-approximation) algorithm with running time of the form
$f(t,\epsilon)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$, for some computable
function $f$. Similarly, we say that $\Pi$ admits an EPTAS (efficient
polynomial-time approximation scheme), if there exists a
$(1+\epsilon)$-approximation (resp. a $(1-\epsilon)$-approximation) algorithm
with running time of the form
$g(\epsilon)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$, for some computable function
$g$.

Graphs. Consider a graph $G$. We denote by $V(G)$ and $E(G)$, the set of
vertices and the set of edges of the graph $G$, respectively. We say that a
graph $H$ is a subgraph of $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq
V(G)$. We say that $H$ is an induced subgraph of $G$ if
$E(H)=\\{uv~{}|~{}u,v\in V(H),uv\in E(G)\\}$. Let $S\subseteq V(G)$, by $G[S]$
we denote the graph $G$ induced on set $S$. For $S\subseteq V(G)$, by $G-S$,
we denote the graph $G[V(G)\setminus S]$. That is, the vertex set of $G-S$ is
$V(G)\setminus S$ and the edge set is $\\{uv|u,v\notin S,uv\in E(G)\\}$. Let
$F\subseteq E(G)$, by $G-F$, we denote the graph with vertex set $V(G)$ and
edge set $E(G)\setminus F$. By vertex (edge) deletion operation or deletion of
a vertex $w$ (edge $uv$) in $G$, we mean the graph $G-w$ ($G-\\{uv\\}$)
obtained by deleting vertex $w$ (edge $uv$) from $G$. For singleton vertex and
edge subsets, we use $G-w$ and $G-uv$. By edge contraction operation or
contraction of an edge $uv$ in $G$ we mean deleting vertices $u,v$ in $G$ and
adding a new vertex $w$, and making $w$ adjacent to all the neighbors of
$u,v$, i.e., the resulting graph has vertex set
$V(G)\setminus\\{u,v\\}\cup\\{w\\}$ and edge set
$\\{xy|x,y\notin\\{u,v\\}\\}\cup\\{wx|x\in N(u)\cup N(v)\\}$. Let $G_{1}$ and
$G_{2}$ be two graphs on $n_{1},n_{2}$ vertices and $m_{1},m_{2}$ edges,
respectively. By disjoint union of $G_{1},G_{2}$ denoted as $G_{1}\uplus
G_{2}$, we denote the graph with $n_{1}+n_{2}$ vertices and $m_{1}+m_{2}$
edges, where vertex set of $G_{1}\uplus G_{2}$ is $V(G_{1})\cup V(G_{2})$ and
edge set of $G_{1}\uplus G_{2}$ is $E(G_{1})\cup E(G_{2})$. We refer the
reader to the book of Diestel [8] for standard graph-related terms that are
not explicitly defined here.

######  Definition 1 (Graph Minor).

A graph $H$ is a _minor_ of $G$ if it can be obtained by a sequence of vertex
deletions, edge deletions, and edge contractions.

Let $\mathcal{G}$ denote the family of all graphs. We say that a family
$\mathcal{F}\subseteq\mathcal{G}$ of graphs is _hereditary_ if for any graph
$G\in\mathcal{F}$, every induced subgraph $G^{\prime}$ of $G$ also belongs to
$\mathcal{F}$. We say that a family $\mathcal{F}\subseteq\mathcal{G}$ is
_closed under disjoint union_ if for any $G_{1},G_{2}\in\mathcal{F}$, the
graph $G$ obtained by taking the disjoint union of $G_{1}$ and $G_{2}$, also
belongs to $\mathcal{F}$. We say that a family
$\mathcal{F}\subseteq\mathcal{G}$ is _well-behaved_ if it is (i) hereditary,
and (ii) closed under disjoint union.

Graph Decomposition. The following definitions are borrowed from [1]. For a
graph $G$, $\mathbf{mod}_{\mathcal{H}}(G)$ denotes the size of a smallest
vertex set $S$ such that $G-S\in\mathcal{H}$. If $G-S\in\mathcal{H}$, then $S$
is called a modulator to $\mathcal{H}$.

######  Definition 2.

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

  1. 1.

For each internal node $t\in V(T)$, we have that $|\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 leaf $t$ in $T$, we have $\chi(t)\subseteq L$, such that the graph
$G[\chi(t)]$, called a base component, belongs to $\mathcal{H}$. Furthermore,
$(\chi(t))_{\text{leaf }t}$ forms a partition of $L$.

  4. 4.

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

The depth of a rooted tree $T$ is the maximum number of edges on a root-to-
leaf path in $T$. We refer to the union of base components as the set of base
vertices. The $\mathcal{H}$-elimination distance of $G$, denoted as
$\mathbf{ed}_{\mathcal{H}}(G)$, is the minimum depth of an
$\mathcal{H}$-elimination forest for $G$. Note that a pair $(T,\chi)$ is a
(standard) elimination forest of $\mathcal{H}$ is a class of empty graphs,
i.e., the base components are empty. In this case,
$\mathbf{ed}_{\mathcal{H}}(G)$ is known as the _treedepth_ of $G$, and is
denoted as $\mathbf{td}(G)$.

Just like the notion of $\mathcal{H}$-elimination decomposition generalizes
the notion of elimination forest, the following is an analogous generalization
of the notion of tree decomposition.

######  Definition 3.

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

  1. 1.

For each $v\in V(G)$, the nodes $\left\\{t\in V(T):v\in\chi(t)\right\\}$
induce a non-empty connected subtree in $T$.

  2. 2.

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

  3. 3.

For each vertex $v\in L$, there is a _unique leaf_ $t\in V(T)$ for which
$v\in\chi(t)$.

  4. 4.

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

The _width_ of an $\mathcal{H}$-tree decomposition is defined as
$\max\left\\{0,\max_{t\in V(T)}|\chi(t)\setminus L|-1\right\\}$. The
$\mathcal{H}$-treewidth of $G$, denoted by $\mathbf{tw}_{\mathcal{H}}(G)$, is
the minimum width of an $\mathcal{H}$-tree 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, where the choice
of $\mathcal{H}$ is irrelevant.

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 [2, 5] for a detailed introduction to CMSO.

##  3 Vertex Deletion to $\mathcal{F}$

In this section we give our “first equivalence” result. Towards that, first in
Section 3.2, we design concrete FPT-ASes for several Vertex Deletion to
$\mathcal{F}$ type problems (e.g., Vertex Cover, Feedback Vertex Set
parameterized by $\mathbf{mod}_{\mathcal{H}}$, where $\mathcal{H}$ is an apex-
minor family of graphs. Then, in Section 3.3 we prove our main equivalence
theorem, which lets us extend the previous FPT-ASes parameterized by
$\mathbf{mod}_{\mathcal{H}}(\cdot)$ to $\mathbf{ed}_{\mathcal{H}}(\cdot)$, and
$\mathbf{tw}_{\mathcal{H}}(\cdot)$.

###  3.1 Preliminaries for Vertex Deletion to  $\mathcal{F}$

We focus on the following problem, specifically on the case where
$\mathcal{F}$ is some fixed well-behaved family of graphs.

Vertex Deletion to  $\mathcal{F}$ Input: An instance $(G,k)$, where $G=(V,E)$
is a graph, and $k\geq 0$ is an integer. Question: Does there exist a subset
$S\subseteq V(G)$ of size at most $k$, such that $G-S\in\mathcal{F}$?

Optimization variant. Let $\mathcal{F}$ be a well-behaved family of graphs.
For a graph $G$, a set $S\subseteq V(G)$ is said to be a _solution_ to Vertex
Deletion to  $\mathcal{F}$ , if $G-S\in\mathcal{F}$. In the optimization
variant of Vertex Deletion to  $\mathcal{F}$ , we want to find a solution of
the smallest cardinality. By slightly abusing the notation, we will use Vertex
Deletion to  $\mathcal{F}$ to refer to the decision as well as the
optimization version, and will only disambiguate when strictly necessary. Note
that assuming $\mathcal{F}$ contains at least one graph, the hereditary
property implies that the empty graph belongs to $\mathcal{F}$, which means
that $V(G)$ is always a solution to Vertex Deletion to  $\mathcal{F}$ .

######  Observation 1.

Let $\mathcal{F}$ be a well-behaved family, and let
$\Pi=\textup{{Vertex}}\allowbreak\textup{{Deletion}}\allowbreak\textup{{ to
}}\allowbreak\text{$\mathcal{F}$}$. Then, for any graph $G$ and any subset
$S\subseteq V(G)$, it holds that

$\textup{{OPT}}_{\Pi}(G-S)\leq\textup{{OPT}}_{\Pi}(G)\leq\textup{{OPT}}_{\Pi}(G-S)+|S|.$

###### Proof.

Let $T\subseteq V(G)$ (resp. $T^{\prime}\subseteq V(G)\setminus S$) be an
optimal solution to $\Pi$ on $G$ (resp. $G-S$). Let
$T^{\prime\prime}=T\cap(V(G)\setminus S)$, and note that
$G^{\prime\prime}\coloneqq(G-S)-T^{\prime\prime}$ is an induced subgraph of
$G-T\in\mathcal{F}$. Since $\mathcal{F}$ is hereditary,
$G^{\prime\prime}\in\mathcal{F}$, which implies that $T^{\prime\prime}$ is a
solution to $\Pi$ on $G^{\prime\prime}$. Then,
$\textup{{OPT}}_{\Pi}(G-S)=|T^{\prime}|\leq|T^{\prime\prime}|\leq|T|=\textup{{OPT}}_{\Pi}(G)$,
the first inequality follows.

For the second inequality, note that $(G-S)-T^{\prime}\in\mathcal{F}\iff
G-(S\cup T^{\prime})\in\mathcal{F}$. That is, $S\cup T^{\prime}$ is a feasible
solution to $\Pi$ on $G$. Thus, $\textup{{OPT}}_{\Pi}(G)\leq|S\cup
T^{\prime}|=|S|+|T^{\prime}|\leq|S|+\textup{{OPT}}_{\Pi}(G-S)$. ∎

######  Definition 4 (Self-reducibility).

Let $\Pi$ be a decision problem on graphs, and let $\mathcal{A}$ be an
algorithm for $\Pi$. We say that $\Pi$ is _self-reducible_ if, there exists an
algorithm $\mathcal{A}^{\prime}$, that makes at most polynomially many calls
to $\mathcal{A}^{\prime}$, and at most a polynomial overhead, and has the
following behavior. Given a no-instance of $\Pi$, $\mathcal{A}^{\prime}$
correctly concludes that it is a no-instance; otherwise, given a yes-instance
of $\Pi$, it outputs a “solution” witnessing the yes-instance.

The preceding definition is imprecise, since the notion of “solution” is not
formally defined. However, for all the problems that we will consider in this
paper, the notion of solution will be obvious. For example, the decision
version of Vertex Cover (resp. Independent Set) takes input a pair $(G,k)$,
and asks whether there exists a vertex cover (independent set) of size at most
(at least) $k$. Here, the solution is naturally a vertex cover (independent
set) of the prescribed size.

######  Lemma 1.

For any fixed family $\mathcal{F}\subseteq\mathcal{G}$, the problem Vertex
Deletion to  $\mathcal{F}$ is self-reducible.

###### Proof.

Consider the input $(G,k)$ to $\mathcal{A}^{\prime}$. We first call
$\mathcal{A}$ on the instance $\mathcal{I}=(G,k)$, which takes time $T$. If
$\mathcal{A}$ reports that $\mathcal{I}$ is a no-instance of Vertex Deletion
to  $\mathcal{F}$ , then so does $\mathcal{A}^{\prime}$. Otherwise, assume
that $\mathcal{I}$ is a yes-instance. Thus, there exists $S\subseteq V(G)$ of
size at most $k$ such that $G-S\in\mathcal{F}$. For any $v\in V(G)$, define an
instance $\mathcal{I}_{v}\coloneqq(G-v,k-1)$.

For any $v\in S$, observe that the graph
$(G-v)-(S\setminus\\{v\\})=G-S\in\mathcal{F}$. Therefore, for any $v\in S$,
$\mathcal{I}_{v}$ is a yes-instance. Furthermore, consider a $w\in V(G)$ such
that $\mathcal{I}_{w}$ is a yes-instance. Then, there exists a subset
$S^{\prime}\subseteq V(G)\setminus\\{w\\}$ of size at most $k-1$ such that
$(G-w)-S^{\prime}\in\mathcal{H}\implies
G-(S^{\prime}\cup\\{w\\})\in\mathcal{F}$. Thus, $S^{\prime}\cup\\{w\\}$ is a
solution of size at most $k$.

So $\mathcal{A}^{\prime}$ iterates over the vertices $v\in V(G)$, and use the
algorithm $\mathcal{A}$ to decide the instance $\mathcal{I}_{v}$. The first
time $\mathcal{A}$ reports that $\mathcal{I}_{v}$ is a yes-instance, we add
$v$ to our solution, and continue the procedure on the graph obtained by
deleting $v$ from the current graph, and reducing $k$ by $1$. We stop when
either the graph becomes empty or $k$ becomes $0$. The correctness of the
algorithm follows from the previous claim. As for the running time,
$\mathcal{A}$ is called initially on $(G,k)$, and then at most once for each
instance $\mathcal{I}_{v}$ for each $v\in V(G)$. Accounting for the polynomial
time taken for deleting vertices and incident edges, the claimed running time
follows. ∎

###  3.2 FPT-ASes for Vertex Deletion to  $\mathcal{F}$ Parameterized by
$\mathbf{mod}_{\mathcal{H}}(\cdot)$

Let $\mathcal{H},\mathcal{F}$ be well-behaved families of graphs, such that
$\Pi=\textup{{Vertex}}\allowbreak\textup{{Deletion}}\allowbreak\textup{{ to
}}\allowbreak\text{$\mathcal{F}$}$ admits an EPTAS for (the optimization
variant of) $\Pi$ on any $G\in\mathcal{H}$. Then, we show how to design an
FPT-AS for $\Pi$ parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$, and
$\epsilon$. Note that, for a graph $G$, when
$p\coloneqq\mathbf{mod}_{\mathcal{H}}(G)=0$, the graph already belongs to
$\mathcal{H}$, and in this case our algorithm is essentially an EPTAS. In this
sense, we generalize the assumed EPTAS on $\mathcal{H}$ to a larger family of
graphs that are at most $p$ vertices away from $\mathcal{H}$.

Let $M\subseteq V(G)$ be a modulator to $\mathcal{H}$ of size $p$, i.e.,
$G-M=:F\in\mathcal{H}$. We first compute a $(1+\epsilon/2)$-approximate
solution $S$ for $F$ using EPTAS in time $g(\epsilon)\cdot
n^{\mathcal{O}(1)}$. Note that $S\subseteq V(G)\setminus M$, and
$p\leq(1+\epsilon/2)\cdot\textup{{OPT}}(F)\leq(1+\epsilon/2)\textup{{OPT}}(G)$,
where the last inequality follows from 1. Depending on the relative sizes of
$M$, and the approximate solution $S$, we consider the following two cases.

  1. 1.

$p\leq\frac{\epsilon}{3}\cdot|S|$.
Then we simply return $X\cup S$ as a solution for $G$. Note that
$|M|+|S|\leq(1+\epsilon/3)(1+\epsilon/2)\cdot\textup{{OPT}}(F)\leq(1+\epsilon)\cdot\textup{{OPT}}(F)\leq(1+\epsilon)\cdot\textup{{OPT}}(G)$.

  2. 2.

$p>\frac{\epsilon}{3}\cdot|S|$, i.e,
$\textup{{OPT}}(F)\leq|S|\leq\frac{3p}{\epsilon}$.
Then, by 1, $\textup{{OPT}}(G)\leq\textup{{OPT}}(F)+|M|\leq
p+\frac{3p}{\epsilon}=:p^{\prime}$. In this case, we use an FPT algorithm
parameterized by the solution size, to find an optimal solution for $G$. Note
that this takes $h(p^{\prime})\cdot n^{\mathcal{O}(1)}$, i.e.,
$f(p,\epsilon)\cdot n^{\mathcal{O}(1)}$ time, where
$f(p,\epsilon)=h(p+3p/\epsilon)$.

Thus, we get the following theorem.

######  Theorem 2.

Let $\mathcal{F},\mathcal{H}$ be well-behaved families of graphs. Moreover,
suppose that
$\Pi=\textup{{Vertex}}\allowbreak\textup{{Deletion}}\allowbreak\textup{{ to
}}\allowbreak\text{$\mathcal{F}$}$ admits an EPTAS on any graph in
$\mathcal{H}$, and that $\Pi$ is FPT parameterized by the solution size. Then,
there exists an FPT-AS for $\Pi$, parameterized by
$p\coloneqq\mathbf{mod}_{\mathcal{H}}(G)$ with running time
$\max\\{g(\epsilon),f(p,\epsilon)\\}\cdot n^{\mathcal{O}(1)}$.

Corollaries. Let $\Pi$ be either Vertex Cover or Feedback Vertex Set. Note
that $\Pi$ is Vertex Deletion to  $\mathcal{F}$ , where $\mathcal{F}$ is
family of isolated vertices, and forests, respectively. If $\mathcal{H}$ is a
family of apex-minor free graphs, then $\Pi$ admits an EPTAS on $\mathcal{H}$
with running time $2^{\mathcal{O}(1/\epsilon)}\cdot n^{\mathcal{O}(1)}$ ([11],
Corollary 2). Furthermore, $\Pi$ is FPT parameterized by solution size on
general graphs, with running time $2^{\mathcal{O}(k)}\cdot
n^{\mathcal{O}(1)}$, where $k$ denotes the solution size. Therefore, we get an
FPT-AS parameterized by $p\coloneqq\mathbf{mod}_{\mathcal{H}}(G)$ with running
time $2^{\mathcal{O}(p/\epsilon)}\cdot n^{\mathcal{O}(1)}$ for Vertex Cover
and Feedback Vertex Set.

We note that it is possible to improve the running time of FPT-AS for Vertex
Cover using an even simpler algorithm – we simply guess the intersection of an
optimal solution with $X$ by iterating over all subsets of $X$. Let
$Y\subseteq X$ be a guess. If $Y$ is feasible, then it must be that
$U\coloneqq X\setminus Y$ must be an independent set, and $M\coloneqq
N(U)\cap(V(G)\setminus X)$ must belong to the solution. Thus, the remaining
graph is $G\setminus(M\cup X)$, which belongs to the family $\mathcal{H}$.
Then, we use the $2^{\mathcal{O}(1/\epsilon)}\cdot n^{\mathcal{O}(1)}$ time
EPTAS on $\mathcal{H}$ to obtain a solution $S$ and return the smallest
possible solution of the form $Y\cup M\cup S$. Thus, we get a
$2^{\mathcal{O}(\mathbf{mod}_{\mathcal{H}}(G)+1/\epsilon)}\cdot
n^{\mathcal{O}(1)}$ time FPT-AS.

######  Corollary 1.

There exists an FPT-AS for Vertex Cover (resp. Feedback Vertex Set) that runs
in time $2^{\mathcal{O}(p+\frac{1}{\epsilon})}\cdot n^{\mathcal{O}(1)}$ (resp.
$2^{\mathcal{O}(p/\epsilon)}\cdot n^{\mathcal{O}(1)}$), where
$p=\mathbf{mod}_{\mathcal{H}}(G)$, and $\mathcal{H}$ is a family of apex-minor
free graphs.

More generally, this result extends for Planar $\mathcal{R}$-Deletion, which
is a special case of VertexDeletion to $\mathcal{F}$, where the family
$\mathcal{F}$ is characterized by a set $\mathcal{R}$ of forbidden minors
containing at least one planar graph. We note that Fomin et al. [11] give an
EPTAS for this problem on $H$-minor free graphs. On the other hand, this
problem is known to admit a single-exponential FPT algorithm parameterized by
the solution size via the results from Fomin et al. [10]. Thus, we get the
following corollary.

######  Corollary 2.

There exists an FPT-AS for Planar $\mathcal{R}$-Deletion, that runs in time
$f(p,\epsilon)\cdot n^{\mathcal{O}(1)}$, where
$p=\mathbf{mod}_{\mathcal{H}}(G)$, and $\mathcal{H}$ is a family of $H$-minor
free graphs, for some fixed graph $H$ and some computable function $f$. In
particular, this implies an FPT-AS for Treewidth-$\eta$-Modulator.333For a
fixed $\eta\geq 0$, Treewidth-$\eta$-Modulator is the problem of deciding
whether one can delete at most $k$ vertices from a given graph $G$, such that
the resulting graph has treewidth at most $\eta$.

Finally, we mention Odd Cycle Transversal. Note that there exists a polynomial
time $\frac{9}{4}$-approximation for Odd Cycle Transversal on planar graphs
[16], and there exists a $3^{k}n^{\mathcal{O}(1)}$ time algorithm for the
problem parameterized by the solution size [25]. Thus, by using the
$9/4$-approximation instead of an $(1+\epsilon/2)$-approximation on $G-X$,
followed by a similar case analysis, we get the following result.

######  Corollary 3.

There exists an algorithm that runs in time $2^{\mathcal{O}(p/\epsilon)}\cdot
n^{\mathcal{O}(1)}$, where $p$ is the size of planar vertex deletion set, to
compute a $(\frac{9}{4}+\epsilon)$-approximation for Odd Cycle Transversal.

###  3.3 Equivalence Theorem

In this section we “extend” the result of Theorem 2 “using Theorem 2”. In
particular, we get the following equivalent statement.

See 1

###### Proof.

To prove that the three items are equivalent, we first note that for any graph
$G$ and any well-behaved family $\mathcal{H}$, it holds that
$\mathbf{mod}_{\mathcal{H}}(G)\geq\mathbf{ed}_{\mathcal{H}}(G)\geq\mathbf{tw}_{\mathcal{H}}(G)$.
Therefore, $3\implies 2\implies 1$. Thus, we focus on proving $1\implies 3$.
Let $\mathcal{P}_{\mathbf{mod}}$ denote the assumed FPT-AS for $\Pi$
parameterized by $\mathbf{mod}_{\mathcal{H}}$ and $\epsilon$. That is, for any
graph $G$ on $n$ vertices, $\mathcal{P}_{\mathbf{mod}}$ runs in time
$f(\mathbf{mod}_{\mathcal{H}}(G),\epsilon)\cdot n^{\mathcal{O}(1)}$, and
returns a subset $S\subseteq V(G)$ such that (i) $G-S\in\mathcal{F}$, and (ii)
$|S|\leq(1+\epsilon)\cdot\textup{{OPT}}_{\Pi}(G)$. 444Note that
$\mathcal{P}_{\mathbf{mod}}$ may in fact be a family of approximation
algorithms, containing an algorithm for each value of
$\mathbf{mod}_{\mathcal{H}}(\cdot)$ and $\epsilon$. We slightly abuse the
notation and assume that we use an appropriate algorithm from this family,
based on the value of $\mathbf{mod}_{\mathcal{H}}$ of the relevant graph, and
$\epsilon$..

Let $G=(V,E)$ be a graph, and let $(T,\chi,L)$ be the given $\mathcal{H}$-tree
decomposition of $G$ of width at most $\mathbf{tw}_{\mathcal{H}}(G)$, and let
$\ell\coloneqq\mathbf{tw}_{\mathcal{H}}(G)$ (resp.
$\ell\coloneqq\mathbf{ed}_{\mathcal{H}}(G)$). Recall that
$\mathcal{P}_{\mathbf{mod}}$ returns a $(1+\epsilon)$-approximation to $\Pi$
on any instance $(G,k)$ of $\Pi$.

For every leaf node $t\in V(T)$, let $V_{t}\coloneqq\chi(t)$, and let
$H_{t}=V_{t}\cap L$ and $R_{t}=V_{t}\setminus L$. The properties of
$\mathcal{H}$-tree decomposition imply that $G[H_{t}]\in\mathcal{H}$, and
$|R_{t}|\leq\ell$. Equivalently, $R_{t}\subseteq V(G)\setminus L$ is a
modulator to $\mathcal{H}$ for the graph $G[\chi(t)]$. Note that the base
vertices, i.e., the vertices in $L$, are partitioned across the leaf bags,
which implies that the graphs $\\{G[H_{t}]\\}_{\text{leaf\ }t\in V(T)}$ are
disjoint.

We iterate over every leaf nodes $t\in V(T)$, and proceed as follows. Note
that $G[H_{t}]\in\mathcal{H}$, thus $G[H_{t}]$ has a modulator of size zero to
the family $\mathcal{H}$. Therefore, we can use $\mathcal{P}_{\mathbf{mod}}$
to obtain a set $S_{t}\subseteq H_{t}$ that is a
$(1+\epsilon/2)$-approximation for $\Pi$ on the graph $G[H_{t}]$, i.e.,
$|S_{t}|\leq(1+\epsilon/2)\cdot\textup{{OPT}}(G[H_{t}])$. This takes
$f(0,\epsilon/2)\cdot|H_{t}|^{\mathcal{O}(1)}\leq h(\epsilon)\cdot
n^{\mathcal{O}(1)}$ time for some function $h(\cdot)$. In other words,
$\mathcal{P}_{\mathbf{mod}}$ is an EPTAS for $\Pi$ on $G[H_{t}]$.

For every leaf node $t\in V(T)$, if $|R_{t}|\leq\epsilon/3\cdot|S_{t}|$, then
we say that the node is _good_. Otherwise, we say that $t\in V(T)$ is _bad_.
Furthermore, all non-leaf nodes are classified as _bad_. Note that for a good
node $t\in V(T)$,
$|R_{t}|\leq(1+\epsilon/2)\cdot(\epsilon/3)\cdot\textup{{OPT}}(G[H_{t}])\leq(\epsilon/2)\cdot\textup{{OPT}}(G[H_{t}])$.
On the other hand, for a bad node $t\in V(T)$,
$\ell\geq|R_{t}|\geq\epsilon/3\cdot|S_{t}|\geq\epsilon/3\cdot\textup{{OPT}}(G[H_{t}])$.
Let $U_{g}$ and $U_{b}$ denote the set of good and bad nodes, respectively.
Let $S_{1}=\bigcup_{t\in U_{g}}S_{t}$, and $S_{2}=\bigcup_{t\in U_{g}}R_{t}$.

Furthermore, let $V_{g}=\bigcup_{t\in U_{g}}\chi(t)$, and $V_{b}=V\setminus
V_{g}$. Now, let $S_{b}\subseteq V_{b}$ denote an $(1+\epsilon)$-approximate
solution to $\Pi$ on the graph $G[V_{b}]$. We first state the following lemma,
whose proof is given after the current proof.

######  Lemma 2.

$|S|\leq(1+\epsilon)\cdot\textup{{OPT}}(G)$, where $S=S_{1}\cup S_{2}\cup
S_{b}$ as defined above.

Let $F=G[V_{b}]$. From the $\mathcal{H}$-tree decomposition $(T,\chi,L)$ of
$G$ of width $\ell$, it is possible to obtain an $\mathcal{H}$-tree
decomposition of $F$ of width at most $\ell$, by deleting the vertices of
$V_{g}$ from every bag. For simplicity, we will continue to use $(T,\chi,L)$
for the new “projected” $\mathcal{H}$-tree decomposition of $F$. As suggested
by Lemma 2, we need to find a set $S_{b}$, which is a
$(1+\epsilon)$-approximation to $\Pi$ on $F\coloneqq G[V_{b}]$. In fact, we
will show how to find an optimal solution. To this end, we prove the following
technical lemma.

######  Lemma 3.

Let $\mathcal{H},\mathcal{F}$ be well-behaved families of graphs, such that
$\Pi=\textup{{Vertex}}\allowbreak\textup{{Deletion}}\allowbreak\textup{{ to
}}\allowbreak\text{$\mathcal{F}$}$ is CMSO-definable, and has FII.
Furthermore, suppose there exists an FPT-AS $\mathcal{P}_{\mathbf{mod}}$ for
$\Pi$, parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$ and $\epsilon$.
Then, for every positive integer $\ell$, there exists an algorithm
$\mathcal{A}_{\ell}$, that takes input $(G,T,\chi,L)$, where

  1. 1.

$G$ is a graph on at most $n$ vertices, and

  2. 2.

A $\mathcal{H}$-tree decomposition $(T,\chi,L)$ of $G$ of width $\ell$, such
that:
$\mathbf{\star}$ for every leaf $t\in V(T)$, the graph $H_{t}\coloneqq
G[\chi(t)\cap L]$ satisfies $\textup{{OPT}}_{\Pi}(H_{t})\leq 3\ell/\epsilon$.

The algorithm $\mathcal{A}_{\ell}$ runs in time $g(\ell,\epsilon)\cdot
n^{\mathcal{O}(1)}$, where $g$ is some function, and returns an optimal
solution $S\subseteq V(G)$ to $\Pi$ on $G$, i.e.,
$|S|=\textup{{OPT}}_{\Pi}(G)$, and $G-S\in\mathcal{F}$.

The idea of the proof of Lemma 3 is similar to that of Theorem 6.1 from [1].
However, they require that $\mathcal{P}_{\mathbf{mod}}$ be an _exact
algorithm_ for $\Pi$. Our main contribution is to observe that, when the input
graph satisfies the property $\star$, an _approximation algorithm_ can be made
to behave like an exact algorithm by a suitable choice of $\epsilon$. However,
a formal proof requires several technical definitions pertaining to FII, and
thus, we defer the formal proof to Section A.4 wherein we first give all the
necessary background.

Now we finish the proof of Theorem 1. Note that the graph $G[V_{b}]$ and the
$\mathcal{H}$-tree decomposition $(T,\chi,L)$ restricted to $G[V_{b}]$
satisfies the requirements of Lemma 3 by construction. Thus, using the
algorithm from Lemma 3, we can, in fact, get an optimal solution
$S_{b}\subseteq V_{b}$ to $\Pi$ on $G[V_{b}]$. This concludes the proof of
Theorem 1, modulo the proof of Lemma 2.

∎

###### Proof of Lemma 2.

Recall the definitions of the partial solutions $S_{1},S_{2},S_{b}$ as defined
in the proof of Theorem 1. From 1, we have the following inequality.

$\textup{{OPT}}(G-S_{2})\leq\textup{{OPT}}(G)$ (1)

Note that the properties of $\mathcal{H}$-tree decomposition imply that, if we
delete $S_{2}$ from $G$, the graph $G-S_{2}$ consists of disjoint induced
subgraphs $H_{t}$ for $t\in U_{g}$, as well as $G[V_{b}]$ (note that each of
these induced subgraphs may or may not be connected).

$\displaystyle|S|$ $\displaystyle=|S_{1}|+|S_{2}|+|S_{b}|$ (Since
$S=S_{1}\uplus S_{2}\uplus S_{b}$.) $\displaystyle\leq\sum_{t\in
U_{g}}(|S_{t}|+|R_{t}|)+|S_{b}|$ (Since $S_{1}=\bigcup_{t\in U_{g}}S_{t}$ and
$S_{2}=\bigcup_{t\in U_{g}}R_{t}$) $\displaystyle\leq\left(\sum_{t\in
U_{g}}(1+\epsilon/2)\cdot\textup{{OPT}}(G[H_{t}])+\epsilon/2\cdot\textup{{OPT}}(G[H_{t}])\right)+(1+\epsilon)\cdot\textup{{OPT}}(G[V_{b}])$
(Using bounds on $S_{t},R_{t}$ and $S_{b}$ respectively)
$\displaystyle\leq(1+\epsilon)\cdot\left(\left(\sum_{t\in
U_{g}}\textup{{OPT}}(G[H_{t}])\right)+\textup{{OPT}}(G[V_{b}])\right)$
$\displaystyle\leq(1+\epsilon)\cdot\textup{{OPT}}(G)$ (since $\displaystyle
V(G)\setminus S_{2}=V_{b}\uplus\biguplus_{t\in U_{g}}H_{t}$, and (1))

∎

###  3.4 Variations of the Equivalence Theorem

Theorem 1 gives non-uniform FPT-ASes. In the following, we obtain a simpler,
and _explicit_ version of Theorem 1 for Vertex Deletion to  $\mathcal{F}$ when
$\mathcal{F}$ satisfies the following property, called _treewidth-
$\eta$-modulated_: Suppose there exists a constant $\eta$, such that the
(standard) treewidth of every graph in $\mathcal{F}$ is bounded by $\eta$. In
this case, we say that the family $\mathcal{F}$ is _treewidth-
$\eta$-modulated_, or simply, _$\eta$ -modulated_. Note that many natural
Vertex Deletion to  $\mathcal{F}$ problems are $\eta$-modulated. For example,
Vertex Cover (resp. Feedback Vertex Set) is $\eta$-modulated for $\eta=0$
(resp. $\eta=1$). More generally, it is also known if the family $\mathcal{F}$
is characterized by a family of excluded minors $\mathcal{O}$ containing at
least one planar graph, then Vertex Deletion to  $\mathcal{F}$ is known as
Planar $\mathcal{O}$-Deletion, and is also $\eta$-modulated for some $\eta$
that depends on $\mathcal{O}$.

######  Theorem 3.

Let $\mathcal{H},\mathcal{F}$ be well-behaved families of graphs, and let
$\Pi=\textup{{Vertex}}\allowbreak\textup{{Deletion}}\allowbreak\textup{{ to
}}\allowbreak\text{$\mathcal{F}$}$ such that: (i) $\mathcal{F}$ is
$\eta$-modulated for some constant $\eta\geq 0$, and (ii) there exists an
exact FPT algorithm for $\Pi$ parameterized by $\mathbf{tw}(\cdot)$. Then, the
following statements are equivalent.

  1. 1.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$
and $\epsilon$.

  2. 2.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{ed}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

  3. 3.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{tw}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

###### Proof.

We proceed exactly as in the proof of Theorem 1, and classify each node $t\in
V(T)$ in the $\mathcal{H}$-tree decomposition $(T,\chi,L)$ of $G$ into _good_
and _bad_ , respectively. We use the same notation as in the previous proof.

For every good node $t\in V(T)$, we add an $(1+\epsilon/2)$-approximate
solution $S_{t}$ as well as $R_{t}$ in the solution. Now we discuss how to
find an optimal solution $S_{b}$ for the graph $G[V_{b}]$. For each bad node
$t\in V(T)$, note that $|R_{t}|>\epsilon/3\cdot|S_{t}|$, which implies that
$|S_{t}|\leq 3\ell/\epsilon$. Since $S_{t}$ is a solution to $\Pi$ on
$G[H_{t}]$, $G[H_{t}]-S_{t}\in\mathcal{F}$, which implies that
$\mathbf{tw}(G[H_{t}]-S_{t})\leq\eta$. Therefore,
$\mathbf{tw}(G[H_{t}])\leq\eta+|S_{t}|\leq 3\ell/\epsilon+\eta$. This implies
that $\mathbf{tw}(G[V_{b}])\leq\ell+3\ell/\epsilon+\eta$. Furthermore, the
given $\mathcal{H}$-tree decomposition $(T,\chi,L)$ of $G[V_{b}]$ can be
transformed into the (standard) tree decomposition of width at most
$\ell+3\ell/\epsilon+\eta$. Then, by using the FPT algorithm for $\Pi$
parameterized by $\mathbf{tw}(G[V_{b}])$, the theorem follows. ∎

Note that Theorem 3 requires that $\Pi$ admit an FPT-AS parameterized by
$\mathbf{mod}_{\mathcal{H}}(G)$. In particular, when
$\mathbf{mod}_{\mathcal{H}}(G)=0\iff G\in\mathcal{H}$, $\Pi$ should have an
EPTAS. However, in some cases, we only know an $\alpha$-approximation for
$\Pi$ even when $G\in\mathcal{H}$, where $\alpha\geq 1$. In such cases, the
following theorem may be applicable, if $\Pi$ is also known to be FPT
parameterized by the size of the solution.

######  Theorem 4.

Let $\mathcal{H},\mathcal{F}$ be well-behaved families of graphs, such that
$\Pi=\textup{{Vertex}}\allowbreak\textup{{Deletion}}\allowbreak\textup{{ to
}}\allowbreak\text{$\mathcal{F}$}$ satisfies the following properties: (i)
$\Pi$ is CMSO-definable, (ii) has FII, and (iii) $\Pi$ is FPT parameterized by
the size of the solution. Also, suppose that for some constant $\alpha\geq 1$,
$\Pi$ admits an $\alpha$-approximation in time
$f(\mathbf{mod}_{\mathcal{H}}(\cdot))\cdot n^{\mathcal{O}(1)}$. Then,

  1. 1.

$\Pi$ admits an $(\alpha+\epsilon)$-approximation in time
$g(\mathbf{ed}_{\mathcal{H}}(\cdot),\epsilon)\cdot n^{\mathcal{O}(1)}$, and

  2. 2.

$\Pi$ admits an $(\alpha+\epsilon)$-approximation in time
$h(\mathbf{tw}_{\mathcal{H}}(\cdot),\epsilon)\cdot n^{\mathcal{O}(1)}$.

###### Proof Sketch.

The proof of the theorem follows essentially follows the same structure as
that of Theorem 1, line-by-line. We only highlight the important differences.
First, we use the $\alpha$-approximation on each $G[H_{t}]$ to obtain a set
$S_{t}\subseteq H_{t}$ such that
$|S_{t}|\leq\alpha\cdot\textup{{OPT}}(G[H_{t}])$, for each node $t\in V(T)$ in
the $\mathcal{H}$-tree decomposition $(T,\chi,L)$. Then, a node is said to be
_good_ if
$|S_{t}|\leq(\epsilon/2\alpha)\cdot|S_{t}|\leq\epsilon/2\cdot\textup{{OPT}}(G[H_{t}])$.
Otherwise, if $|S_{t}|>\epsilon/(2\alpha)\cdot\textup{{OPT}}(G[H_{t}])$, then
$t$ is bad.

We follow the same notation as in the proof of Theorem 1, and let
$S_{1}=\bigcup_{t\in U_{g}}S_{t},S_{2}=\bigcup_{t\in U_{g}}R_{t}$, and $S_{b}$
be an $(1+\epsilon)$-approximation to $\Pi$ on $G[V_{b}]$. Then, we obtain an
analogous version of Lemma 2 implies that
$|S|\leq(\alpha+\epsilon)\cdot\textup{{OPT}}(G)$, where $S=S_{1}\cup S_{2}\cup
S_{b}$. Thus, it suffices to obtain an $(1+\epsilon)$-approximation to $\Pi$
on $S_{b}$.

Now, we can use the FPT algorithm for $\Pi$ parameterized by the solution size
to prove an analogous version of Lemma 3 (this, in fact, almost exactly
matches Theorem 6.1 from [1]). Here, we use the fact that, when we perform a
replacement (i.e., application of Lemma 14) using the FII property of $\Pi$,
the size of the solution is upper bounded by
$\textup{{OPT}}(G[H_{t}])+c_{\mathbf{mod}_{\mathcal{H}}(G)}$, which is upper
bounded by a function of $\mathbf{tw}_{\mathcal{H}}(G)$ and $\epsilon$, where
$t$ is a _bad node_. Thus, in time
$h^{\prime}(\mathbf{tw}_{\mathcal{H}},\epsilon)\cdot n^{\mathcal{O}(1)}$, we
obtain an _exact solution_ $S_{b}$ to $\Pi$ on $G[V_{b}]$. Thus, overall, we
obtain an $(\alpha+\epsilon)$-approximation to $\Pi$ on $G$. ∎

Plugging in Corollary 3 into Theorem 4, we obtain the following corollary.

######  Corollary 4.

There exists an algorithm that runs in time $f(\ell,\epsilon)\cdot
n^{\mathcal{O}(1)}$, where $\ell$ is $\mathbf{ed}_{\mathcal{H}}(G)$ (or
$\mathbf{tw}_{\mathcal{H}}(G)$) to planar graphs, and computes a
$(\frac{9}{4}+\epsilon)$-approximation for Odd Cycle Transversal.

##  4 Packing Problems

In this section, we consider packing problems. First, we give preliminaries on
packing problems in Section 4.1. Then, in Section 4.2, we design FPT-ASes for
these packing problems, parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$.
Finally, in Section 4.3, we prove the equivalence theorems for these packing
problems, which extends these FPT-ASes, parameterized by
$\mathbf{ed}_{\mathcal{H}}(\cdot)$, and $\mathbf{tw}_{\mathcal{H}}(\cdot)$.

###  4.1 Preliminaries on Packing Problems

We consider the following three packing problems in this section.

Independent Set Input: An instance $(G,k)$, where $G=(V,E)$ is a graph, and
$k$ is a positive integer. Question: Does there exist a subset $S\subseteq
V(G)$ of size at least $k$ that is independent in $G$?

$\mathcal{F}$-Minor Packing ($\mathcal{F}$ is a fixed finite family of graphs)
Input: An instance $(G,k)$, where $G=(V,E)$ is a graph, and $k$ is a positive
integer. Question: Do there exist $k$ pairwise vertex-disjoint subgraphs
$H_{1},\ldots,H_{k}$ of $G$, such that each $H_{i}$ contains a graph from
$\mathcal{F}$ as a minor?

$\mathcal{S}$-Subgraph Packing ($\mathcal{S}$ is a fixed finite family of
graphs) Input: An instance $(G,k)$, where $G=(V,E)$ is a graph, and $k$ is a
positive integer. Question: Do there exist $k$ pairwise vertex-disjoint
subgraphs $H_{1},\ldots,H_{k}$ of $G$, such that each $H_{i}$ is isomorphic to
some graph in $\mathcal{S}$?

Throughout the section, we will assume the families $\mathcal{F}$ and
$\mathcal{S}$ in $\mathcal{F}$-Minor Packing and $\mathcal{S}$-Subgraph
Packing, are fixed finite families of connected graphs. First, we note that
Independent Set is self-reducible. This can be inferred from, e.g., the self-
reduicibility of Vertex Cover (Lemma 1). Now we prove the same for
$\mathcal{F}$-Minor Packing and $\mathcal{S}$-Subgraph Packing, under the mild
assumption that the graphs in $\mathcal{F}$ and $\mathcal{S}$ are connected
and non-empty. For this, we need some definitions.

######  Definition 5 (Minor Model).

$H$ is a minor of $G$ iff there exists a function $\varphi:V(G)\to
2^{V(G)}\setminus\\{\emptyset\\}$ such that for every $u\in V(H)$, (i)
$G[\varphi(u)]$ is connected, and (ii) for every $uv\in E(H)$, there exist
$u^{\prime}\in\varphi(u)$ and $v^{\prime}\in\varphi(v)$, such that
$u^{\prime}v^{\prime}\in E(G)$. Such a function $\varphi$ is called a _minor
model_ of $H$ in $G$.

######  Definition 6 (Graph Isomorphism).

The graphs $H$ and $G$ are said to be _isomorphic_ if there exists a bijection
$\varphi:V(H)\to V(G)$ such that for any $u,v\in V(H)$, $uv\in E(H)$ iff
$\varphi(u)\varphi(v)\in E(G)$.

######  Definition 7 (Solution to $\mathcal{F}$-Minor Packing).

Let $\mathcal{F}$ be a fixed finite family of connected graphs. Let $(G,k)$ be
a yes-instance of $\mathcal{F}$-Minor Packing. Then, a solution to $(G,k)$ is
given by
$\sigma=\left\\{(H_{1},F_{1},\varphi_{1}),(H_{2},F_{2},\varphi_{2}),\ldots,(H_{k},F_{k},\varphi_{k})\right\\}$,
with the following properties.

  * •

$H_{1},\ldots,H_{k}$ are pairwise vertex-disjoint subgraphs of $G$.

  * •

$F_{1},\ldots,F_{k}$ are (not necessarily distinct) graphs from $\mathcal{F}$.

  * •

For each $i\in[k]$, $\varphi_{i}$ is a minor model of $F_{i}$ in $H_{i}$.

We refer that each tuple $(H_{i},F_{i},\varphi_{i})$ as a _minor model tuple_.
The _size_ of the solution $\sigma$, is defined as the number of minor model
tuples in the solution, e.g., $\mathsf{size}(\sigma)\coloneqq k$ for $\sigma$
above. For a graph $G$, let $\textup{{OPT}}_{\Pi}(G)$ denote the maximum size
of a solution to $\Pi\coloneqq\textup{{$\mathcal{F}$-Minor Packing}}$. An
$\alpha$-approximation algorithm returns a solution of size at least
$\alpha\cdot\textup{{OPT}}(G)$ on any input graph $G$. These notions are
analogously defined for $\mathcal{S}$-Subgraph Packing, where we require
$\varphi_{i}$’s to be isomorphisms instead of minor models.

######  Lemma 4.

For any fixed finite family of connected graphs $\mathcal{F}$ (resp.
$\mathcal{S}$), $\mathcal{F}$-Minor Packing (resp. $\mathcal{S}$-Subgraph
Packing) is self-reducible. That is, given an algorithm for the decision
version, there exists an algorithm that produces a solution to an instance
$(G,k)$, or concludes that $(G,k)$ is a no-instance.

###### Proof.

We prove the theorem for $\mathcal{F}$-Minor Packing and then discuss the case
of $\mathcal{S}$-Subgraph Packing, which is only simpler. Let $\mathcal{A}$ be
an algorithm for the decision version of $\mathcal{F}$-Minor Packing, which we
denote by $\Pi$ for brevity.

Consider an input $(G,k)$. First, we run $\mathcal{A}$ on $(G,k)$, and if it
outputs that it is a no-instance, then we report the same. Otherwise, suppose
that $(G,k)$ is a yes-instance. Then, there exists a solution
$\left\\{(H_{i},F_{i},\varphi_{i})\right\\}_{i\in[k]}$. Let
$U\coloneqq\bigcup_{i\in[k]}V(H_{i})$, and let $F=\bigcup_{i\in[k]}E(H_{i})$.
We prove the following claim, which follows quite easily from the definitions
of a minor model and of a solution.

######  Observation 2.

Suppose that for some $u\in V(G)$, $(G-u,k)$ is a yes-instance. Then, any
solution for $(G-u,k)$ for $\Pi$ is a solution for $(G,k)$. Similarly, suppose
that for some $uv\in V(G)$, $(G-uv,k)$ is a yes-instance. Then, any solution
for $(G-uv,k)$ for $\Pi$ is a solution for $(G,k)$.

Let $G^{\prime}$ be a copy of $G$. We first iterate over each vertex $u\in
V(G^{\prime})$, and check whether $(G-u,k)$ is a yes-instance using
$\mathcal{A}$. If it is a yes-instance, then we redefine $G^{\prime}\leftarrow
G^{\prime}-u$, and proceed with the next iteration; otherwise we leave the
graph unchanged. Next, we do the same for each edge $uv\in E(G^{\prime})$,
i.e., check whether $(G^{\prime}-uv,k)$ is a yes-instance using $\mathcal{A}$,
and delete the edge from $G^{\prime}$ is that is the case. Note that we make
at most $|V(G)|+|E(G)|$ calls to $\mathcal{A}$. If $G^{\prime}$ denotes the
graph at the end of this procedure, then 2 implies that $(G^{\prime},k)$ is a
yes-instance of $\mathcal{F}$-Minor Packing.

Now, consider a solution
$\sigma=\\{(G^{\prime}_{i},F_{i},\varphi_{i})\\}_{i\in[k]}$ of $\Pi$ on
$G^{\prime}$. First, we have the following claim.

######  Claim 1.

For every $(G^{\prime}_{i},F_{i},\varphi_{i})\in\sigma$, there exists a unique
connected component $C$ of $G^{\prime}$ such that $V(G^{\prime}_{i})=C$.

###### Proof.

First we show that the number of connected components in $G^{\prime}$ is
exactly $k=|\sigma|$. Suppose $|\texttt{cc}(G^{\prime})|>k$, then there exists
a non-empty connected component $C\in\texttt{cc}(G)$ such that $C\cap
V(G^{\prime}_{i})=\emptyset$ for all $i\in[k]$. Then, for any $v\in C$,
$\sigma$ remains a solution for $(G-v,k)$, which contradicts the assumption on
$G^{\prime}$. Now, suppose $|\texttt{cc}(G^{\prime})|<k$. Then, by pigeonhole
principle, there exists a connected component $C$ such that $C\cap
V(G^{\prime}_{i})\neq\emptyset$ and $C\cap V(G^{\prime}_{j})\neq\emptyset$ for
two distinct $G^{\prime}_{i},G^{\prime}_{j}$. Thus, there exists a path
between vertices $u$ and $v$ in $(G^{\prime}[C])$ such that $u\in
V(G^{\prime}_{i})$ and $v\in V(G^{\prime}_{j})$. Now, there are two cases. If
there exists an edge $u^{\prime}v^{\prime}\in E(G^{\prime}[C])$ such that
$u^{\prime}\in V(G^{\prime}_{i})$ and $v^{\prime}\in V(G^{\prime}_{j})$, then
we observe that $\sigma$ is a solution for $(G-uv,k)$, which is a
contradiction. Otherwise, there is an edge $u^{\prime}v^{\prime}\in
E(G^{\prime}[C])$ such that $u^{\prime}\in V(G^{\prime}_{i})$, but
$v^{\prime}\not\in\bigcup_{j^{\prime}\in[k]}V(G^{\prime}_{j^{\prime}})$. This
is again a contradiction since $\sigma$ is a solution $(G-v^{\prime},k)$.
Thus, the number of connected components of $G^{\prime}$ is exactly
$k^{\prime}$, and each connected component contains exactly the vertices from
$V(G^{\prime}_{i})$ for some $i\in[k]$. ∎

Thus, consider a connected subgraph $G^{\prime}_{i}$ of $G^{\prime}$
corresponding to a minor model tuple $(G^{\prime}_{i},F_{i},\varphi_{i})$, and
an edge $uv\in E(G^{\prime}_{i})$. If $\varphi(u)=\varphi(v)$, then
$(G^{\prime}\backslash uv,k)$ is a yes-instance. Similarly, if for some
$u^{\prime}v^{\prime}\in E(G^{\prime}_{i})$, $(G^{\prime}\backslash uv,k)$ is
a yes-instance, then the solution for $(G^{\prime}\backslash uv,k)$ can be
translated into a solution for $(G^{\prime},k)$. Therefore, we iterate over
the edges of $G^{\prime}_{i}$, and use $\mathcal{A}$ to decide the instance
$(G^{\prime}\backslash uv,k)$. If it returns yes, we contract the edge and
proceed to the next iteration. We stop when none of the edges can be
contracted. It follows that the resulting graph is isomorphic to some
$F_{i}\in\mathcal{F}$. By iterating over all connected components, we obtain a
solution of size $k$, which can be translated into a solution for $G$. ∎

###  4.2 FPT-ASes for Packing Problems Parameterized by
$\mathbf{mod}_{\mathcal{H}}$

Here, we show that a natural variant of the bucket versus ocean also yields
FPT-ASes for packing problems such as Independent Set and Cycle Packing. Let
$\mathcal{H}$ be an apex-minor closed family. We are given a graph $G=(V,E)$,
and a set $M\subseteq V(G)$ of size at most $p$ such that
$G^{\prime}=G\setminus M\in\mathcal{H}$, Let $H=V(G)\setminus M$.

Independent Set. By iterating over all subsets of $M$, we guess the
intersection of an optimal independent set $I$ with $M$. Consider the
iteration corresponding to $Y=I\cap M$. Then, let $R=N(Y)\cap H$. We compute a
$(1-\epsilon)$-approximation $I^{\prime}$ to the maximum independent set in
the graph $G^{\prime}\setminus R$, using an $2^{\mathcal{O}(1/\epsilon)}\cdot
n^{\mathcal{O}(1)}$ time algorithm from Fomin et al. [11]. It follows that
$|Y|+|I^{\prime}|\geq|Y|+(1-\epsilon)\cdot|I\setminus
Y|\geq(1-\epsilon)\cdot|I|=\textup{{OPT}}(G)$. Thus, we get the following
result.

######  Theorem 5.

Let $\mathcal{H}$ be an apex-minor free graph family. Then, there exists an
FPT-AS for Independent Set parameterized by
$\mathbf{mod}_{\mathcal{H}}(\cdot)$ that runs in time
$2^{\mathcal{O}(\mathbf{mod}_{\mathcal{H}}(G)+1/\epsilon)}\cdot
n^{\mathcal{O}(1)}$.

Cycle Packing. We compute an $(1-\epsilon/2)$-approximate solution $S$ to
cycle packing on the graph $G^{\prime}$ in time $f(\epsilon)\cdot
n^{\mathcal{O}(1)}$. Note that Cycle Packing is a special case of
$\mathcal{F}$-Minor Packing, where $\mathcal{F}$ contains a single graph
$C_{3}$ (i.e., a cycle on $3$ vertices). We begin by stating the following two
inequalities.

$\displaystyle\textup{{OPT}}(G)\geq\textup{{OPT}}(G^{\prime})\geq|S|\geq(1-\frac{\epsilon}{2})\cdot\textup{{OPT}}(G^{\prime})$
(2)
$\displaystyle\textup{{OPT}}(G^{\prime})+|M|\geq\textup{{OPT}}(G)\geq\textup{{OPT}}(G^{\prime})$
(3)

This follows from the fact that any solution to Cycle Packing on $G^{\prime}$
is also a solution to $G$. On the other hand, $G^{\prime}=G\setminus X$. Now
consider a set $S^{*}$ of disjoint cycles in $G$. Note that at most $|M|$
cycles are incident to a vertex of $X$. Therefore, it is possible to obtain a
set $\tilde{S}^{*}$ of disjoint cycles in $G^{\prime}$ of size at least
$|S^{*}|-|M|$. Now, consider two cases.

Case 1. If $|M|\leq\frac{\epsilon}{2}\cdot|S|$. We have the following lemma.

######  Claim 2.

If $|M|\leq\frac{\epsilon}{2}\cdot|S|$, then
$|S|\geq(1-\epsilon)\textup{{OPT}}(G)$.

###### Proof.

Now, consider:

$\displaystyle|S|\geq(1-\frac{\epsilon}{2})\textup{{OPT}}(G^{\prime})$
$\displaystyle\geq(1-\frac{\epsilon}{2})\cdot\left(\textup{{OPT}}(G)-|M|\right)$
(From (3))
$\displaystyle\geq(1-\frac{\epsilon}{2})\cdot\textup{{OPT}}(G)-(1-\frac{\epsilon}{2})\cdot\frac{\epsilon}{2}|S|$
(Since $|M|\leq\frac{\epsilon}{2}|S|$)
$\displaystyle\geq(1-\frac{\epsilon}{2})\cdot\textup{{OPT}}(G)-\frac{\epsilon}{2}\cdot\textup{{OPT}}(G)$
(From (2)) $\displaystyle=(1-\epsilon)\cdot\textup{{OPT}}(G)$

∎

Case 2. $|M|\geq\frac{\epsilon}{2}|S|$. Then,

######  Lemma 5.

If $|M|\geq\frac{\epsilon}{2}|S|$, then
$\textup{{OPT}}(G)\leq\left(1+\frac{4}{\epsilon}\right)p$.

###### Proof.

Note that
$|M|\geq\frac{\epsilon}{2}\cdot|S|\geq(1-\frac{\epsilon}{2})\cdot\frac{\epsilon}{2}\cdot\textup{{OPT}}(G^{\prime})\geq\frac{\epsilon}{4}\textup{{OPT}}(G^{\prime})$,
where the second-last inequality follows from (2). In other words,
$\textup{{OPT}}(G^{\prime})\leq\frac{4}{\epsilon}|M|$. Now, consider

$\displaystyle\textup{{OPT}}(G)\leq\textup{{OPT}}(G^{\prime})+|M|\leq\left(1+\frac{4}{\epsilon}\right)|M|=\left(1+\frac{4}{\epsilon}\right)p.$

∎

In this case, we can use an algorithm for Cycle Packing parameterized by the
solution size that runs in time $2^{\mathcal{O}(\frac{k\log^{2}k}{\log\log
k})}\cdot n^{\mathcal{O}(1)}$ time [21]. Therefore, we obtain the following
result.

######  Corollary 5.

Let $\mathcal{H}$ be a family of apex-minor of graphs. Then, there exists an
FPT-AS for Cycle Packing that runs in time
$2^{\tilde{\mathcal{O}}({\mathbf{mod}_{\mathcal{H}}(G)/\epsilon})}\cdot
n^{\mathcal{O}(1)}$.

###  4.3 Equivalence Theorems for Packing Problems

First we prove an equivalence theorem for Independent Set (Theorem 12), and
then proceed to proving a similar theorem for $\mathcal{F}$-Minor Packing and
$\mathcal{S}$-Subgraph Packing (Theorem 7), whose proof is technically more
involved.

####  4.3.1 Independent Set

######  Theorem 6.

Let $\mathcal{H}$ be a well-behaved family of graphs, and let
$\Pi=\textup{{Independent Set}}$. Then, the following statements are
equivalent.

  1. 1.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$
and $\epsilon$.

  2. 2.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{ed}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

  3. 3.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{tw}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

###### Proof.

The overall structure of the proof follows the same outline as the proof of
Theorem 1, so we only discuss the modifications required. As before, it
suffices to prove $1\implies 3$. We also omit the subscript $\Pi$ from
$\textup{{OPT}}_{\Pi}(\cdot)$. Let $\mathcal{P}_{\mathbf{mod}}$ denote the
supposed FPT-AS for $\Pi$.

Let $G=(V,E)$ be a graph, and let $(T,\chi,L)$ be the given $\mathcal{H}$-tree
decomposition of width $\ell-1$. For each node $t\in V(T)$, let
$\chi(t)=H_{t}\uplus R_{t}$, where $H_{t}\subseteq L$ with
$G[H_{t}]\in\mathcal{H}$, and $|R_{t}|\leq\ell$. By iterating over each leaf
node $t\in V(T)$, we classify as _good_ or _bad_ , as follows. We use
$\mathcal{P}_{\mathbf{mod}}$ on $G[H_{t}]$ to obtain an independent set
$S_{t}\subseteq H_{t}$ such that
$|S_{t}|\geq(1-\epsilon/2)\cdot\textup{{OPT}}(G[H_{t}])$, which takes
$f(0,\epsilon/2)\cdot|H_{t}|^{\mathcal{O}(1)}=h(\epsilon)\cdot
n^{\mathcal{O}(1)}$ time. Now, if $|R_{t}|\leq\epsilon/2\cdot|S_{t}|$, then we
say that the leaf node $t$ is _good_ ; otherwise we say that $t$ is _bad_.
Furthermore, all internal nodes are classified as bad. Let $U_{g},U_{b}$
denote the sets of good and bad nodes respectively, and let
$S_{1}=\bigcup_{t\in U_{g}}S_{t}$. Finally, let $V_{g}=\bigcup_{t\in
U_{g}}\chi(t)$ and $V_{b}=V\setminus V_{g}$. Let $S_{b}\subseteq V_{b}$ denote
an $(1-\epsilon)$-approximate solution to $\Pi$ on $G[V_{b}]$. We prove the
following lemma.

######  Lemma 6.

$|S|\geq(1-\epsilon)\cdot\textup{{OPT}}(G)$, where $S\coloneqq S_{1}\cup
S_{b}$, as defined above.

###### Proof.

Let $S^{*}\subseteq V(G)$ denote a maximum-size independent set. Let
$S^{*}_{1}\coloneqq S^{*}\cap\bigcup_{t\in U_{g}}H_{t}$, $S^{*}_{2}\coloneqq
S^{*}\cap\bigcup_{t\in U_{g}}R_{t}$, and $S^{*}_{b}\coloneqq S^{*}\cap V_{b}$.
Note that $\\{S^{*}_{1},S^{*}_{2},S^{*}_{3}\\}$ is a partition of $S^{*}$.

For each $t\in U_{g}$, let $S^{*}_{1,t}\coloneqq S^{*}_{1}\cap H_{t}$, and
$S^{*}_{2,t}\coloneqq S^{*}_{2}\cap R_{t}$. Note that
$\left\\{S^{*}_{1,t}\right\\}_{t\in U_{g}}$ is a partition of $S^{*}_{1}$,
whereas a vertex $u$ may belong to multiple $S^{*}_{2,t}$’s. Also, note that
for any $t\in U_{g}$, $S^{*}_{1,t}$ is an independent set in $G[H_{t}]$, which
implies that $|S^{*}_{1,t}|\leq\textup{{OPT}}(G[H_{t}])$. Now, consider

$\displaystyle|S^{*}_{1}|+|S^{*}_{2}|$ $\displaystyle\leq\sum_{t\in
U_{g}}|S^{*}_{1,t}|+|S^{*}_{2,t}|$ $\displaystyle\leq\sum_{t\in
U_{g}}\textup{{OPT}}(G[H_{t}])+|R_{t}|$ (Since $S^{*}_{2,t}\subseteq R_{t}$ )
$\displaystyle\leq\sum_{t\in
U_{g}}\frac{1}{1-\epsilon/2}\cdot|S_{t}|+\frac{\epsilon}{2}\cdot|S_{t}|$
(Since $S_{t}$ is $1-\epsilon/2$-approximation, and by definition of good
node) $\displaystyle\leq(1+\epsilon)\cdot\sum_{t\in U_{g}}|S_{t}|$
$\displaystyle\leq\frac{1}{1-\epsilon}\cdot|S_{1}|$ (4)

Note that $S^{*}_{b}$ is an independent set in $G[V_{b}]$, which implies that

$\displaystyle|S^{*}_{b}|\leq\textup{{OPT}}(G[V_{b}])\leq\frac{1}{1-\epsilon}\cdot|S_{b}|$
(5)

Therefore,

$\displaystyle\textup{{OPT}}(G)=|S^{*}|$
$\displaystyle=|S^{*}_{1}|+|S^{*}_{2}|+|S^{*}_{b}|$
$\displaystyle\leq\frac{1}{1-\epsilon}\cdot|S_{1}|+\frac{1}{1-\epsilon}\cdot|S_{b}|$
(from (4) and (5)) $\displaystyle\leq\frac{1}{1-\epsilon}\cdot|S|$ (6)

Which concludes the proof. ∎

Now, since Independent Set has FII, and the size of an optimal solution in
each $G[H_{t}]$ for $t\in U_{b}$ is bounded, we can prove a lemma analogous to
Lemma 3, which uses $\mathcal{P}_{\mathbf{mod}}$ to return an optimal solution
$S_{b}\subseteq G[V_{b}]$ in time
$g(\mathbf{tw}_{\mathcal{H}}(G),\epsilon)\cdot n^{\mathcal{O}(1)}$. This
concludes the proof of the theorem. ∎

####  4.3.2 $\mathcal{F}$-Minor Packing and $\mathcal{S}$-Subgraph Packing

Now we adapt the previous proof to $\mathcal{F}$-Minor Packing and
$\mathcal{S}$-Subgraph Packing.

######  Theorem 7.

Let $\mathcal{H}$ be a well-behaved family of graphs. Let
$\Pi=\textup{{$\mathcal{F}$-Minor Packing}}$ (resp. $\mathcal{S}$-Subgraph
Packing), where $\mathcal{F}$ ($\mathcal{S}$) is a fixed finite family of
connected graphs, such that $\Pi$ is CMSO-definable and has FII. Then, the
following statements are equivalent.

  1. 1.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$
and $\epsilon$.

  2. 2.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{ed}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

  3. 3.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{tw}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

###### Proof.

We focus on $\Pi\coloneqq\textup{{$\mathcal{F}$-Minor Packing}}$, since the
arguments for $\mathcal{S}$-Subgraph Packing are only easier. Also, as before,
we prove $1\implies 3$. Let $\mathcal{P}_{\mathbf{mod}}$ be the FPT-AS for
$\Pi$ parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$ and $\epsilon$.

Let $G=(V,E)$ be the input graph on $n$ vertices, and $(T,\chi,L)$ be its
$\mathcal{H}$-tree decomposition of width $\ell$. By iterating over each leaf
node $t\in V(T)$, we use $\mathcal{P}_{\mathbf{mod}}$ on $G[H_{t}]$, to obtain
a solution
$\sigma_{t}\coloneqq\left\\{(G_{i,t},F_{i,t},\varphi_{i,t})\right\\}_{i\in[k_{t}]}$
for some $k_{t}\geq 0$, such that
$|\sigma_{t}|\geq(1-\epsilon)\cdot\textup{{OPT}}(G[H_{t}])$. Let
$S_{t}\coloneqq\bigcup_{i\in[k_{t}]}V(G_{i,t})$. If
$|R_{t}|\leq\epsilon/2\cdot|\sigma_{t}|$, then we say that the leaf node $t$
is _good_ ; _bad_ otherwise. All internal nodes are classified as _bad_. As
before, let $U_{g},U_{b}$ denote the sets of good and bad nodes respectively.
These definitions follow the same idea as in the proof of Theorem 12 so far.
Now, we slightly deviate, and use $V_{g}\coloneqq\bigcup_{t\in U_{g}}H_{t}$,
and let $V_{b}=V(G)\setminus V_{g}$. (Note that these definitions are
different from Theorem 12, where we used $\bigcup_{t\in U_{g}}\chi(t)$. That
is, the vertices of $R_{t}$ belong to $V_{b}$ instead of $V_{g}$.) Let
$\sigma_{1}=\bigcup_{t\in U_{g}}\sigma_{t}$, and let $\sigma_{b}$ denote an
$(1-\epsilon)$-approximate solution to $\Pi$ on $G[V_{b}]$. We claim the
following

######  Lemma 7.

$|\sigma|\geq(1-\epsilon)\cdot\textup{{OPT}}(G)$,
$\sigma=\sigma_{1}\cup\sigma_{b}$, as defined above.

###### Proof.

Let $\sigma^{*}$ denote an optimal solution to $\Pi$ on $G$. Let us classify
the minor models from $\sigma^{*}$ into three types. Consider some minor model
tuple $M=(G_{i},F_{i},\varphi_{i})\in\sigma^{*}$ that is a minor model tuple.
Note that the subgraphs $G_{i}$ are pairwise vertex-disjoint. Then,

  * •

$M$ is type 1 if for some good node $t\in U_{g}$, $V(G_{i})\subseteq H_{t}$.

  * •

$M$ is type 2 if for some good node $t\in U_{g}$, it holds that $V(G_{i})\cap
H_{t}\neq\emptyset$, and $V(G_{i})\setminus H_{t}\neq\emptyset$.
Since $\mathcal{F}$ contains connected graphs, this implies that, in
particular, $V(G_{i})\cap R_{t}\neq\emptyset$.

  * •

$M$ is type 3 if $V(G_{i})\subseteq V_{b}$.

Let $\sigma^{*}_{1},\sigma^{*}_{2},\sigma^{*}_{3}$ denote the subsets of
$\sigma$ containing minor model tuples of type 1, 2, 3 respectively. For each
$t\in U_{g}$, let
$\sigma^{*}_{1,t}=\left\\{(G_{i},F_{i},\varphi_{i})\in\sigma^{*}_{1}:V(G_{i})\subseteq
H_{t}\right\\}$, and note that $\left\\{\sigma^{*}_{1,t}\right\\}_{t\in
U_{g}}$ is a partition of $\sigma^{*}_{1}$. Note that

$|\sigma^{*}_{1,t}|\leq\textup{{OPT}}(G[H_{t}])$ (7)

Similarly, for each $t\in U_{g}$, let
$\sigma^{*}_{2,t}=\left\\{(G_{i},F_{i},\varphi_{i})\in\sigma^{*}_{2}:V(G_{i})\cap
H_{t}\neq\emptyset\right\\}$. Note that
$\left\\{\sigma^{*}_{2,t}\right\\}_{t\in U_{g}}$ is not necessarily partition
of $\sigma^{*}_{2}$, since a minor model from $\sigma^{*}_{2}$ may span
multiple $G[H_{t}]$’s. We first have the following observation.

######  Observation 3.

For any $t\in U_{g}$,
$|\sigma^{*}_{2,t}|\leq|R_{t}|\leq\epsilon/2\cdot|\sigma_{t}|$.

###### Proof.

For each $(G_{i},F_{i},\varphi_{i})\in\sigma^{*}_{2,t}$, note that
$V(G_{i})\cap R_{t}\neq\emptyset$. However, since
$\sigma^{*}_{2,t}\subseteq\sigma^{*}$, it follows that the vertex sets of
$G_{i}$’s from $\sigma^{*}_{2,t}$ are pairwise disjoint. This implies that
$|\sigma^{*}_{2,t}|\leq|R_{t}|$. Finally, since $t$ is a good node, by
definition, we have that $|R_{t}|\leq\epsilon/2\cdot|\sigma_{t}|$. ∎

Now, we proceed exactly as in the proof of Lemma 6. Consider,

$\displaystyle|\sigma^{*}_{1}|+|\sigma^{*}_{2}|$ $\displaystyle\leq\sum_{t\in
U_{g}}|\sigma^{*}_{1},t|+|\sigma^{*}_{2,t}|$ $\displaystyle\leq\sum_{t\in
U_{g}}\textup{{OPT}}(G[H_{t}])+\frac{\epsilon}{2}\cdot|\sigma_{t}|$ (From (7)
and 3) $\displaystyle\leq\sum_{t\in
U_{g}}\frac{1}{1-\epsilon/2}|\sigma_{t}|+\frac{\epsilon}{2}|\sigma_{t}|$ (8)
$\displaystyle\leq\frac{1}{1-\epsilon}\cdot\sum_{t\in
U_{g}}|\sigma_{t}|=\frac{1}{1-\epsilon}|\sigma_{1}|$ (9)

Since $\sigma^{*}_{b}$ is a valid solution to $\Pi$ on $G[V_{b}]$, it follows
that

$|\sigma^{*}_{b}|\leq\textup{{OPT}}(G[V_{b}])\leq\frac{1}{1-\epsilon}|\sigma_{b}|$
(10)

Finally, consider,

$\displaystyle\textup{{OPT}}(G)=|\sigma^{*}|$
$\displaystyle=|\sigma^{*}_{1}|+|\sigma^{*}_{2}|+|\sigma^{*}_{3}|$
$\displaystyle\leq\frac{1}{1-\epsilon}|\sigma_{1}|+\frac{1}{1-\epsilon}|\sigma_{b}|$
(From (9) and (10)) $\displaystyle=\frac{1}{1-\epsilon}|\sigma|$

This concludes the proof of the lemma. ∎

Now, the task is reduced to finding a solution $\sigma_{b}$ to $\Pi$ on
$G[V_{b}]$ such that
$|\sigma_{b}|\geq(1-\epsilon)\cdot\textup{{OPT}}(G[V_{b}])$. As before, we can
prove an analogous version of Lemma 3, where we use
$\mathcal{P}_{\mathbf{mod}}$ and the fact that $\Pi$ is CMSO-definable, to
obtain an optimal solution on $G[V_{b}]$. Again, the crucial observation is
that each replacement operation (i.e., application Lemma 14) requires solving
$\Pi$ exactly on an instance, where the instances are of the form
$G[\chi(t)]\oplus Y$, where $|V(Y)|\leq g(\ell,\epsilon)$. Since
$\textup{{OPT}}(G[\chi(t)])\leq\textup{{OPT}}(G[H_{t}])+|R_{t}|\leq
2\ell/\epsilon+\ell$, and each vertex in $Y$ can contribute to the image of at
most one minor model. Therefore, $\textup{{OPT}}(G[H_{t}\oplus Y])$ is upper
bounded by a function of $\ell$ and $\epsilon$. Therefore, by suitably
choosing the value of $\epsilon^{\prime}$, $\mathcal{P}_{\mathbf{mod}}$ can be
made to return an exact solution on such instance in time FPT in $\ell$ and
$\epsilon$. This concludes the proof of the theorem for $\mathcal{F}$-Minor
Packing. Finally, we note that all arguments only rely on assumption that the
graphs in $\mathcal{F}$ are connected, and thus also hold for
$\mathcal{S}$-Subgraph Packing. ∎

##  5 FPT-ASes for Dominating Set

In this section, we consider Dominating Set, defined as follows.

Blue-White Dominating Set Input: An instance $(G,k)$, where $G$ is a graph,
and $k$ is a non-negative integer Question: Does $G$ contain a dominating set
of size at most $k$, i.e., does there exist a set $S\subseteq V(G)$ such that
for each $u\in V(G)$, $N[v]\cap S\neq\emptyset$?

Note that the main difficulty is that Dominating Set is not monotone, i.e., it
does not necessarily hold that for any $S\subseteq V(G)$,
$\textup{{OPT}}(G-S)\leq\textup{{OPT}}(G)$. Thus, the approach for Vertex
Deletion to  $\mathcal{F}$ does not immediately generalize, and the arguments
for Dominating Set are technically more involved. Furthermore, it is not
immediately clear that Dominating Set is _self-reducible_. Therefore, we need
to rely on different _annotated versions_ of Dominating Set to design
approximation algorithms for the problem.

First, in Section 5.1, we design an FPT-AS for Dominating Set, parameterized
by the $\mathbf{mod}_{\mathcal{H}}(\cdot)$ and $\epsilon$, for any apex-minor
free family $\mathcal{H}$. Then we prove the equivalence theorem (cf. Theorem
9), which implies FPT-AS for Dominating Set, parameterized by
$\mathbf{ed}_{\mathcal{H}}(\cdot)$ (resp. $\mathbf{tw}_{\mathcal{H}}(\cdot)$)
and $\epsilon$. The proof of this theorem is conceptually similar to that of
Theorem 1; however, it is technically much more involved due to the reasons
mentioned above.

###  5.1 FPT-AS for Dominating Set Parameterized by
$\mathbf{mod}_{\mathcal{H}}$

In the following, we combine the case analysis from the previous approach, as
well as use arguments involving bidimensionality, as in Fomin et al. [11], to
design an FPT-AS for Dominating Set parameterized by
$\mathbf{mod}_{\mathcal{H}}(\cdot)$ and $\epsilon$, where $\mathcal{H}$ is a
family of apex-minor free graphs, which we fix in the following discussion.
Before proceeding to the algorithm for Dominating Set, we consider an
annotated version of Dominating Set and discuss its properties.

Annotated Dominating Set. We are given a graph $G^{\prime}$, and a set of
vertices $D\subseteq V(G^{\prime})$ that are marked as _dominated_ , and the
vertices of $V(G^{\prime})\setminus D$ are marked as _undominated_.
Furthermore, $G^{\prime}[D]$ is edgeless. The goal of Annotated Dominating Set
is to compute a minimum-size set of vertices that dominates all the vertices
of $V(G^{\prime})\setminus D$, i.e., to compute a dominating set for all the
undominated vertices. We use $(G^{\prime},D)$ to denote this instance of
Annotated Dominating Set.

In the definition of Annotated Dominating Set, we have enforced that
$G^{\prime}[D]$ is edgeless (i.e., the dominated vertices induce an
independent set). This assumption is convenient in the subsequent arguments,
and is without loss of generality, for the following reason. Note that a
solution for $(G^{\prime},D)$ is allowed to contain vertices from $D$, but it
is not required to dominate all the vertices of $D$. Thus, if a solution
contains a vertex $v\in D$, then $v$ must dominate one or more vertices from
$V(G^{\prime})\setminus D$ – otherwise we may obtain a smaller solution by
deleting $v$. However, observe that the set of neighbors of $v$ outside $D$ is
unaffected by deleting all the edges among the vertices in $D$.

Note that this is a generalization of the usual Dominating Set problem, which
is obtained by setting $D=\emptyset$. We observe that Fomin et al. [11] design
an EPTAS even for Annotated Dominating Set, when the input graph belongs to a
family of apex-minor free graphs 555Since $\mathcal{H}$ is a minor-closed
family, the graph obtained after deletion of edges among $D$ still belongs to
$\mathcal{H}$.. In our algorithm, we use this EPTAS as a black-box. A crucial
property used to obtain an EPTAS is that the problem is contraction
bidimensional. We sketch this argument, since we will subsequently use the
property in our analysis.

Consider an instance $(G^{\prime},D)$ of Annotated Dominating Set. Suppose we
contract an edge $e=uv\in E(G^{\prime})$ and obtain a graph
$G^{\prime\prime}\coloneqq G^{\prime}/e$. Then, let $D^{\prime\prime}\coloneqq
D\setminus\\{u,v\\}$, and let $(G^{\prime\prime},D^{\prime\prime})$ be the
resulting instance of Annotated Dominating Set. In other words, the vertex $w$
resulting from the contraction of the edge $uv$ is always marked as
_undominated_. The intuition for this is as follows. Recall that $D$ induces
an independent set in $G^{\prime}$. Therefore, the contracted edge $uv$ must
have at least one undominated endpoint. Thus, the vertex resulting from the
contraction must be marked as _undominated_. We now have the following simple
observations.

######  Observation 4.

  1. 1.

$\textup{{OPT}}(G^{\prime\prime},D^{\prime\prime})\leq\textup{{OPT}}(G^{\prime},D)$,
where $G^{\prime\prime}\coloneqq G^{\prime}/uv$ and $D^{\prime\prime}\coloneqq
D\setminus\\{u,v\\}$.

  2. 2.

$D^{\prime\prime}$ forms an independent set in $G^{\prime\prime}$.

###### Proof.

For item 1, let $S^{\prime}$ be a solution for Annotated Dominating Set
instance $(G^{\prime},D)$. Recall that at least one of the two vertices $u$
and $v$ must be undominated, say $u$. We consider two cases. (A) If
$S^{\prime}\cap\\{u,v\\}\neq\emptyset$, then let
$S^{\prime\prime}\coloneqq(S^{\prime}\setminus\\{u,v\\})\cup\\{w\\}$. (B)
Otherwise, $S^{\prime}$ contains a neighbor $u^{\prime}$ of $u$. Then, we let
$S^{\prime\prime}\coloneqq S^{\prime}$. Note that each of the two cases,
$S^{\prime\prime}$ is a valid solution for the resulting instance
$(G^{\prime\prime},D^{\prime\prime})$.

For item 2, we note that the vertex resulting from an edge contraction is
always an undominated vertex. It follows that two dominated vertices can never
become adjacent as a result of an edge contraction. ∎

We also need the following observation.

######  Observation 5.

Let $(G^{\prime},D)$ be an original instance, and suppose we obtain an
instance $(\Gamma_{k},D^{\prime})$ from $(G^{\prime},D)$ after a series of
edge contractions, as defined above, where $\Gamma_{k}$ is the $k\times k$
triangulated grid for a sufficiently large integer $k\geq 0$ (see Section A.5
for a formal definition). Then,
$\textup{{OPT}}(\Gamma_{k},D^{\prime})\geq\Omega(k^{2})$.

###### Proof.

We prove that any subgraph forming a $5\times 5$ triangulated grid must have
at least one vertex in the solution. Then, the claim follows. Consider a
vertex $u\in D^{\prime}$ that is at least $5$ rows and columns away from the
boundary of the grid. Let $W=N(u)$ be the set of neighbors of $u$. Note that
$|W|=6$ and $W$ is a subset of the $3\times 3$ sub-grid centered at $u$.
Furthermore, 4 implies that $W\cap D^{\prime}=\emptyset$, since the instance
$(\Gamma,D^{\prime})$ is obtained from a series of edge contractions from an
original instance $(G^{\prime},D)$, wherein $D$ forms an independent set. This
implies that any solution must contain at least one vertex from the set of
vertices $P$ forming a $5\times 5$ sub-grid centered at $u$, since
$N[W]\subseteq P$. ∎

4 and 5 imply the following Lemma.

######  Lemma 8.

Annotated Dominating Set is contraction bidimensional.

Additionally, we state the following result from Fomin et al. [11].

######  Proposition 1 (Corollary of Lemma 3 from [11]).

Let $(G^{\prime},D)$ be an instance of Annotated Dominating Set, where
$G^{\prime}$ belongs to a family of apex-minor free graphs $\mathcal{H}$.
Then,
$\mathbf{tw}(G^{\prime})\leq\mathcal{O}\left(\sqrt{OPT(G^{\prime},D)}\right)$.

Paramaterized Approximation Scheme. To design an FPT-AS for Dominating Set, we
combine the case analysis from the previous section along with arguments
involving bidimensionality. Recall that the input is $G=(V,E)$ and $M\subseteq
V(G)$ with $|M|=p$, such that $G^{\prime}\coloneqq G\setminus
M\in\mathcal{H}$. Let $H\coloneqq V(G)\setminus M$, and let $D\coloneqq
N(M)\subseteq H$. Note that $G^{\prime}=G[H]$. Let $(G^{\prime},D)$ denote an
instance of Annotated Dominating Set, where we want to compute a dominating
set for the vertices in $H\setminus D$. Since $G^{\prime}\in\mathcal{H}$, we
use the EPTAS from [11] to compute a $(1+\frac{\epsilon}{2})$-approximate
solution $S$. That is,
$|S|\leq(1+\frac{\epsilon}{2})\textup{{OPT}}(G^{\prime},D)$. Note that this
takes $2^{\mathcal{O}(1/\epsilon)}\cdot n^{\mathcal{O}(1)}$ time. Now, we
consider two cases.

Case 1. $p\leq\frac{\epsilon}{3}|S|$. In this case, we have the following
claim.

######  Claim 3.

If $p=|M|\leq\frac{\epsilon}{3}\cdot|S|$, then $M\cup S$ is a
$(1+\epsilon)$-approximation for Dominating Set on the graph $G$.

###### Proof.

The solution $S$ dominates all vertices of $H\setminus D$. Any remaining
vertex of $V(G)$ either belongs to $M$ or to $D$. However, since $D=N(M)$, the
solution $M\cup S$ is a dominating set for $G$.

Now we argue about the approximation guarantee. Let $S^{*}$ denote an optimal
Dominating Set solution for $G$. We first argue that $S^{*}\setminus M$ is a
feasible solution for Annotated Dominating Set instance $(G^{\prime},D)$.
Consider any vertex $u\in H\setminus D$. If $u\not\in S^{*}$, then $u$ is
dominated by a neighbor $v\in S^{*}$. Note that $v\not\in M$, since otherwise
$u\in N(M)=D$, which is a contradiction. Therefore, every $u\in H\setminus D$
is dominated by some vertex of $S^{*}\setminus M$. Therefore,
$\textup{{OPT}}(G^{\prime},D)\leq|S^{*}\setminus M|\leq|S^{*}|$. Then, the
claim follows, since
$|S|+|M|\leq(1+\epsilon/3)(1+\epsilon/2)\cdot\textup{{OPT}}(G^{\prime},D)\leq(1+\epsilon)\cdot|S^{*}|.$
∎

Case 2.
$p>\frac{\epsilon}{3}\cdot|S|\geq\frac{\epsilon}{3}\cdot\textup{{OPT}}(G^{\prime},D)$.
In this case, we have the following claim.

######  Claim 4.

If $p=|M|>\frac{\epsilon}{3}\cdot\textup{{OPT}}(G^{\prime},D)$, then
$\mathbf{tw}(G)\leq p+\mathcal{O}\left(\sqrt{\frac{p}{\epsilon}}\right)$.
In this case, there exists a
$2^{\mathcal{O}\left(p+\sqrt{\frac{p}{\epsilon}}\right)}\cdot
n^{\mathcal{O}(1)}$ time algorithm to find an optimal dominating set for $G$.

###### Proof.

Recall that Proposition 1 implies that
$\mathbf{tw}(G^{\prime})\leq\mathcal{O}\left(\sqrt{OPT(G^{\prime},D)}\right)$,
and due to case assumption, we have that
$\textup{{OPT}}(G^{\prime},D)\leq=3p/\epsilon$. Finally,
$\mathbf{tw}(G)\leq\mathbf{tw}(G\setminus M)+|M|\leq
p+\mathcal{O}(\sqrt{\frac{p}{\epsilon}})$. Since the treewidth of $G$ is
bounded, we can use a $2^{\mathcal{O}(\mathbf{tw}(G))}\cdot
n^{\mathcal{O}(1)}$ time algorithm to find an optimal dominating set for $G$.
∎

By combining the results from two cases, we get the following theorem.

######  Theorem 8.

Suppose we are given a graph $G$, and a set $M\subseteq V(G)$ of size $p$,
such that $G^{\prime}\coloneqq G\setminus M\in\mathcal{H}$, where
$\mathcal{H}$ is a family of apex-minor free graphs. Then, there exists an
$f(p,\epsilon)\cdot n^{\mathcal{O}(1)}$ time algorithm to find a
$(1+\epsilon)$-approximation for Dominating Set on $G$, where
$f(p,\epsilon)=\max\left\\{2^{\mathcal{O}(p+\sqrt{\frac{p}{\epsilon}})},\ \
2^{\mathcal{O}(1/\epsilon)}\right\\}$.

###  5.2 Equivalence Theorem for Dominating Set

In this section, we prove the following equivalence theorem for Dominating
Set, assuming that $\mathcal{H}$ be _well-behaved_ , i.e., hereditary and
closed under disjoint union.

######  Theorem 9.

Let $\mathcal{H}$ be any well-behaved family of graphs, and let
$\Pi=\textup{{Dominating Set}}$. Then, the following statements are
equivalent.

  1. 1.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$
and $\epsilon$.

  2. 2.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{ed}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

  3. 3.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{tw}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

###### Proof.

We prove $1\implies 3$. Let $\mathcal{P}_{\mathbf{mod}}$ be the assumed FPT-AS
for $\Pi$ parameterized by $\mathbf{mod}_{\mathcal{H}}$ and $\epsilon$. Let
$G=(V,E)$ be the input graph on $n$ vertices, along with an $\mathcal{H}$-tree
decomposition $(T,\chi,L)$. Let $\ell$ denote the width of the given
$\mathcal{H}$-tree decomposition. First, if $\mathcal{H}$ only contains the
empty graph $(\emptyset,\emptyset)$, our goal is to prove that Dominating Set
admits an FPT-AS parameterized by (standard) $\mathbf{tw}(\cdot)$. Indeed,
since Dominating Set is FPT parameterized by $\mathbf{tw}(\cdot)$, we assume
that $\mathcal{H}$ contains at least one non-empty graph. In particular, due
to hereditary property, $\mathcal{H}$ must contain a graph on a single vertex.
Furthermore, we assume that $\ell\geq 1$ – otherwise $G$ is a disjoint union
of graphs belonging to $\mathcal{H}$. This implies that $G\in\mathcal{H}$, in
which case all three statements are trivially equivalent.

As before, for any leaf node $t\in V(T)$, let $V_{t}=\chi(t)$,
$H_{t}=V_{t}\cap L$, and $R_{t}=V_{t}\setminus H_{t}$. Note that
$G[H_{t}]\in\mathcal{H}$, and the sets $\\{H_{t}\\}_{t\in V(T)}$ are pairwise
disjoint, and $|R_{t}|\leq\ell$ for any $t\in V(T)$.

We iterate over every leaf node $t\in V(T)$, and create a new graph
$\widetilde{G}_{t}$ as follows. Let $v^{*}$ be a new vertex that is not in
$V_{t}$. Let $V^{\prime}_{t}=V_{t}\cup\\{v^{*}\\}$. Let
$E^{\prime}_{t}=E(G[V_{t}])\cup\widetilde{E}$, where
$\widetilde{E}=\left\\{v^{*}u:u\in R_{t}\right\\}$. That is, the graph
$\widetilde{G}_{t}$ is obtained by adding a new vertex $v^{*}$ to the graph
$G[V_{t}]$ and making it adjacent to all vertices of $R_{t}$.

Note that $\widetilde{G}^{\prime}-R_{t}=G[H_{t}]\uplus G^{*}$, where
$G^{*}=({v^{*}},\emptyset)$ is an isolated component containing $v^{*}$. Now,
$G[H_{t}]\in\mathcal{H}$, and $G^{*}\in\mathcal{H}$, which implies that
$\widetilde{G}^{\prime}-R_{t}=G[H_{t}]\uplus G^{*}\in\mathcal{H}$, since
$\mathcal{H}$ is closed under disjoint union. Now, we use
$\mathcal{P}_{\mathbf{mod}}$ on $\widetilde{G}_{t}$ to obtain
$\widetilde{S}_{t}\subseteq V(\widetilde{G}_{t})$, such that (i)
$\widetilde{S}_{t}$ is a dominating set for $\widetilde{G}_{t}$, and (ii)
$|\widetilde{S}_{t}|\leq(1+\epsilon/4)\cdot\textup{{OPT}}(\widetilde{G}_{t})$.
Let $S_{t}=\widetilde{S}_{t}\setminus\\{v^{*}\\}$.

For a leaf node $t\in V(T)$ if $\ell\leq\frac{\epsilon}{29}\cdot|S_{t}|$, then
we say that $t$ is a _good_ node; and _bad_ otherwise. All internal nodes are
classified as bad. Let $U_{g},U_{b}$ denote the sets of good and bad nodes
respectively. Let $V_{g}=\bigcup_{t\in U_{g}}H_{t}$, $V_{m}=\bigcup_{t\in
U_{g}}R_{t}$, and $V_{b}=V(G)\setminus(V_{g}\cup V_{m})$.

Let $D^{*}$ be an optimal dominating set for $G$, and for any $t\in U_{g}$,
let $D^{*}_{1,t}=H_{t}\cap D^{*}$, and $D^{*}_{2,t}=R_{t}\cap D^{*}$, and
$D^{*}_{t}=D^{*}_{1,t}\cup D^{*}_{2,t}$. Let $D^{*}_{1}=\bigcup_{t\in
U_{G}}D^{*}_{1,t}$, and $D^{*}_{2}=\bigcup_{t\in U_{g}}D^{*}_{2,t}$. Note that
$\left\\{D^{*}_{1,t}\right\\}_{t\in U_{g}}$ is a partition of $D^{*}_{1}$,
whereas a vertex in $D^{*}_{2}$ may belong to multiple $D^{*}_{2,t}$’s.
Finally, let $D^{*}_{b}=D^{*}\cap V_{b}$. Note that
$\left\\{D^{*}_{1},D^{*}_{2},D^{*}_{b}\right\\}$ is a partition of $D^{*}$.

Now, let $S_{1}\coloneqq\bigcup_{t\in U_{g}}S_{t}$, and
$S_{2}\coloneqq\bigcup_{t\in U_{g}}R_{t}$. We wish to add $S_{1}\cup S_{2}$ to
our solution. Since each $R_{t}$ is a separator between $H_{t}$ and
$G-\chi(t)$, we can delete $V_{g}$ from the graph. However, we cannot simply
delete $V_{m}=S_{2}$ from the graph – since the vertices in $S_{2}$ may
already dominate a subset of vertices in $V_{b}$. Therefore, we need to
“remember” that we have decided to add $S_{2}$ into our solution. To this end,
we define an _annotated_ version of Dominating Set, which we call Blue-White
Dominating Set (note that this is similar to, but not exactly the same as
Annotated Dominating Set problem defined in the previous subsection). The
Blue-White Dominating Set problem is defined as follows.

Blue-White Dominating Set Input: An instance $(G,B,W,k)$, where $G$ is a
graph, $V(G)=B\uplus W$, and $k$ is a non-negative integer Question: Does
there exist a subset $S\subseteq V(G)$ of size at most $k$ such that (i) $S$
is a dominating set for $G$, and (ii) $B\subseteq S$?

Let $F\coloneqq G[S_{2}\uplus V_{b}]$. We want to find the smallest integer
$k^{\prime}$, such that $(F,S_{2},V_{b},k^{\prime})$ is a yes-instance of
Blue-White Dominating Set. Let $S_{b}$ denote an $(1+\epsilon/2)$-approximate
solution on this instance, i.e., (i) $S_{b}\subseteq S_{2}\cup V_{b}$ is a
dominating set for $F$, (ii) $S_{2}\subseteq S_{b}$, and (iii)
$|S_{b}|\leq(1+\epsilon/2)\cdot\textup{{OPT}}^{\prime}(F)$, where
$\textup{{OPT}}^{\prime}(F)$ denotes the size of the optimal solution for the
Blue-White Dominating Set instance. We prove the following technical lemma,
the proof of which is rather involved, and thus given after finishing the
current proof.

######  Lemma 9.

$|S|=|S_{1}|+|S_{2}|+|S_{b}|\leq(1+\epsilon)\cdot\textup{{OPT}}(G)$ (11)

Thus, our task is reduced to finding an approximate solution to Blue-White
Dominating Set on $(F,S_{2},V_{b},k^{\prime})$; in fact, we will find an exact
solution. To do this, first we prove the following lemma, which shows that
Blue-White Dominating Set can be reduced to the (standard) dominating problem
on an auxiliary graph. The proof is given after finishing the current proof.

######  Lemma 10.

Let $\mathcal{I}=(G,B,W,k)$ be an instance of Blue-White Dominating Set. Let
$G^{\prime}$ be the graph obtained by attaching $N=n^{2}$ distinct pendant
vertices to each vertex in $B$, where $n=|V(G)|$. Let
$\mathcal{I}^{\prime}=(G^{\prime},k)$ be the resulting instance of Dominating
Set. Then $\mathcal{I}$ is a yes-instance of Blue-White Dominating Set iff
$\mathcal{I}^{\prime}$ is a yes-instance of Dominating Set.

As suggested by Lemma 10, we create a graph $F^{\prime}$, as follows. For each
$u\in S_{2}$, let $P_{u}$ denote the set of $|V(F)|^{2}$ distinct pendant
vertices attached to $u$. By slightly abusing the notation, let $(T,\chi,L)$
be the original $\mathcal{H}$-tree decomposition, restricted to the vertices
of $F$. We modify this to obtain an $\mathcal{H}$-tree decomposition for
$F^{\prime}$. Consider a vertex $u\in S_{2}$, and note that $u\in R_{t}$ for
some $t\in V(T)$. We pick one such arbitrary node $t$, and add a child
$t_{u}$, which becomes a leaf in $T$. For this node $t_{u}$, we define its bag
$\chi^{\prime}(t_{u})=P_{u}\cup\\{u\\}$, where $P_{u}$ becomes the set of
_base vertices_ in $\chi^{\prime}(t_{u})$, and $u$ is a non-base vertex in
$\chi^{\prime}(t_{u})$. Note that $G[P_{u}]$ is a set of isolated vertices,
and thus belongs to $\mathcal{H}$. For all original nodes $t\in V(T)$, we set
$\chi^{\prime}(t)=\chi(t)$. Finally, $L^{\prime}=\bigcup_{u\in S_{2}}P_{u}$,
and let $T^{\prime}$ be the resulting tree. It is easy to see that
$(T^{\prime},\chi^{\prime},L^{\prime})$ is a valid $\mathcal{H}$-tree
decomposition for $F^{\prime}$ of width at most $\ell$.

Now, we can prove an analogous version of Lemma 3 for the instance
$(F,k^{\prime})$ of Dominating Set. It is known that Dominating Set is CMSO-
definable and has FII [13]. We highlight the key differences required to
perform replacement using the FII property of Dominating Set. Note that for a
node that was earlier classified as _bad_ ,
$\textup{{OPT}}(F[H_{t}])=\textup{{OPT}}(G[H_{t}])\leq 29\ell/\epsilon$, which
implies that $\textup{{OPT}}(F[\chi^{\prime}(t)])\leq 29\ell/\epsilon+\ell\leq
30\ell/\epsilon$. On the other hand, if $t$ is a newly added leaf node then
$\textup{{OPT}}(F[\chi^{\prime}(t)])\leq|R_{t}|\leq\ell$. This implies that,
when we want to find a replacement for $G[\chi^{\prime}(t)]$ using an
application of Lemma 14, we want to decide instances of the form
$F[\chi^{\prime}(t)]\oplus Y$, where $|V(Y)|$ is upper bounded by some
function of $\ell$. Therefore, $\textup{{OPT}}(F[\chi^{\prime}(t)]\oplus
Y)\leq\textup{{OPT}}(F[\chi^{\prime}(t)])+|V(Y)|$, which is upper bounded by
some function of $\ell$ and $\epsilon$. Therefore, a version of Lemma 3 can
solve _the decision version_ of Blue-White Dominating Set.

Now, we discuss how to find a solution, using the algorithm for the decision
version as an oracle. We try the following for the values of
$k=|S_{2}|,|S_{2}|+1,\ldots$, until the first time the decision version
returns that $\textup{{Blue-White Dominating Set}}(F,S_{2},V(F)\setminus
S_{2},k)$ is a yes-instance. Let $k^{*}$ denote this value.

We maintain a partial solution $S_{b}$, which is initialized to $S_{2}$.
Consider a leaf node $t\in V(T)$, such that $S_{b}$ does not already dominate
all vertices of $\chi^{\prime}(t)\cap L^{\prime}$. We pick an arbitrary
_original_ vertex $u\in\chi^{\prime}(t)\cap L^{\prime}$, and use the algorithm
to decide the instance
$(F,S_{b}\cup\left\\{u\right\\},V(F)\setminus(S_{b}\cup\left\\{u\right\\}),k^{*})$
of Blue-White Dominating Set. If the algorithm returns no, then we conclude
that $u$ does not belong to a solution of size $k^{*}$. Otherwise, we update
$S_{b}$ by adding $u$ to it, and proceed to the next iteration.

Now we discuss the technicalities when we use the reduction from Lemma 10 on
the newly created Blue-White Dominating Set instance. In this reduction, we
add $N=n^{2}$ distinct pendant vertices to $u$, and let $F_{u}$ be the
resulting graph. We add all these vertices to $L^{\prime}$ and to
$\chi^{\prime}(t)$. We also remove $u$ from $L$, i.e., move it from $H_{t}$ to
$R_{t}$. Note that the resulting base graph is a disjoint union of
$F^{\prime}[H_{t}]-u$ and the $N$ pendant vertices, each of which belong to
$\mathcal{H}$ due to the well-behaved property. The size of the modulator
increases by $1$. However, since $\textup{{OPT}}(F[\chi(t)])$ is bounded by
$29\ell/\epsilon$, therefore, we move at most $29\ell/\epsilon$ vertices from
$H_{t}$ to $L_{t}$. Thus, the width of the resulting $\mathcal{H}$-tree
decomposition remains bounded by $\ell+29\ell/\epsilon$. Furthermore, even for
an incorrect choice of $u$, $\textup{{OPT}}(F^{\prime}[\chi^{\prime}(t)])$
remains bounded by a function of $\ell$ and $\epsilon$. Thus, a version of
Lemma 3 can still be used to obtain a solution $S_{b}$ of size $k^{*}$ to the
original instance $(F,S_{2},V_{b},k^{*})$. This concludes the proof of the
theorem.

∎

###  5.3 Proofs of Technical Lemmas

Now we prove the technical lemmas from the proof of Theorem 9. For
convenience, we reiterate the statement of each lemma and then provide the
proof.

See 9

###### Proof.

First, we prove two technical claims, then the bound follows. The first claim
is stated below.

######  Claim 5.

The following two inequalities hold.

$|S_{2}|\leq\left(1+\frac{\epsilon}{24}\right)\cdot(|D^{*}_{1}|+|D^{*}_{2}|)$
(12) $|S_{1}|+|S_{2}|\leq\sum_{t\in
U_{g}}|S_{t}|+|R_{t}|\leq\left(1+\frac{7\epsilon}{11}\right)\cdot(|D^{*}_{1}|+|D^{*}_{2}|)$
(13)

###### Proof.

First, we consider on a particular $t\in U_{g}$, and focus on showing the
following inequality.

$|S_{t}|+|R_{t}|\leq(1+\epsilon)\cdot|D^{*}_{t}|=(1+\epsilon)\cdot(|D^{*}_{1,t}|+|D^{*}_{2,t}|)$
(14)

First, we note that $D^{*}_{1,t}\cup D^{*}_{2,t}\cup\left\\{v^{*}\right\\}$ is
a dominating set for $\widetilde{G}_{t}$. It follows that,

$\textup{{OPT}}(\widetilde{G}_{t})\leq|D^{*}_{1,t}|+|D^{*}_{2,t}|+1$ (15)

Now, note that,

$\textup{{OPT}}(\widetilde{G}_{t})\leq|\widetilde{S}_{t}|\leq\left(1+\frac{\epsilon}{4}\right)\cdot\textup{{OPT}}(\widetilde{G}_{t})\leq\left(1+\frac{\epsilon}{4}\right)\cdot\left(|D^{*}_{1,t}|+|D^{*}_{2,t}|+1\right)$
(16)

Now, note that since $t$ is a good node,
$|S_{t}|\geq|\widetilde{S}_{t}|-1\geq\frac{29\ell}{\epsilon}$. Therefore,
$|\widetilde{S}_{t}|\geq\frac{28\ell}{\epsilon}$ since $\ell\geq 1$. Combining
this with (16), we obtain that

$2\cdot(|D^{*}_{1,t}|+\ell+\ell)\geq\left(1+\frac{\epsilon}{4}\right)\cdot\left(|D^{*}_{1,t}|+|D^{*}_{2,t}|+1\right)\geq|S_{t}|\geq\frac{28\ell}{\epsilon}$

Then, from the first and the last term in this sequence of inequalities, we
obtain that

$|D^{*}_{1,t}|+4\ell\geq\frac{28\ell}{\epsilon}\ \implies\
|D^{*}_{1,t}|\geq\frac{24\ell}{\epsilon}\ \implies\
1\leq\ell\leq\frac{\epsilon}{24}\cdot|D^{*}_{1,t}|$ (17)

It follows that

$\displaystyle|S_{t}|\leq|\widetilde{S}_{t}|$
$\displaystyle\leq\left(1+\frac{\epsilon}{4}\right)\cdot(|D^{*}_{1,t}|+|D^{*}_{2,t}|+1)$
(From (16))
$\displaystyle\leq\left(1+\frac{\epsilon}{4}\right)\cdot\left(|D^{*}_{1,t}|+\frac{2\epsilon}{24}\cdot|D^{*}_{1,t}|\right)$
(from (17))
$\displaystyle\leq\left(1+\frac{\epsilon}{2}\right)\cdot|D^{*}_{1,t}|$ (18)

Finally, consider

$\displaystyle|S_{t}|+|R_{t}|$
$\displaystyle\leq\left(1+\frac{\epsilon}{11}\right)|S_{t}|$ (Since
$|R_{t}|\leq\ell\leq\frac{\epsilon}{11}|S_{t}|$)
$\displaystyle\leq\left(1+\frac{\epsilon}{2}\right)\cdot\left(1+\frac{\epsilon}{11}\right)\cdot|D^{*}_{1,t}|$
(From (18)) $\displaystyle\leq(1+\frac{7\epsilon}{11})\cdot|D^{*}_{1,t}|$ (19)

Now, adding (14) over all $t\in U_{g}$, we obtain,

$\displaystyle|S_{1}|+|S_{2}|$ $\displaystyle\leq\sum_{t\in
U_{g}}|S_{t}|+|R_{t}|$
$\displaystyle\leq\left(1+\frac{7\epsilon}{11}\right)\cdot\sum_{t\in
U_{g}}|D^{*}_{1,t}|$
$\displaystyle\leq\left(1+\frac{7\epsilon}{11}\right)\cdot|D^{*}_{1}|$

This shows (13).

Finally, since $|R_{t}|\leq\ell\leq\frac{\epsilon}{24}\cdot|D^{*}_{1,t}|$, we
obtain (12) as follows.

$\displaystyle|S_{2}|$ $\displaystyle\leq\sum_{t\in
U_{g}}|R_{t}|\leq\sum_{t\in U_{g}}\frac{\epsilon}{24}\cdot\sum_{t\in
U_{g}}|D^{*}_{1,t}|\leq\frac{\epsilon}{24}\cdot|D^{*}_{1}|$

∎

Next, we have the following.

######  Claim 6.

$|S_{b}|\leq\left(1+\epsilon\right)\cdot|D^{*}_{b}|+\frac{\epsilon}{16}\cdot|D^{*}_{1}|$
(20)

###### Proof.

Note that $D^{*}_{b}\cup S_{2}\subseteq S_{2}\cup V_{b}$ is a dominating set
for $F$ and it contains $S_{2}$ as a subset. Therefore,
$\textup{{OPT}}^{\prime}(F)\leq|D^{*}_{b}|+|S_{2}|$. Now, consider

$\displaystyle|S_{b}|$
$\displaystyle\leq\left(1+\frac{\epsilon}{2}\right)\cdot\left(|D^{*}_{b}|+|S_{2}|\right)$
$\displaystyle\leq\left(1+\epsilon\right)\cdot|D^{*}_{b}|+\left(1+\frac{\epsilon}{2}\right)\cdot\frac{\epsilon}{24}\cdot|D^{*}_{1}|$
(From 5)
$\displaystyle\leq(1+\epsilon)\cdot|D^{*}_{b}|+\frac{\epsilon}{16}\cdot|D^{*}_{1}|$

This concludes the proof of the claim. ∎

Now, we are ready to conclude the proof of Lemma 9. From 5 and 6, we have that

$\displaystyle|S|=|S_{1}|+|S_{2}|+|S_{b}|$
$\displaystyle\leq\left(1+\frac{7\epsilon}{11}\right)\cdot|D^{*}_{1}|+(1+\epsilon)\cdot|D^{*}_{b}|+\frac{\epsilon}{16}\cdot|D^{*}_{1}|$
$\displaystyle\leq(1+\epsilon)\cdot|D^{*}_{1}|+(1+\epsilon)\cdot|D^{*}_{b}|$
$\displaystyle\leq(1+\epsilon)\cdot|D^{*}|$ (Since
$|D^{*}|=|D^{*}_{1}|+|D^{*}_{2}|+|D^{*}_{b}|$)
$\displaystyle=(1+\epsilon)\cdot\textup{{OPT}}(G)$

∎

See 10

###### Proof.

In the forward direction, consider a dominating set $S\subseteq V(G)$ of size
$k$, such that $B\subseteq S$. In the graph $G^{\prime}$, $S$ dominates all
vertices of $V(G)$. A vertex $u\in V(G^{\prime})\setminus V(G)$ is a pendant
vertex adjacent to some $v\in B$. Since $B\subseteq S$, $u$ is dominated by
$v\in S$.

In the reverse direction, consider a dominating set $S^{\prime}\subseteq
V(G^{\prime})$ of size $k\leq|V(G)|$. Since $S^{\prime}$ dominates all
vertices of $V(G^{\prime})$, in particular, it dominates the vertices of
$V(G)$. Now, suppose there exists some $v\in B$ such that $v\not\in
S^{\prime}$. Then, all of its $n^{2}$ pendant neighbors must belong to
$S^{\prime}$, since $S^{\prime}$ is a dominating set. However, since
$|S^{\prime}|\leq k<n^{2}$, this is a contradiction. ∎

##  6 FPT-ASes for Connectivity Problems

In this section we show that bucket versus ocean also yields FPT-ASes for
connectivity problems such as Connected Vertex Cover and Connected Dominating
Set. Let $\mathcal{H}$ be an apex-minor closed family. We are given a graph
$G=(V,E)$, and a set $M\subseteq V(G)$ of size at most $p$ such that
$G^{\prime}=G\setminus M\in\mathcal{H}$, Let $H=V(G)\setminus M$.

We first design FPT-AS for Connected Vertex Cover. Given an $\epsilon>0$, we
fix an $\epsilon^{\prime}=\frac{\epsilon}{5}$. Our objective is to find a
connected vertex cover $S\subseteq V(G)$ in $G$ of size $|S|\leq(1+\epsilon)\
\textup{{OPT}}(G)$ where $\textup{{OPT}}(G)$ denotes the size of a smallest
connected vertex cover of $G$. Recall that a vertex set $S\subseteq V(G)$ is
called connected vertex cover if $S$ is a vertex cover of $G$ and $G[S]$ is
connected. Without loss of generality, we assume that the graph is connected.
Indeed, we can safely delete isolated vertices, and if we have at least two
connected components of size at least $2$, then it is trivially no-instance.

Observe that a connected vertex cover of $G$ may not be connected vertex cover
for its induced subgraphs. More elaborately, for a graph $G$, if $G$ has a
connected vertex cover $S$, then for any induced subgraph $G[Y]$ of $G$,
$(S\cap Y)$ is a vertex cover but not necessarily a connected vertex cover for
$G[Y]$. However, observe that every connected component $C$ of $G-M$
intersects with a neighbor of $M$. That is, $C\cap N(M)\neq\emptyset$. This
leads us to the following variant of Vertex Cover problem which is used later
in our FPT-AS.

Set Intersecting Vertex Cover Input: A graph $G^{\prime}$, a set $X\subseteq
V(G^{\prime})$ Objective: Find a minimum vertex cover, say $Z$, of
$G^{\prime}$ such that every connected component of $G^{\prime}[Z]$ contains a
vertex from $X$.

Fomin et al. [11, Section $4.1$] has shown that Set Intersecting Vertex Cover
admits an EPTAS, with running time
$2^{\mathcal{O}(1/\epsilon)}n^{\mathcal{O}(1)}$ on apex minor free graphs. We
use this result with $G^{\prime}$ and $X=N(M)$, and obtain a solution
$S^{\prime}$ of Set Intersecting Vertex Cover, of size
$(1+\epsilon^{\prime})\textup{{OPT}}_{{\sf SIVC}}(G^{\prime})$. Here,
$\textup{{OPT}}_{{\sf SIVC}}(G^{\prime})$ denotes the size of a smallest
vertex cover, say $Z$, of $G^{\prime}$ such that every connected component of
$G^{\prime}[Z]$ contains a vertex from $X$. Next we prove two important
inequalities.

######  Lemma 11.

$\textup{{OPT}}_{{\sf SIVC}}(G^{\prime})\leq\textup{{OPT}}(G)$

###### Proof.

Let $Y$ be an optimum solution for the Connected Vertex Cover problem in $G$.
Hence, $|Y|=\textup{{OPT}}(G)$. Recall that $G^{\prime}=G\setminus M$ and
$X=N(M)$. Observe that, every connected component of $Y\cap G^{\prime}$ has a
neighbour in $M$. Thus, $Y\cap G^{\prime}$ is also a feasible solution for Set
Intersecting Vertex Cover of $G^{\prime}$. Hence, $\textup{{OPT}}_{{\sf
SIVC}}(G^{\prime})\leq|Y\cap V(G^{\prime})|\leq|Y|=\textup{{OPT}}(G)$. This
concludes the proof of the lemma. ∎

######  Lemma 12.

$\textup{{OPT}}(G)\leq\textup{{OPT}}_{{\sf SIVC}}(G^{\prime})+2|M|$. Further,
given a solution $S^{\prime\prime}$ of size $\textup{{OPT}}_{{\sf
SIVC}}(G^{\prime})$, we can construct a connected vertex cover of $G$ of size
at most $(|S^{\prime\prime}|+2|M|)$ in polynomial time.

###### Proof.

Observe that $(S^{\prime\prime}\cup M)$ is a vertex cover of $G$ but might not
be a connected vertex cover of $G$. However, each connected component of
$S^{\prime\prime}$ can be classified by a vertex of $M$, which implies that
when we add $M$ to $S^{\prime\prime}$, then $G[S^{\prime\prime}\cup M]$ has at
most $|M|$ connected components. If $G[S^{\prime\prime}\cup M]$ is connected,
we are done. Otherwise, since $G$ is connected there exists a vertex, say $v$,
that has neighbors in two connected component of $G[S^{\prime\prime}\cup M]$.
Add $v$ to $(S^{\prime\prime}\cup M)$. Observe that every such addition
reduces the number of connected component of $(S^{\prime\prime}\cup M)$ by at
least $1$. Since $G[S^{\prime\prime}\cup M]$ has at most $|M|$ connected
components, we need to repeat this procedure at most $(|M|-1)$ times to make
it connected. At the end, the size of the connected vertex cover solution will
be at most $(|S^{\prime\prime}|+2|M|-1)$. The bound of
$\textup{{OPT}}(G)\leq\textup{{OPT}}_{{\sf SIVC}}(G^{\prime})+2|M|$ follows
from the construction. The whole process takes polynomial time which concludes
the proof. ∎

After getting $S^{\prime}$, we compare the size of $S^{\prime}$ with the size
of the modulator $M$ and accordingly we divide it into two cases.

  * •

Case 1: $|M|>\epsilon^{\prime}|S^{\prime}|$, implies that
$|S^{\prime}|<|M|/\epsilon^{\prime}$. This implies that $\textup{{OPT}}_{{\sf
SIVC}}\leq|S^{\prime}|\leq|M|/\epsilon^{\prime}$. Further, using Lemma 12, we
can say that $\textup{{OPT}}(G)\leq\textup{{OPT}}_{{\sf
SIVC}}+2|M|\leq\frac{|M|}{\epsilon^{\prime}}+2|M|$. Now, using the know
parameterized algorithm for Connected Vertex Cover that checks whether $G$ has
a connected vertex cover of size $k$ in time $2^{k}n^{\mathcal{O}(1)}$ [6], we
can find a smallest connected vertex cover $S$ of $G$ in time
$2^{\mathcal{O}(p/\epsilon)}n^{\mathcal{O}(1)}$. Hence, in this case, we solve
our problem exactly.

  * •

Case 2: $|M|\leq\epsilon^{\prime}|S^{\prime}|$. Starting from $S^{\prime}$,
using Lemma 12, we construct a connected vertex cover $S$ of size at most
$|S^{\prime}|+2|M|\leq(1+2\epsilon^{\prime})|S^{\prime}|\leq(1+2\epsilon^{\prime})(1+\epsilon^{\prime})\textup{{OPT}}(G)=(1+3\epsilon^{\prime}+2\epsilon^{\prime
2})\textup{{OPT}}(G)\leq(1+5\epsilon^{\prime})\textup{{OPT}}(G)=(1+\epsilon)\textup{{OPT}}(G)$.
Hence, in this case, we get an $(1+\epsilon)$ approximate solution, in time
$2^{\mathcal{O}(1/\epsilon)}n^{\mathcal{O}(1)}$.

This leads to the following theorem.

######  Theorem 10.

Let $\mathcal{H}$ be an apex-minor free graph family. Then, there exists an
FPT-AS for Connected Vertex Cover parameterized by
$\mathbf{mod}_{\mathcal{H}}(\cdot)$ that runs in time
$2^{\mathcal{O}(\mathbf{mod}_{\mathcal{H}}(G)+1/\epsilon)}\cdot
n^{\mathcal{O}(1)}$.

The outline of FPT-AS for Connected Dominating Set is identical to the one
used for Connected Vertex Cover. Here, we need to obtain EPTAS for following
variant of Connected Dominating Set problem, which we call Set Intersecting
Dominating Set. Here, we are given a graph $G^{\prime}$, a set of vertices
$X$, and the objective is to find a minimum sized dominating set, say $Z$,
that dominates all the vertices in $V(G^{\prime})\setminus X$ and every
connected component of $G^{\prime}[Z]$ contains a vertex of $X$. For our case
$G^{\prime}=G-M$ and $X=N(M)$. Fomin et al. [11, Section $4.1$] has shown that
this problem admits an EPTAS, with running time
$2^{\mathcal{O}(1/\epsilon)}n^{\mathcal{O}(1)}$ on apex minor free graphs.
Finally, the result follows from the fact that $\textup{{OPT}}_{{\sf
SIDS}}(G^{\prime})\leq\textup{{OPT}}(G)$,
$\textup{{OPT}}(G)\leq\textup{{OPT}}_{{\sf SIDS}}(G^{\prime})+3|M|$, and that
given a solution $S^{\prime\prime}$ of size $\textup{{OPT}}_{{\sf
SIDS}}(G^{\prime})$, we can construct a connected dominating set of $G$ of
size at most $(|S^{\prime\prime}|+3|M|)$ in polynomial time. This leads to the
following result.

######  Theorem 11.

Let $\mathcal{H}$ be an apex-minor free graph family. Then, there exists an
FPT-AS for Connected Dominating Set parameterized by
$\mathbf{mod}_{\mathcal{H}}(\cdot)$ that runs in time
$2^{\mathcal{O}(\mathbf{mod}_{\mathcal{H}}(G)+1/\epsilon)}\cdot
n^{\mathcal{O}(1)}$.

Using ideas similar to Theorem 9, we can get the following results. The only
place we need to be careful is how to get a connected solution on graph on bad
vertices. This can be achieved with careful book keeping,

######  Theorem 12.

Let $\mathcal{H}$ be a well-behaved family of graphs, and let $\Pi=$Connected
Vertex Cover (Connected Dominating Set). Then, the following statements are
equivalent.

  1. 1.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{mod}_{\mathcal{H}}(\cdot)$
and $\epsilon$.

  2. 2.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{ed}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

  3. 3.

$\Pi$ admits an FPT-AS parameterized by $\mathbf{tw}_{\mathcal{H}}(\cdot)$ and
$\epsilon$.

##  7 Conclusion

In this paper, we have initiated a systematic exploration of the impact that
recently introduced “hybrid” graph parameters have on the existence of good
approximations for fundamental graph problems. In fact, we have shown that as
far as the task of obtaining an FPT-AS is concerned, for many problems,
designing an FPT-AS parameterized by the largest of these, i.e.,
$\mathbf{mod}_{\mathcal{H}}$, is sufficient to obtain an FPT-AS parameterized
by both $\mathbf{ed}_{\mathcal{H}}$ and $\mathbf{tw}_{\mathcal{H}}$ . This
result gives an approximation analogue of recent equivalence obtained between
these parameters in the exact algorithmic setting.

To demonstrate concrete applicability of our techniques, we first designed
FPT-ASes for many classical graph problems parameterized by
$\mathbf{mod}_{\mathcal{H}}$, where $\mathcal{H}$ is an apex/$H$-minor free
graph family. Then, using our equivalence theorems, we are able to lift these
FPT-ASes to $\mathbf{ed}_{\mathcal{H}}$ and $\mathbf{tw}_{\mathcal{H}}$. At
this point, we would like to highlight that, in several concrete applications
of our equivalence theorems, the _non-uniform_ FPT-ASes can be made uniform.
For example, we believe that one can obtain uniform FPT-ASes parameterized by
$\mathbf{mod}_{\mathcal{H}},\mathbf{ed}_{\mathcal{H}}$ and
$\mathbf{tw}_{\mathcal{H}}$ for problems such as Vertex Cover, Feedback Vertex
Set, Independent Set, Dominating Set, Cycle Packing, where $\mathcal{H}$ is an
apex-minor free graph family.

We conclude with two final remarks. Firstly, the assumption of CMSO-
definability can be relaxed. In fact, we only require an EPTAS for the problem
on graphs of bounded treewidth. This would then enable one to apply our
framework to problems that are not CMSO-definable but are known to have good
approximations on the graph family under consideration. Secondly, the initial
step of our algorithm, i.e., FPT-ASes parameterized by
$\mathbf{mod}_{\mathcal{H}}$, can be made to work with other graph families,
such as (Unit) Disk Graphs, using known EPTASes for a number of graph problems
[11, 22].

## References

  * [1] A. Agrawal, L. Kanesh, D. Lokshtanov, F. Panolan, M. S. Ramanujan, S. Saurabh, and M. Zehavi, Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022, pp. 1976–2004.
  * [2] S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, 12 (1991), pp. 308–340.
  * [3] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos, (meta) kernelization, J. ACM, 63 (2016), pp. 44:1–44:69.
  * [4] J. Bulian and A. Dawar, Graph isomorphism parameterized by elimination distance to bounded degree, Algorithmica, 75 (2016), pp. 363–382.
  * [5] B. Courcelle, The monadic second-order logic of graphs. i. recognizable sets of finite graphs, Inf. Comput., 85 (1990), pp. 12–75.
  * [6] M. Cygan, Deterministic parameterized connected vertex cover, in Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, F. V. Fomin and P. Kaski, eds., vol. 7357 of Lecture Notes in Computer Science, Springer, 2012, pp. 95–106.
  * [7] E. D. Demaine, T. D. Goodrich, K. Kloster, B. Lavallee, Q. C. Liu, B. D. Sullivan, A. Vakilian, and A. van der Poel, Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class, in 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, M. A. Bender, O. Svensson, and G. Herman, eds., vol. 144 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 37:1–37:15.
  * [8] R. Diestel, Graph Theory, 4th Edition, vol. 173 of Graduate texts in mathematics, Springer, 2012.
  * [9] A. E. Feldmann, Karthik C. S., E. Lee, and P. Manurangsi, A survey on approximation in parameterized complexity: Hardness and algorithms, Algorithms, 13 (2020), p. 146.
  * [10] F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh, Planar F-deletion: Approximation, kernelization and optimal FPT algorithms, in 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, IEEE Computer Society, 2012, pp. 470–479.
  * [11] F. V. Fomin, D. Lokshtanov, and S. Saurabh, Excluded grid minors and efficient polynomial-time approximation schemes, J. ACM, 65 (2018), pp. 10:1–10:44.
  * [12] F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos, Kernels for (connected) dominating set on graphs with excluded topological minors, ACM Trans. Algorithms, 14 (2018), pp. 6:1–6:31.
  * [13] F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi, Kernelization: theory of parameterized preprocessing, Cambridge University Press, 2019.
  * [14] R. Ganian, M. S. Ramanujan, and S. Szeider, Combining treewidth and backdoors for CSP, in 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, H. Vollmer and B. Vallée, eds., vol. 66 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 36:1–36:17.
  * [15] M. R. Garey and D. S. Johnson, The rectilinear steiner tree problem is NP complete, SIAM Journal of Applied Mathematics, 32 (1977), pp. 826–834.
  * [16] M. X. Goemans and D. P. Williamson, Primal-dual approximation algorithms for feedback problems in planar graphs, Comb., 18 (1998), pp. 37–59.
  * [17] J. Guo, F. Hüffner, and R. Niedermeier, A structural view on parameterizing problems: Distance from triviality, in Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings, R. G. Downey, M. R. Fellows, and F. K. H. A. Dehne, eds., vol. 3162 of Lecture Notes in Computer Science, Springer, 2004, pp. 162–173.
  * [18] B. M. P. Jansen and J. J. H. de Kroon, FPT algorithms to compute the elimination distance to bipartite graphs and more, in Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers, L. Kowalik, M. Pilipczuk, and P. Rzazewski, eds., vol. 12911 of Lecture Notes in Computer Science, Springer, 2021, pp. 80–93.
  * [19] B. M. P. Jansen, J. J. H. de Kroon, and M. Wlodarczyk, Vertex deletion parameterized by elimination distance and even less, in STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, S. Khuller and V. V. Williams, eds., ACM, 2021, pp. 1757–1769.
  * [20] , 5-approximation for $\mathscr{h}$-treewidth essentially as fast as $\mathscr{h}$-deletion parameterized by solution size, in 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, I. L. Gørtz, M. Farach-Colton, S. J. Puglisi, and G. Herman, eds., vol. 274 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 66:1–66:16.
  * [21] D. Lokshtanov, A. E. Mouawad, S. Saurabh, and M. Zehavi, Packing cycles faster than erdos-posa, SIAM J. Discret. Math., 33 (2019), pp. 1194–1215.
  * [22] D. Lokshtanov, F. Panolan, S. Saurabh, J. Xue, and M. Zehavi, A framework for approximation schemes on disk graphs, in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, N. Bansal and V. Nagarajan, eds., SIAM, 2023, pp. 2228–2241.
  * [23] D. Marx, Parameterized complexity and approximation algorithms, Comput. J., 51 (2008), pp. 60–78.
  * [24] L. Morelle, I. Sau, G. Stamoulis, and D. M. Thilikos, Faster parameterized algorithms for modification problems to minor-closed classes, in 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, K. Etessami, U. Feige, and G. Puppis, eds., vol. 261 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 93:1–93:19.
  * [25] B. A. Reed, K. Smith, and A. Vetta, Finding odd cycle transversals, Oper. Res. Lett., 32 (2004), pp. 299–301.

##  Appendix A Background on FII and Proof of Lemma 3

The material from Section A.1 to Section A.3 is largely borrowed verbatim from
[1].

###  A.1 Boundaried Graphs

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

######  Definition 8.

[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 9.

[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 10.

[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 11.

[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).$

###  A.2 Finite Integer Index

######  Definition 12.

[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 13.

[Progressive representatives [3]] 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.$ (21)

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

######  Lemma 13 ([3]).

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 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}}$.

###  A.3 Replacement lemma

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

######  Definition 15.

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 16.

([12, 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