$\gamma$-witnessed by $v$. Define $I$ as the set of all indices $i\in[r]$ such
that all vertices in $V_{i}$ are smaller than or equal to $v$ under the
ordering $\sigma$. For each $i\in[r]$, let $v_{i}\in V_{i}$ be the largest
vertex under $\sigma$. Note that $v_{1},\dots,v_{r}$ are distinct as
$V_{1},\dots,V_{r}$ are disjoint. Observe that
$v_{i}\in\text{WR}_{2\gamma}(G_{1},\sigma,v)$ for all $i\in[r]\backslash I$.
Indeed, as $V_{i}$ is $\gamma$-witnessed by $v$, there exists $u_{i}\in
N_{G_{1}}[V_{i}]$ such that $v\in\text{WR}_{\gamma}(G_{1},\sigma,u_{i})$. So
there is a path $\pi_{i}$ in $G_{1}$ of length at most $\gamma$ between $v$
and $u_{i}$, on which the largest vertex is $v$. Let $u_{i}^{\prime}\in V_{i}$
be the vertex neighboring to $u_{i}$, and $\pi_{i}^{\prime}$ be a simple path
in $G_{1}[V_{i}]$ between $u_{i}^{\prime}$ and $v_{i}$, which exists since
$G_{1}[V_{i}]$ is connected. Concatenating $\pi_{i}$ and $\pi_{i}^{\prime}$
gives a path $\pi_{i}^{*}$ in $G_{1}$ between $v$ and $v_{i}$ of length at
most $\gamma+|V_{i}|\leq 2\gamma$. Now $v$ is the largest vertex on $\pi_{i}$
and $v_{i}$ is the largest vertex on $\pi_{i}^{\prime}$. If $i\in[r]\backslash
I$, then $v_{i}\geq_{\sigma}v$ and $v_{i}$ is the largest vertex on
$\pi_{i}^{*}$, which implies $v_{i}\in\text{WR}_{2\gamma}(G_{1},\sigma,v)$. It
follows that
$r-|I|\leq|\text{WR}_{2\gamma}(G_{1},\sigma,v)|\leq\mathsf{wcol}_{2\gamma}(G_{1},\sigma)=\mathsf{wcol}_{2\gamma}(G_{1})$.
Equivalently, we have $|I|\geq r-\mathsf{wcol}_{2\gamma}(G_{1})$. For each
$i\in I$, we have $v\geq_{\sigma}v_{i}$ and thus $v\geq_{\sigma}x$ for all
$x\in V_{i}$, which implies $v\in\text{WR}_{2\gamma}(G_{1},\sigma,x)$ for all
$x\in V_{i}$, because one can concatenate $\pi_{i}$ and a simple path from
$u_{i}^{\prime}$ to $x$ in $G[V_{i}]$ to obtain a path between $v$ and $x$ of
length at most $\gamma+|V_{i}|\leq 2\gamma$ on which $v$ is the largest
vertex. Using the fact $|I|\geq r-\mathsf{wcol}_{2\gamma}(G_{1})$, we see that
$v$ $\gamma$-witnesses $r-\mathsf{wcol}_{2\gamma}(G_{1})$ disjoint sets
$V\in\mathcal{V}\Cap V(G_{1})$ such that
$v\in\text{WR}_{2\gamma}(G_{1},\sigma,x)$ for all $x\in V$.

To prove the lemma, let $A\subseteq V(G_{1})$ be a minimum hitting set of
$\mathcal{V}\Cap V(G_{1})$. As argued above, each vertex $v\in B$
$\gamma$-witnesses $r^{\prime}=r-\mathsf{wcol}_{2\gamma}(G_{1})$ disjoint sets
$V_{1},\dots,V_{r^{\prime}}\in\mathcal{V}\Cap V(G_{1})$ such that
$v\in\text{WR}_{2\gamma}(G_{1},\sigma,x)$ for all
$x\in\bigcup_{i=1}^{r^{\prime}}V_{i}$. Note that each $V_{i}$ contains at
least one vertex $a_{i}\in A$. The vertices $a_{1},\dots,a_{r^{\prime}}$ are
distinct as $V_{1},\dots,V_{r^{\prime}}$ are disjoint. We charge $v$ to the
vertices $a_{1},\dots,a_{r^{\prime}}$. In this way, each vertex in $B$ is
charged to $r^{\prime}$ (distinct) vertices in $A$. Also, whenever we charge a
vertex $v\in B$ to a vertex $a\in A$, we have
$v\in\text{WR}_{2\gamma}(G_{1},\sigma,a)$. Thus, each vertex in $A$ gets
charged at most
$|\text{WR}_{2\gamma}(G_{1},\sigma,a)|\leq\mathsf{wcol}_{2\gamma}(G_{1})$
times. It follows that
$r^{\prime}\cdot|B|\leq\mathsf{wcol}_{2\gamma}(G_{1})\cdot|A|$, which implies

$|B|\leq\frac{\mathsf{wcol}_{2\gamma}(G_{1})}{r-\mathsf{wcol}_{2\gamma}(G_{1})}\cdot|A|\leq
p\cdot|A|=p\cdot\mathsf{opt}(G_{1}),$

because $r=\lceil\frac{1+p}{p}\cdot\mathsf{wcol}_{2\gamma}(G_{1})\rceil$. ∎

By applying the above lemma with $p=\frac{\varepsilon}{4}$, we see that the
number of vertices in $G_{1}$ that $\gamma$-witness
$\lceil\frac{4+\varepsilon}{\varepsilon}\cdot\mathsf{wcol}_{2\gamma}(G_{1})\rceil$
disjoint sets in $\mathcal{V}\Cap V(G_{1})$ is bounded
$\frac{\varepsilon}{4}\cdot\mathsf{opt}(G_{1})$. Therefore, if we can
guarantee that every vertex in $V^{*}$ $\gamma$-witness
$\lceil\frac{4+\varepsilon}{\varepsilon}\cdot\mathsf{wcol}_{2\gamma}(G_{1})\rceil$
disjoint sets in $\mathcal{V}\Cap V(G_{1})$, then we have
$|V^{*}|\leq\frac{\varepsilon}{4}\cdot\mathsf{opt}(G_{1})$. The rest of this
section is dedicated to showing that every vertex in $G_{1}$ either
$\gamma$-witness (at least) $\delta$ disjoint sets in $\mathcal{V}\Cap
V(G_{1})$ or has degree at most $O_{\varepsilon,\mathcal{F}}(1)$. Note that if
this is the case, then we can choose
$\delta\geq\lceil\frac{4+\varepsilon}{\varepsilon}\cdot\mathsf{wcol}_{2\gamma}(G_{1})\rceil$
and a proper threshold $\delta^{\prime}=O_{\varepsilon,\mathcal{F}}(1)$ to
make every vertex in $V^{*}$ $\gamma$-witness
$\lceil\frac{4+\varepsilon}{\varepsilon}\cdot\mathsf{wcol}_{2\gamma}(G_{1})\rceil$
disjoint sets in $\mathcal{V}\Cap V(G_{1})$.

For the rest of the subsection, fix a vertex $v\in V(G_{1})$. Recall the set
$R$ computed in line 2 of Algorithm 1. The set $N_{G_{1}}(\\{v\\})$ of
neighbors of $v$ in $G_{1}$ can be partitioned into two subsets,
$N_{G_{1}}(\\{v\\})\backslash R$ and $N_{G_{1}}(\\{v\\})\cap R$. Note that any
vertex $u\in N_{G_{1}}(\\{v\\})\cap R$ must satisfy
$\varGamma_{G}^{*}\subseteq\varGamma_{G_{1}-\\{u\\}}$, for otherwise it cannot
survive in $G_{1}$: it will be removed from $G_{1}$ during the while-loop in
line 4-5. We write
$\mathsf{deg}_{G_{1}}^{\prime}(v)=|N_{G_{1}}(\\{v\\})\backslash R|$ and
$\mathsf{deg}_{G_{1}}^{\prime\prime}(v)=|N_{G_{1}}(\\{v\\})\cap R|$. Then
$\mathsf{deg}_{G_{1}}(v)=\mathsf{deg}_{G_{1}}^{\prime}(v)+\mathsf{deg}_{G_{1}}^{\prime\prime}(v)$.
We shall show that if $v$ does not $\gamma$-witness $\delta$ disjoint sets in
$\mathcal{V}\Cap V(G_{1})$, then
$\mathsf{deg}_{G_{1}}^{\prime}(v)=O_{\varepsilon,\mathcal{F}}(1)$ and
$\mathsf{deg}_{G_{1}}^{\prime\prime}(v)=O_{\varepsilon,\mathcal{F}}(1)$. The
part for $\mathsf{deg}_{G_{1}}^{\prime}(v)$ is relatively easy, which follows
from the lemma below.

######  Lemma 4.9.

If
$\mathsf{deg}_{G_{1}}^{\prime}(v)\geq\gamma(\delta\gamma^{\gamma})^{\gamma}\gamma!$,
then $v$ $0$-witnesses $\delta\gamma^{\gamma}$ disjoint sets in
$\mathcal{V}\Cap V(G_{1})$.

###### Proof.

Suppose $N_{G_{1}}(\\{v\\})\backslash R=\\{v_{1},\dots,v_{k}\\}$, where
$k=\mathsf{deg}_{G_{1}}^{\prime}(v)$. Assume
$k\geq\gamma(\delta\gamma^{\gamma})^{\gamma}\gamma!$. For each $i\in[k]$,
since $v_{i}\notin R$, there exists $V_{i}\in\mathcal{V}$ such that $v_{i}\in
V_{i}$ and $V_{i}$ does not contain any set in $\varGamma_{G}$. We have
$V_{i}\cap R=\emptyset$, as the existence of $V_{i}$ prevents any vertex in
$V_{i}$ to be contained in $R$. Since $V(G)\backslash V(G_{1})\subseteq R$,
this implies $V_{i}\in\mathcal{V}\Cap V(G_{1})$. Furthermore, $v$
$0$-witnesses $V_{i}$, simply because $v_{i}\in V_{i}$ and thus $v\in
N_{G_{1}}[V_{i}]$. Note that the sets $V_{1},\dots,V_{k}$ are not necessarily
distinct, i.e., it can happen that $V_{i}=V_{j}$ for different $i,j\in[k]$.
However, for each $V\in\mathcal{V}\Cap V(G_{1})$, there can be at most
$\gamma$ indices $i\in[k]$ such that $V=V_{i}$, since $|V|\leq\gamma$ and
$v_{i}\in V$ for all $i\in[k]$ with $V=V_{i}$. Therefore, among
$V_{1},\dots,V_{k}$, there are at least $k/\gamma$ distinct sets, i.e.,
$|\\{V_{1},\dots,V_{k}\\}|\geq k/\gamma$. By the sunflower lemma (Lemma 3.1),
there is a $\lfloor(\frac{k/\gamma}{\gamma!})^{-\gamma}\rfloor$-sunflower in
$\\{V_{1},\dots,V_{k}\\}$. Let $X$ be the core of this sunflower. We claim
that $X=\emptyset$. Since $k\geq\gamma(\delta\gamma^{\gamma})^{\gamma}\gamma!$
by assumption, the size of the sunflower is at least $\delta\gamma^{\gamma}$.
It follows that $X$ is the core of a $\delta\gamma^{|X|}$-sunflower in
$\mathcal{V}\Cap V(G_{1})$, because
$\delta\gamma^{\gamma}\geq\delta\gamma^{|X|}$. If $X\neq\emptyset$, then by
definition $X$ is a heavy set in $G_{1}$ and thus $X\in\varGamma_{G_{1}}$.
However, this contradicts the fact that none of $V_{1},\dots,V_{k}$ contains a
set in $\varGamma_{G}$. Therefore, $X=\emptyset$ and the sets in the sunflower
are disjoint. So we find
$\lfloor(\frac{k/\gamma}{\gamma!})^{-\gamma}\rfloor\geq\delta\gamma^{\gamma}$
disjoint sets in $\mathcal{V}\Cap V(G_{1})$ which are $0$-witnessed by $v$. ∎

Next, we do the part for $\mathsf{deg}_{G_{1}}^{\prime\prime}(v)$, i.e.,
showing that
$\mathsf{deg}_{G_{1}}^{\prime\prime}(v)=O_{\varepsilon,\mathcal{F}}(1)$ if $v$
does not $\gamma$-witness $\delta$ disjoint sets in $\mathcal{V}\Cap
V(G_{1})$. We first show that if $v$ $\gamma$-witnesses too many sets in
$\varGamma_{G_{1}}^{*}$, then $v$ must $\gamma$-witnesses $\delta$ disjoint
sets in $\mathcal{V}\Cap V(G_{1})$. To this end, we need the following key
observation which states that a single vertex cannot hit too many minimal
heavy sets.

######  Lemma 4.10.

For any subgraph $H$ of $G$, every vertex in $H$ hits at most
$(\delta\gamma^{\gamma})^{\gamma}\gamma!$ sets in $\varGamma_{H}^{*}$.

###### Proof.

We prove the lemma by contradiction. Suppose there exists $u\in V(H)$ that
hits more than $(\delta\gamma^{\gamma})^{\gamma}\gamma!$ sets in
$\varGamma_{H}^{*}$. We use $\varGamma_{u}\subseteq\varGamma_{H}^{*}$ to
denote the collection of sets in $\varGamma_{H}^{*}$ hit by $u$. Since
$|\varGamma_{u}|>(\delta\gamma^{\gamma})^{\gamma}\gamma!$, by the sunflower
lemma (Lemma 3.1), there exists a $\delta\gamma^{\gamma}$-sunflower in
$\varGamma_{u}$. Let $\\{X_{1},\dots,X_{k}\\}$ be this sunflower where
$k=\delta\gamma^{\gamma}$, and $X$ be its core. Note that $X\neq\emptyset$
because $u\in X$. Also, $|X|<\gamma$, since if $|X|=\gamma$, then
$X=X_{1}=\dots=X_{k}$, implying $k=1$. We shall show that $X\in\varGamma_{H}$,
which contradicts the fact that $X_{1},\dots,X_{k}\in\varGamma_{H}^{*}$, i.e.,
$X_{1},\dots,X_{k}$ are minimal sets in $\varGamma_{H}$. It suffices to find a
$\delta\gamma^{|X|}$-sunflower in $\mathcal{V}\Cap V(H)$ whose core is $X$.
Let $\\{V_{1},\dots,V_{r}\\}\subseteq\mathcal{V}\Cap V(H)$ be a maximal
sunflower with core $X$. We claim that $r\geq\delta\gamma^{|X|}$. Set
$X_{i}^{\prime}=X_{i}\backslash X$ for all $i\in[k]$ and
$V_{i}^{\prime}=V_{i}\backslash X$ for all $i\in[r]$. Note that
$X_{1}^{\prime},\dots,X_{k}^{\prime}$ are disjoint and
$V_{1}^{\prime},\dots,V_{r}^{\prime}$ are disjoint. If
$\bigcup_{i=1}^{r}V_{i}^{\prime}$ hits all of
$X_{1}^{\prime},\dots,X_{k}^{\prime}$, then
$\sum_{i=1}^{r}|V_{i}^{\prime}|\geq k$, which implies $r\geq
k/\gamma=\delta\gamma^{\gamma-1}$, because
$X_{1}^{\prime},\dots,X_{k}^{\prime}$ are disjoint and
$|V_{i}^{\prime}|\leq\gamma$ for all $i\in[r]$. In this case,
$r\geq\delta\gamma^{\gamma-1}\geq\delta\gamma^{|X|}$ and we are done.
Otherwise, $\bigcup_{i=1}^{r}V_{i}^{\prime}$ does not hit all of
$X_{1}^{\prime},\dots,X_{k}^{\prime}$, and we may assume
$(\bigcup_{i=1}^{r}V_{i}^{\prime})\cap X_{1}^{\prime}=\emptyset$ without loss
of generality. Since $X_{1}\in\varGamma_{H}^{*}$, there exists a
$\delta\gamma^{|X_{1}|}$-sunflower in $\mathcal{V}\Cap V(H)$ with core
$X_{1}$. Let $\\{U_{1},\dots,U_{s}\\}$ be this sunflower where
$s=\delta\gamma^{|X_{1}|}$. Set $U_{i}^{\prime}=U_{i}\backslash X_{1}$ for all
$i\in[s]$. Clearly, $U_{1}^{\prime},\dots,U_{s}^{\prime}$ are disjoint. Note
that $\bigcup_{i=1}^{r}V_{i}^{\prime}$ hits all of
$U_{1}^{\prime},\dots,U_{s}^{\prime}$. Indeed, if
$\bigcup_{i=1}^{r}V_{i}^{\prime}$ does not hit $U_{j}^{\prime}$ for some
$j\in[s]$, then $\\{V_{1},\dots,V_{r},U_{j}\\}$ is a sunflower in
$\mathcal{V}\Cap V(H)$ with core $X$ (because $U_{j}=X\sqcup
X_{1}^{\prime}\sqcup U_{j}^{\prime}$ and $\bigcup_{i=1}^{r}V_{i}^{\prime}$
does not hit $X_{1}^{\prime}\sqcup U_{j}^{\prime}$), which contradicts the
maximality of the sunflower $\\{V_{1},\dots,V_{r}\\}$. It follows that
$\sum_{i=1}^{r}|V_{i}^{\prime}|\geq s$, as
$U_{1}^{\prime},\dots,U_{s}^{\prime}$ are disjoint. Therefore, $r\geq
s/\gamma=\delta\gamma^{|X_{1}|-1}\geq\delta\gamma^{|X|}$. Now
$\\{V_{1},\dots,V_{r}\\}$ is a sunflower of size at least $\delta\gamma^{|X|}$
with core $X$, which implies $X\in\varGamma_{H}$ and contradicts the fact that
$X_{1},\dots,X_{k}\in\varGamma_{H}^{*}$. This contradiction completes the
proof. ∎

######  Corollary 4.11.

If $v$ $\gamma$-witnesses $(\delta\gamma^{\gamma})^{\gamma+1}\gamma!$ sets in
$\varGamma_{G_{1}}^{*}$ (not necessarily disjoint), then it $\gamma$-witnesses
$\delta$ disjoint sets in $\mathcal{V}\Cap V(G_{1})$.

###### Proof.

Set $k=(\delta\gamma^{\gamma})^{\gamma+1}\gamma!$ and denote by
$X_{1},\dots,X_{k}\in\varGamma_{G_{1}}^{*}$ the $k$ sets that are
$\gamma$-witnessed by $v$. Let $\mathcal{V}^{\prime}\subseteq\mathcal{V}\Cap
V(G_{1})$ consist of the sets $\gamma$-witnessed by $v$. Our goal to show that
there exist $\delta$ disjoint sets in $\mathcal{V}^{\prime}$. As all sets in
$\mathcal{V}^{\prime}$ are of size at most $\gamma$, the size of a minimum
hitting set of $\mathcal{V}^{\prime}$ is at most $\gamma$ times the maximum
number of disjoint sets in $\mathcal{V}^{\prime}$. So it suffices to show that
every hitting set of $\mathcal{V}^{\prime}$ is of size at least
$\delta\gamma$. Consider a hitting set $A$ of $\mathcal{V}^{\prime}$. If $A$
hits all of $X_{1},\dots,X_{k}$, then applying Lemma 4.10 with $H=G_{1}$
implies that $|A|\geq
k/((\delta\gamma^{\gamma})^{\gamma}\gamma!)\geq\delta\gamma$. If $A$ does not
hit all of $X_{1},\dots,X_{k}$, assume $X_{1}\cap A=\emptyset$ without loss of
generality. Since $X_{1}\in\varGamma_{G_{1}}^{*}\subseteq\varGamma_{G_{1}}$,
there exists a $\delta\gamma^{|X_{1}|}$-sunflower in $\mathcal{V}\Cap
V(G_{1})$ with core $X_{1}$. Note that all sets in this sunflower are
$\gamma$-witnessed by $v$ and thus contained in $\mathcal{V}^{\prime}$,
because they contain $X_{1}$ as a subset. Thus, the $\delta\gamma^{|X_{1}|}$
sets in the sunflower are all hit by $A$. However, $X_{1}\cap A=\emptyset$,
which implies $|A|\geq\delta\gamma^{|X_{1}|}\geq\delta\gamma$. As a result,
the size of a minimum hitting set of $\mathcal{V}^{\prime}$ is at least
$\delta\gamma$, and there exist $\delta$ disjoint sets in
$\mathcal{V}^{\prime}$. ∎

The above corollary tells us that if $v$ does not $\gamma$-witnesses $\delta$
disjoint sets in $\mathcal{V}\Cap V(G_{1})$, then it can $\gamma$-witness at
most $(\delta\gamma^{\gamma})^{\gamma+1}\gamma!$ sets in
$\varGamma_{G_{1}}^{*}$. This allows us to bound
$\mathsf{deg}_{G_{1}}^{\prime\prime}(v)$ using representative sets. Let $K$ be
the union of $\text{WR}_{\gamma}(G_{1},\sigma,v)$ and all sets in
$\varGamma_{G_{1}}^{*}$ that are $\gamma$-witnessed by $v$. We now define an
equivalence relation $\sim$ over the subsets of $V(G_{1})\backslash K$ as
follows. For two sets $V,V^{\prime}\subseteq V(G_{1})\backslash K$, we set
$V\sim V^{\prime}$ iff there exists an isomorphism $\phi:K\sqcup V\rightarrow
K\sqcup V^{\prime}$ of the graphs $G_{1}[K\sqcup V]$ and $G_{1}[K\sqcup
V^{\prime}]$ such that $\phi_{|K}$ is the identity map on $K$. It is clear
that $\sim$ is an equivalence relation. For every integer $i\geq 0$, define
$P_{i}=\\{u\in V(G_{1})\backslash K:v\in\text{WR}_{i}(G_{1},\sigma,u)\\}$ and
$\mathcal{P}_{i}=\\{P\subseteq P_{i}:|P|\leq\gamma\\}$. Clearly, we have
$P_{i}\subseteq P_{j}$ if $i\leq j$. For each $i\in[\gamma]$ and each
equivalence class $\mathcal{C}$ of $\mathcal{P}_{i}$ under $\sim$, we take a
$\delta\gamma^{\gamma}$-representative set of $\mathcal{C}$ of size
$(\delta\gamma^{\gamma}+\gamma)^{\gamma}$; the existence of such a
representative set is implied by Lemma 3.2. Define $Q$ as the union of $K$ and
all these representative sets. In the next lemma, we prove a key property of
the set $Q$.

######  Lemma 4.12.

Let $\mathcal{L}\subseteq\mathcal{V}\Cap V(G_{1})$ be an $r$-sunflower with
core $X\in\varGamma_{G_{1}}^{*}$, where $r\leq\delta\gamma^{\gamma-1}$. Then
for any $V\in\mathcal{L}$, there exists some set $V^{\prime}\in\mathcal{V}\Cap
V(G_{1})$ such that $V^{\prime}\cap N_{G_{1}}(\\{v\\})\subseteq Q$ and
$(\mathcal{L}\backslash\\{V\\})\cup\\{V^{\prime}\\}$ is also an $r$-sunflower
with core $X$.

###### Proof.

Let $\mathcal{L}$ be the sunflower as in the lemma (with core
$X\in\varGamma_{G_{1}}^{*}$), and consider a set $V\in\mathcal{L}$. Define $k$
as the smallest index such that $V\cap(P_{k+1}\backslash P_{k})=\emptyset$.
Note that $k$ exists and $k\leq\gamma$, because the sets $P_{1}\backslash
P_{0},P_{2}\backslash P_{1},\dots,P_{\gamma+1}\backslash P_{\gamma}$ are
disjoint. Observe that $P_{k}\cap X=\emptyset$. Indeed, if $X$ contains a
vertex $u\in P_{k}$, then $X$ is $k$-witnessed by $v$ because $u\in
N_{G_{1}}[X]$ and $v\in\text{WR}_{k}(G_{1},\sigma,u)$, which further implies
$X\subseteq K$ as $k\leq\gamma$. On the other hand, we have $P_{k}\cap
K=\emptyset$ by construction and thus $u\notin K$, which contradicts the fact
$X\subseteq K$. Thus, $P_{k}\cap X=\emptyset$.

Now we define $U=V\cap P_{k}$. As $P_{k}\cap X=\emptyset$, we have $U\cap
X=\emptyset$ and thus $U\subseteq V\backslash X$. Since $|U|\leq|V|\leq\gamma$
and $U\subseteq P_{k}$, we have $U\in\mathcal{P}_{k}$. So $U$ is contained in
a (unique) equivalence class $\mathcal{C}$ of $\mathcal{P}_{k}$ under $\sim$.
By construction, $Q$ contains a $\delta\gamma^{\gamma}$-representative set of
$\mathcal{C}$, which we denote by
$\mathcal{C}_{\mathsf{rep}}\subseteq\mathcal{C}$. Let $Z$ be the union of all
sets in $\mathcal{L}\backslash\\{V\\}$. Note that $U\cap Z=\emptyset$, because
$U\subseteq V\backslash X$ and $\mathcal{L}$ is a sunflower with core $X$.
Also note that $|Z|\leq\delta\gamma^{\gamma}$, since
$|\mathcal{L}|\leq\delta\gamma^{\gamma-1}$ by assumption and each set in
$\mathcal{L}$ is of size at most $\gamma$. Therefore, there exists
$U^{\prime}\in\mathcal{C}_{\mathsf{rep}}$ such that $U^{\prime}\cap
Z=\emptyset$. We then define $V^{\prime}=(V\backslash U)\cup U^{\prime}$. We
shall show that $V^{\prime}$ is the desired set in the lemma.

First, $(\mathcal{L}\backslash\\{V\\})\cup\\{V^{\prime}\\}$ is clearly a
sunflower with core $X$, as $U\subseteq V\backslash X$ and $U^{\prime}\cap
Z=\emptyset$. Furthermore, we observe that $V^{\prime}\cap
N_{G_{1}}(\\{v\\})\subseteq Q$. To see this, consider a vertex $v^{\prime}\in
V^{\prime}\cap N_{G_{1}}(\\{v\\})$. If $v^{\prime}\in U^{\prime}$, then
$v^{\prime}\in Q$ since $Q$ contains all sets in $\mathcal{C}_{\mathsf{rep}}$
and in particular contains $U^{\prime}$. If $v^{\prime}\notin U^{\prime}$,
then we must have $v^{\prime}\in V\backslash U$. In this case,
$v^{\prime}\notin P_{k}$ because $U=V\cap P_{k}$. Since $v^{\prime}\in
N_{G_{1}}(\\{v\\})$, this further implies $v^{\prime}>_{\sigma}v$, for
otherwise $v^{\prime}\in P_{1}\subseteq P_{k}$. Thus,
$v^{\prime}\in\text{WR}_{1}(G_{1},\sigma,v)\subseteq K\subseteq U$,
contradicting the fact $v^{\prime}\in V\backslash U$. So we have
$V^{\prime}\cap N_{G_{1}}(\\{v\\})\subseteq Q$. Finally, we show that
$G_{1}[V]$ and $G_{1}[V^{\prime}]$ are isomorphic. Note that this implies
$V^{\prime}\in\mathcal{V}\Cap V(G_{1})$ since $V\in\mathcal{V}\Cap V(G_{1})$,
which completes the proof. Set $W=(V\backslash U)\backslash K$.

Claim 1. $V=W\sqcup(V\cap K)\sqcup U$ and $V^{\prime}=W\sqcup(V\cap K)\sqcup
U^{\prime}$.

Proof of Claim 1. We have $V\backslash U=W\sqcup((V\backslash U)\cap
K)=W\sqcup(V\cap K)$, simply because $U\subseteq P_{k}$ and thus $U\cap
K=\emptyset$. Therefore, $V=W\sqcup(V\cap K)\sqcup U$. Besides, as
$U^{\prime}\subseteq P_{k}$ and $(V\backslash U)\cap P_{k}=\emptyset$, we have
$(V\backslash U)\cap U^{\prime}=\emptyset$. It follows that
$V^{\prime}=W\sqcup(V\cap K)\sqcup U^{\prime}$. $\lhd$

Since $U$ and $U^{\prime}$ belong to the same equivalence class $\mathcal{C}$
of $\mathcal{P}_{k}$ under $\sim$, there exists an isomorphism $\phi:K\sqcup
U\rightarrow K\sqcup U^{\prime}$ between $G_{1}[K\sqcup U]$ and $G_{1}[K\sqcup
U^{\prime}]$ such that $\phi_{|K}$ is the identity map on $K$. Note that
$\phi$ induces a bijection between $U$ and $U^{\prime}$. We then define a map
$\psi:V\rightarrow V^{\prime}$ by setting $\psi(u)=u$ for all $u\in
W\sqcup(V\cap K)$ and $\psi(u)=\phi(u)$ for all $u\in U$. By Claim 1 and the
fact that $\phi$ induces a bijection between $U$ and $U^{\prime}$, we know
that $\psi$ is a bijection between $V$ and $V^{\prime}$. We further show that
$\psi$ is in fact an isomorphism between $G_{1}[V]$ and $G_{1}[V^{\prime}]$.
To this end, the key observation is the following claim.

Claim 2. $N_{G_{1}}(P_{k})\cap W=\emptyset$. In particular, $N_{G_{1}}(U)\cap
W=\emptyset$ and $N_{G_{1}}(U^{\prime})\cap W=\emptyset$.

Proof of Claim 2. If $k=\gamma$, then $V\cap(P_{i+1}\backslash
P_{i})\neq\emptyset$ for all $i<\gamma$, and thus

$|U|=|V\cap P_{\gamma}|=\sum_{i=0}^{\gamma-1}|V\cap(P_{i+1}\backslash
P_{i})|\geq\gamma.$

In this case, we must have $U=V$ as $|V|\leq\gamma$, which implies
$W=\emptyset$ by Claim 1 and thus $N_{G_{1}}(P_{k})\cap W=\emptyset$. Now
assume $k<\gamma$. Let $u\in P_{k}$ and $u^{\prime}\in N_{G_{1}}(P_{k})$. What
we want is $u^{\prime}\notin W$. If $u^{\prime}\notin V$, we are done. So we
can suppose $u^{\prime}\in V$. In this case, we have $u^{\prime}\in
V\backslash U$, since $u^{\prime}\notin P_{k}$ and $U=V\cap P_{k}$. Recall our
assumption that $V\cap(P_{k+1}\backslash P_{k})=\emptyset$, which implies
$(V\backslash U)\cap P_{k+1}=\emptyset$. Thus, $u^{\prime}\notin P_{k+1}$.
Note that this in turn implies $u^{\prime}>_{\sigma}v$. Indeed, if
$u^{\prime}\leq_{\sigma}v$, then we have
$v\in\text{WR}_{k+1}(G_{1},\sigma,u^{\prime})$ and thus $u^{\prime}\in
P_{k+1}$, simply because $v\in\text{WR}_{k}(G_{1},\sigma,u)$ and
$(u,u^{\prime})\in E(G_{1})$. Since $v\in\text{WR}_{k}(G_{1},\sigma,u)$, there
exists a path $\pi$ between $u$ and $v$ of length at most $k$ on which all
vertices are smaller than or equal to $v$ under the $\sigma$ ordering.
Concatenating $\pi$ with the edge $(u,u^{\prime})$ gives us a path
$\pi^{\prime}$ between $u^{\prime}$ and $v$ of length at most $k+1$. All
vertices on $\pi^{\prime}$ are smaller than or equal to $u^{\prime}$ under the
$\sigma$ ordering, because $u^{\prime}>_{\sigma}v$. So we have
$u^{\prime}\in\text{WR}_{k+1}(G_{1},\sigma,v)$. It follows that
$u^{\prime}\in\text{WR}_{\gamma}(G_{1},\sigma,v)$, as $k<\gamma$ by our
assumption. Therefore, $u^{\prime}\in K$ and $u^{\prime}\notin W$.

To see $N_{G_{1}}(U)\cap W=\emptyset$ and $N_{G_{1}}(U^{\prime})\cap
W=\emptyset$, simply notice that $N_{G_{1}}(U)\subseteq N_{G_{1}}(P_{k})\cup
P_{k}$ and $N_{G_{1}}(U^{\prime})\subseteq N_{G_{1}}(P_{k})\cup P_{k}$. As
shown above, $N_{G_{1}}(P_{k})\cap W=\emptyset$. Also, $P_{k}\cap W\subseteq
P_{k}\cap(V\backslash U)=\emptyset$. Therefore, $N_{G_{1}}(U)\cap W=\emptyset$
and $N_{G_{1}}(U^{\prime})\cap W=\emptyset$. $\lhd$

Consider two vertices $x,y\in V$. We want to show that $(x,y)\in E(G_{1})$ iff
$(\psi(x),\psi(y))\in E(G_{1})$. Note that $\psi$ is the identity map when
restricted to $W\sqcup(V\cap K)$. So if $x,y\in W\sqcup(V\cap K)$, we have
$(x,y)\in E(G_{1})$ iff $(\psi(x),\psi(y))\in E(G_{1})$. On the other hand,
$\psi$ is identical to $\phi$ when restricted to $(V\cap K)\sqcup U$. By
assumption, $\phi$ is an isomorphism between $G_{1}[K\cup U]$ and $G_{1}[K\cup
U^{\prime}]$. Thus, if $x,y\in(V\cap K)\sqcup U$, we have $(x,y)\in E(G_{1})$
iff $(\psi(x),\psi(y))\in E(G_{1})$. The only remaining case is that one of
$x,y$ is in $W$ and the other is in $U$, say $x\in W$ and $y\in U$ without
loss of generality. In this case, $\psi(x)=x\in W$ and $\psi(y)\in
U^{\prime}$. By Claim 2, we have $(x,y)\notin E(G_{1})$ and
$(\psi(x),\psi(y))\notin E(G_{1})$. Therefore, $\psi$ is an isomorphism
between $G_{1}[V]$ and $G_{1}[V^{\prime}]$. As $V\in\mathcal{V}$, we have
$V^{\prime}\in\mathcal{V}$. It follows that $V^{\prime}\in\mathcal{V}\Cap
V(G_{1})$ since $V^{\prime}\subseteq V(G_{1})$, which completes the proof. ∎

The good property of $Q$ given in the above lemma guarantees that if we remove
from $G_{1}$ any neighbor of $v$ that is not in $Q$, all sets in
$\varGamma_{G_{1}}^{*}$ remain heavy in the resulting graph. This further
implies that any vertex in $N_{G_{1}}(\\{v\\})\backslash Q$ that is also in
$R$ should not survive in $G_{1}$, and hence $N_{G_{1}}(\\{v\\})\cap
R\subseteq Q$. More precisely, we have the following corollary.

######  Corollary 4.13.

For any $u\in N_{G_{1}}(\\{v\\})\backslash Q$, we have
$\varGamma_{G_{1}}^{*}\subseteq\varGamma_{G_{1}-\\{u\\}}$. Thus,
$N_{G_{1}}(\\{v\\})\cap R\subseteq Q$.

###### Proof.

Let $u\in N_{G_{1}}(\\{v\\})\backslash Q$. For each
$X\in\varGamma_{G_{1}}^{*}$, we want to show that
$X\in\varGamma_{G_{1}-\\{u\\}}$, i.e., $X$ is still heavy in $G_{1}-\\{u\\}$.
As $X\in\varGamma_{G_{1}}^{*}$, there exists a $\delta\gamma^{|X|}$-sunflower
$\mathcal{L}\subseteq\mathcal{V}\Cap V(G_{1})$ with core $X$. Note that
$|X|\leq\gamma-1$ since all sets in $\mathcal{L}$ are of size at most
$\gamma$. If $u$ is not contained in any set in $\mathcal{L}$, we are done.
Indeed, in this case, $\mathcal{L}$ is a sunflower in $\mathcal{V}\Cap
V(G_{1}-\\{u\\})$, which implies $X\in\varGamma_{G_{1}-\\{u\\}}$. So suppose
$u\in V$ for some $V\in\mathcal{L}$. By Lemma 4.12, there exists
$V^{\prime}\in\mathcal{V}\Cap V(G_{1})$ such that $V^{\prime}\cap
N_{G_{1}}(\\{v\\})\subseteq Q$ and
$(\mathcal{L}\backslash\\{V\\})\cup\\{V^{\prime}\\}$ is also a
$\delta\gamma^{|X|}$-sunflower with core $X$. Since $V^{\prime}\cap
N_{G_{1}}(\\{v\\})\subseteq Q$ and $u\in N_{G_{1}}(\\{v\\})\backslash Q$, we
have $u\notin V^{\prime}$ and hence $u\notin X$. It follows that $u\in
V\backslash X$ and thus $u$ is not contained in any set in
$\mathcal{L}\backslash\\{V\\}$, for $\mathcal{L}$ is a sunflower with core
$X$. Therefore, $(\mathcal{L}\backslash\\{V\\})\cup\\{V^{\prime}\\}$ is a
sunflower in $\mathcal{V}\Cap V(G_{1}-\\{u\\})$, which implies
$X\in\varGamma_{G_{1}-\\{u\\}}$. ∎

Recall that $\mathsf{deg}_{G_{1}}^{\prime\prime}(v)=|N_{G_{1}}(\\{v\\})\cap
R|$. By the above corollary, to bound
$\mathsf{deg}_{G_{1}}^{\prime\prime}(v)$, it suffices to bound the size of
$Q$. In our construction, $Q$ consists of $K$ and several representative sets
of equivalence classes of $\mathcal{P}_{i}$ under $\sim$ for $i\in[\gamma]$.
It is easy to see that $|Q|$ only depends on $|K|$ and the numbers
$\delta,\gamma$. To obtain a good bound, we exploit the bounded neighbor-
complexity of $\mathcal{G}$ given in Theorem 3.8. Let $c_{\mathcal{G}}$ be the
constant in Theorem 3.8.

######  Lemma 4.14.

Each $\mathcal{P}_{i}$ contains at most $\gamma(c_{\mathcal{G}}|K|\cdot
2^{\gamma})^{\gamma}$ equivalence classes under $\sim$ for $i\in[\gamma]$,
which implies
$\mathsf{deg}_{G_{1}}^{\prime\prime}(v)\leq|Q|\leq|K|+\gamma^{2}(\delta\gamma^{\gamma}+\gamma)^{\gamma}(c_{\mathcal{G}}|K|\cdot
2^{\gamma})^{\gamma}$. Therefore, if $v$ does not $\gamma$-witness $\delta$
disjoint sets in $\mathcal{V}\Cap V(G_{1})$, then
$\mathsf{deg}_{G_{1}}^{\prime\prime}(v)\leq\mathsf{wcol}_{2\gamma}(G_{1})+(c_{\mathcal{G}}(\delta\gamma^{\gamma})^{\gamma+1}\gamma!\cdot
2^{\gamma})^{3\gamma}$.

###### Proof.

Let $\mathcal{P}_{i,j}=\\{P\in\mathcal{P}_{i}:|P|=j\\}$ for $j\in[\gamma]$.
Then $\mathcal{P}_{i}=\bigcup_{j=1}^{\gamma}\mathcal{P}_{i,j}$. Note that two
subsets of $V(G_{1})$ are equivalent under $\sim$ only if they have the same
size. Thus, every equivalence class of $\mathcal{P}_{i}$ is also an
equivalence class of $\mathcal{P}_{i,j}$ for some $j\in[\gamma]$. So it
suffices to bound the number of equivalence classes of $\mathcal{P}_{i,j}$.
Suppose $K=\\{v_{1},\dots,v_{k}\\}$ where $k=|K|$. We map each
$V\in\mathcal{P}_{i,j}$ to a $j\times(k+j)$ binary matrix $M_{V}$ as follows.
We arbitrarily label the $j$ vertices in $V$ by $k+1,\dots,k+j$ and thus
$V=\\{v_{k+1},\dots,v_{k+j}\\}$. Then define $M_{V}(p,q)=1$ if
$(v_{k+p},v_{q})\in E(G_{1})$ and $M_{V}(p,q)=0$ if $(v_{k+p},v_{q})\notin
E(G_{1})$, for $p\in[j]$ and $q\in[k+j]$. We observe that for two sets
$V,V^{\prime}\in\mathcal{P}_{i,j}$, if $M_{V}=M_{V^{\prime}}$, then $V\sim
V^{\prime}$. To see this, suppose $V=\\{v_{k+1},\dots,v_{k+j}\\}$ and
$V^{\prime}=\\{v_{k+1}^{\prime},\dots,v_{k+j}^{\prime}\\}$ under the labeling
for defining $M_{V}$ and $M_{V^{\prime}}$. Define a map $\phi:K\sqcup
V\rightarrow K\sqcup V^{\prime}$ by setting $\phi(v_{t})=v_{t}$ for $t\in[k]$
and $\phi(v_{t})=v_{t}^{\prime}$ for $t\in[k+j]\backslash[k]$. Clearly,
$\phi_{|K}$ is the identity map on $K$. Also, according to the fact
$M_{V}=M_{V^{\prime}}$, one can easily check that the map $\phi:K\sqcup
V\rightarrow K\sqcup V^{\prime}$ gives us an isomorphism between
$G_{1}[K\sqcup V]$ and $G_{1}[K\sqcup V^{\prime}]$. Thus, $V\sim V^{\prime}$.

Based on the above observation, it suffices to bound the number of different
matrices $M_{V}$ for $V\in\mathcal{P}_{i,j}$. Consider one row of the matrix
$M_{V}$, which corresponds to one vertex $u\in V$. The first $k$ entries of
the row are determined by $N_{G_{1}}(\\{u\\})\cap K$. By Theorem 3.8, there
are at most $c_{\mathcal{G}}|K|$ possibilities of $N_{G_{1}}(\\{u\\})\cap K$.
The last $j$ entries of the row has at most $2^{j}$ possibilities. Therefore,
the total number of possibilities of one row is bounded by
$c_{\mathcal{G}}|K|\cdot 2^{j}$. As there are $j$ rows in a matrix, the number
of different matrices $M_{V}$ for $V\in\mathcal{P}_{i,j}$ is at most
$(c_{\mathcal{G}}|K|\cdot 2^{j})^{j}$, so is the number of equivalence classes
of $\mathcal{P}_{i,j}$ under $\sim$. It follows that the number of equivalence
classes of $\mathcal{P}_{i}$ under $\sim$ is at most
$\sum_{j=1}^{\gamma}(c_{\mathcal{G}}|K|\cdot 2^{j})^{j}$, which is in turn
bounded by $\gamma(c_{\mathcal{G}}|K|\cdot 2^{\gamma})^{\gamma}$.

In each equivalence class $\mathcal{C}$ of $\mathcal{P}_{i}$, $Q$ contains the
union of a $\delta\gamma^{\gamma}$-representative set
$\mathcal{C}_{\mathsf{rep}}\subseteq\mathcal{C}$ where
$|\mathcal{C}_{\mathsf{rep}}|\leq\binom{\delta\gamma^{\gamma}+\gamma}{\gamma}\leq(\delta\gamma^{\gamma}+\gamma)^{\gamma}$.
The union of the sets in $\mathcal{C}_{\mathsf{rep}}$ is of size at most
$\gamma(\delta\gamma^{\gamma}+\gamma)^{\gamma}$. As shown above, each
$\mathcal{P}_{i}$ has at most $\gamma(c_{\mathcal{G}}|K|\cdot
2^{\gamma})^{\gamma}$ equivalence classes. Therefore, the union of the
representative sets of all equivalence classes of all $\mathcal{P}_{i}$ is of
size at most
$\gamma^{2}(\delta\gamma^{\gamma}+\gamma)^{\gamma}(c_{\mathcal{G}}|K|\cdot
2^{\gamma})^{\gamma}$. Since $Q$ is the union of $K$ and these representative
sets,
$|Q|\leq|K|+\gamma^{2}(\delta\gamma^{\gamma}+\gamma)^{\gamma}(c_{\mathcal{G}}|K|\cdot
2^{\gamma})^{\gamma}$. The fact
$\mathsf{deg}_{G_{1}}^{\prime\prime}(v)\leq|Q|$ directly follows from
Corollary 4.13. Finally, if $v$ does not $\gamma$-witness $\delta$ disjoint
sets in $\mathcal{V}\Cap V(G_{1})$, then $v$ $\gamma$-witnesses at most
$(\delta\gamma^{\gamma})^{\gamma+1}\gamma!$ sets in $\varGamma_{G_{1}}^{*}$ by
Corollary 4.11. In this case, by the construction of $K$, we have

$|K|\leq|\text{WR}_{\gamma}(G_{1},\sigma,v)|+\gamma(\delta\gamma^{\gamma})^{\gamma+1}\gamma!\leq\mathsf{wcol}_{2\gamma}(G_{1})+\gamma(\delta\gamma^{\gamma})^{\gamma+1}\gamma!,$

because
$|\text{WR}_{\gamma}(G_{1},\sigma,v)|\leq\mathsf{wcol}_{\gamma}(G_{1},\sigma)\leq\mathsf{wcol}_{2\gamma}(G_{1},\sigma)=\mathsf{wcol}_{2\gamma}(G_{1})$
by the choice of the ordering $\sigma$. Combining this with the bound for
$|Q|$ obtained above, we conclude that if $v$ does not $\gamma$-witness
$\delta$ disjoint sets in $\mathcal{V}\Cap V(G_{1})$, then

$\displaystyle\mathsf{deg}_{G_{1}}^{\prime\prime}(v)\leq|Q|$
$\displaystyle\leq\mathsf{wcol}_{2\gamma}(G_{1})+\gamma(\delta\gamma^{\gamma})^{\gamma+1}\gamma!+\gamma^{2}(\delta\gamma^{\gamma}+\gamma)^{\gamma}(c_{\mathcal{G}}(\delta\gamma^{\gamma})^{\gamma+1}\gamma!\cdot
2^{\gamma})^{\gamma}$
$\displaystyle\leq\mathsf{wcol}_{2\gamma}(G_{1})+(c_{\mathcal{G}}(\delta\gamma^{\gamma})^{\gamma+1}\gamma!\cdot
2^{\gamma})^{3\gamma},$

which completes the proof. ∎

######  Lemma 4.15.

For every vertex $v\in V(G_{1})$, either $v$ $\gamma$-witnesses $\delta$
disjoint sets in $\mathcal{V}\Cap V(G_{1})$ or
$\mathsf{deg}_{G_{1}}(v)<\gamma(\delta\gamma^{\gamma})^{\gamma}\gamma!+\mathsf{wcol}_{2\gamma}(G_{1})+(c_{\mathcal{G}}(\delta\gamma^{\gamma})^{\gamma+1}\gamma!\cdot
2^{\gamma})^{3\gamma}$.

###### Proof.

Suppose $v$ does not $\gamma$-witness $\delta$ disjoint sets in
$\mathcal{V}\Cap V(G_{1})$. By Lemma 4.9,
$\mathsf{deg}_{G_{1}}^{\prime}(v)<\gamma(\delta\gamma^{\gamma})^{\gamma}\gamma!$.
Furthermore, by Lemma 4.14, we have
$\mathsf{deg}_{G_{1}}^{\prime\prime}(v)\leq\mathsf{wcol}_{2\gamma}(G_{1})+(c_{\mathcal{G}}(\delta\gamma^{\gamma})^{\gamma+1}\gamma!\cdot
2^{\gamma})^{3\gamma}$. So
$\mathsf{deg}_{G_{1}}(v)=\mathsf{deg}_{G_{1}}^{\prime}(v)+\mathsf{deg}_{G_{1}}^{\prime\prime}(v)<\gamma(\delta\gamma^{\gamma})^{\gamma}\gamma!+\mathsf{wcol}_{2\gamma}(G_{1})+(c_{\mathcal{G}}(\delta\gamma^{\gamma})^{\gamma+1}\gamma!\cdot
2^{\gamma})^{3\gamma}$. ∎

######  Corollary 4.16.

If
$\delta\geq\lceil\frac{4+\varepsilon}{\varepsilon}\cdot\mathsf{wcol}_{2\gamma}(G_{1})\rceil$
and
$\delta^{\prime}\geq\gamma(\delta\gamma^{\gamma})^{\gamma}\gamma!+\mathsf{wcol}_{2\gamma}(G_{1})+(c_{\mathcal{G}}(\delta\gamma^{\gamma})^{\gamma+1}\gamma!\cdot
2^{\gamma})^{3\gamma}$, then
$|V^{*}|\leq\frac{\varepsilon}{4}\cdot\mathsf{opt}(G_{1})$ and thus
$|S_{1}|\leq(1+\frac{\varepsilon}{2})\cdot\mathsf{opt}(G_{1})$.

###### Proof.

Suppose
$\delta\geq\lceil\frac{4+\varepsilon}{\varepsilon}\cdot\mathsf{wcol}_{2\gamma}(G_{1})\rceil$
and
$\delta^{\prime}\geq\gamma(\delta\gamma^{\gamma})^{\gamma}\gamma!+\mathsf{wcol}_{2\gamma}(G_{1})+(c_{\mathcal{G}}(\delta\gamma^{\gamma})^{\gamma+1}\gamma!\cdot
2^{\gamma})^{3\gamma}$. Then by Lemma 4.15, every vertex in $V^{*}$
$\gamma$-witnesses
$\lceil\frac{4+\varepsilon}{\varepsilon}\cdot\mathsf{wcol}_{2\gamma}(G_{1})\rceil$
disjoint sets in $\mathcal{V}\Cap V(G_{1})$. Further applying Lemma 4.8, we
have $|V^{*}|\leq\frac{\varepsilon}{4}\cdot\mathsf{opt}(G_{1})$. As
$|S_{1}|=|S_{2}|+|V^{*}|$ and
$|S_{2}|\leq(1+\frac{\varepsilon}{4})\cdot\mathsf{opt}(G_{2})\leq(1+\frac{\varepsilon}{4})\cdot\mathsf{opt}(G_{1})$,
we finally have
$|S_{1}|\leq(1+\frac{\varepsilon}{2})\cdot\mathsf{opt}(G_{1})$. ∎

###  4.4 Linear-time implementation

In this section, we show how to implement Algorithm 1 (except the call of the
sub-routine $\textsc{Hitting}^{\prime}$ in line 8) in linear time, or more
precisely, $O_{\varepsilon,\mathcal{F}}(n)$ time. Note that if this can be
done, then the overall time complexity of Algorithm 1 is
$f(\varepsilon,\mathcal{F})\cdot n^{c}$ time for some function $f$, because
line 8 takes $f_{0}(\varepsilon,\mathcal{F},\Delta)\cdot n^{c}$ time where
$\Delta$ is the maximum degree of $G_{2}$ which is bounded by
$\delta^{\prime}=O_{\varepsilon,\mathcal{F}}(1)$. We divide Algorithm 1 into
two parts: the part for computing $G_{2}$ (line 1-7) and the part for
computing $S$ (line 9-13). We discuss these two parts in the following two
sections.

####  4.4.1 Computing $G_{2}$

Consider line 1-7 of Algorithm 1. The sets defined in line 1 are not computed
explicitly. It suffices to implement line 2 and the while-loop in line 4-5 in
linear time. The key idea here is to formulate the computation tasks as first-
order model-checking problems, and properly apply the efficient data structure
of Theorem 3.10. The following lemma shows that line 2 can be done in linear
time.

######  Lemma 4.17.

Let $R$ be the set defined in line 2 of Algorithm 1. Whether a vertex $v\in
V(G)$ is in $R$ can be expressed as a first-order formula $\varphi(v)$ whose
length depends only on $\varepsilon$ and $\mathcal{F}$. Thus, $R$ can be
computed in $f(\varepsilon,\mathcal{F})\cdot n$ time for some function $f$.

###### Proof.

Towards the presentation of the formula to check the membership of $v$ in $R$,
we first present several simpler formulas that will be used as building
blocks. Recall that for two vertices $u,u^{\prime}\in V(G)$,
$\mathsf{Adj}(u,u^{\prime})$ is the atomic formula that is true if and only if
$u$ and $u^{\prime}$ are adjacent in $G$. We start with some simple formulas.

  * •

For every $\ell\in\mathbb{N}$,
$\mathsf{Distinct}(v_{1},v_{2},\ldots,v_{\ell})$: True iff
$v_{1},v_{2},\ldots,v_{\ell}$ are distinct. Defined as follows:

$\bigwedge_{i,j\in[\ell],i\neq j}v_{i}\neq v_{j}.$

  * •

For every $r,\ell\in\mathbb{N}$,
$\mathsf{Subset}(u_{1},u_{2},\ldots,u_{r},v_{1},v_{2},\ldots,v_{\ell})$: True
iff
$\\{u_{1},u_{2},\ldots,u_{r}\\}\subseteq\\{v_{1},v_{2},\ldots,v_{\ell}\\}$.
Defined as follows:

$\bigwedge_{i\in[r]}\left(\bigvee_{j\in[\ell]}u_{i}=v_{j}\right).$

For every $F\in{\cal F}$, we arbitrary order $V(F)$, denoted by
$V(F)=\\{v^{F}_{1},v^{F}_{2},\ldots,v^{F}_{|V(F)|}\\}$. We proceed to formulas
to check isomorphism.

  * •

For every $F\in{\cal F}$,
$F$-$\mathsf{Isomorphic}(v_{1},v_{2},\ldots,v_{\ell})$ where $\ell=|V(F)|$:
True iff $G[\\{v_{1},v_{2},\ldots,v_{\ell}\\}]$ contains a spanning subgraph
isomorphic to $F$ where the isomorphism maps $v_{i}$ to $v^{F}_{i}$ for every
$i\in[\ell]$. Defined as follows:

$\mathsf{Distinct}(v_{1},v_{2},\ldots,v_{\ell})\wedge\left(\bigwedge_{i,j\in[\ell],\\{v^{F}_{i},v^{F}_{j}\\}\in
E(F)}\mathsf{Adj}(v_{i},v_{j})\right).$

  * •

For every $F\in{\cal F}$,
$F$-$\mathsf{Isomorphic}^{\mathsf{in}}(v_{1},v_{2},\ldots,v_{\ell})$ where
$\ell=|V(F)|$: True iff $G[\\{v_{1},v_{2},\ldots,v_{\ell}\\}]$ is isomorphic
to $F$ where the isomorphism maps $v_{i}$ to $v^{F}_{i}$ for every
$i\in[\ell]$. Defined as follows:

$\mathsf{Distinct}(v_{1},v_{2},\ldots,v_{\ell})\wedge\left(\bigwedge_{i,j\in[\ell],\\{v^{F}_{i},v^{F}_{j}\\}\in
E(F)}\mathsf{Adj}(v_{i},v_{j})\right)\wedge\left(\bigwedge_{i,j\in[\ell],\\{v^{F}_{i},v^{F}_{j}\\}\notin
E(F)}\neg\mathsf{Adj}(v_{i},v_{j})\right).$

  * •

For every $\ell\in\mathbb{N}$, $\mathsf{BelongsTo}{\cal V}_{\cal
F}(v_{1},v_{2},\ldots,v_{\ell})$: True iff
$G[\\{v_{1},v_{2},\ldots,v_{\ell}\\}]$ contains a spanning subgraph isomorphic
to some graph $F\in{\cal F}$ where the isomorphism maps $v_{i}$ to $v^{F}_{i}$
for every $i\in[\ell]$. Defined as follows:

$\bigvee_{F\in{\cal
F},|V(F)|=\ell}F\mathrm{-}\mathsf{Isomorphic}(v_{1},v_{2},\ldots,v_{\ell}).$

Now, we present formulas to check heaviness.

  * •

For every $\ell\in\mathbb{N}$, $\mathsf{Heavy}(v_{1},v_{2},\ldots,v_{\ell})$:
True iff $\\{v_{1},v_{2},\ldots,v_{\ell}\\}$ is a heavy set w.r.t. Subgraph
Hitting. Defined as follows, where $x=\delta\gamma^{\ell}$:

$\begin{array}[]{l}\bigvee_{f:[x]\rightarrow[\gamma]}(\exists
u^{1}_{1},u^{1}_{2},\ldots,u^{1}_{f}(1),u^{2}_{1},u^{2}_{2},\ldots,u^{2}_{f}(2),\ldots,u^{x}_{1},u^{x}_{2},\ldots,u^{x}_{f}(x)\\\
\bigwedge_{i\in[x]}(\mathsf{BelongsTo}{\cal V}_{\cal
F}(u^{i}_{1},u^{i}_{2},\ldots,u^{i}_{f(i)})\wedge\mathsf{Subset}(v_{1},v_{2},\ldots,v_{\ell},u^{i}_{1},u^{i}_{2},\ldots,u^{i}_{f(i)}))\\\
\wedge\bigwedge_{i,j\in[x],i\neq
j,k\in[f(i)]}(\mathsf{Subset}(u^{i}_{k},v_{1},v_{2},\ldots,v_{\ell})\vee\neg\mathsf{Subset}(u^{i}_{k},u^{j}_{1},u^{j}_{2},\ldots,u^{j}_{f(j)})).\end{array}$

We remark that, here, we use $\mathsf{Subset}$ to check the membership of an
element (the first argument) in a set.

  * •

For every $\ell\in\mathbb{N}$,
$\mathsf{ContainsHeavy}(v_{1},v_{2},\ldots,v_{\ell})$: True iff
$\\{v_{1},v_{2},\ldots,v_{\ell}\\}$ contains a heavy set w.r.t. Subgraph
Hitting. Defined as follows:

$\bigvee_{r\in[\ell]}\left(\exists
u_{1},u_{2},\ldots,u_{r}\mathsf{Distinct}(u_{1},\ldots,u_{r})\wedge\mathsf{Subset}(u_{1},\ldots,u_{r},v_{1},\ldots,v_{\ell})\wedge\mathsf{Heavy}(u_{1},\ldots,u_{r})\right).$

We are now ready to present the formula to check whether $v\in R$. We start
with Subgraph Hitting:

$\bigwedge_{\ell\in[\gamma]}\left(\forall
v_{1},v_{2},\ldots,v_{\ell}\bigvee_{i\in[\ell]}(v=v_{i})\wedge\left(\mathsf{BelongsTo}{\cal
V}_{\cal
F}(v_{1},v_{2},\ldots,v_{\ell})\rightarrow\mathsf{ContainsHeavy}(v_{1},v_{2},\ldots,v_{\ell})\right)\right).$

For Induced Subgraph Hitting, the required formula is identical except that
every use of $F$-$\mathsf{Isomorphic}(v_{1},v_{2},\ldots,v_{\ell})$ is
replaced by the use of
$F$-$\mathsf{Isomorphic}^{\mathsf{in}}(v_{1},v_{2},\ldots,v_{\ell})$.

We have seen how to construct a first-order formula $\phi(v)$ such that $v\in
R$ iff $\phi(v)$ is true. Define $Q=V(G)$ as a unary relation on $V(G)$, and
set $\varphi=\exists v(\phi(v)\wedge Q(v))$. We build in $O(n)$ time the data
structure $\mathcal{D}$ of Theorem 3.10 on the graph $G$ with the unary
relation $Q$ and the first-order formula $\varphi$. We then delete all
elements from $Q$ and keep updating $\mathcal{D}$. As there are $n$ elements
to be deleted and each update takes $f(|\varphi|)$ time, this step takes
$f(|\varphi|)\cdot n$ time. To compute $R$, we iteratively consider the
vertices of $G$. For a vertex $v\in V(G)$, to check whether $v\in R$, we add
back $v$ to $Q$ and then test whether $(G,Q)$ satisfies the formula $\varphi$.
As $Q=\\{v\\}$ at this point, $(G,Q)$ satisfies $\varphi$ iff $v\in R$. After
this, we delete $v$ from $Q$ and move to the next vertex. The time cost for
considering each vertex is $f(|\varphi|)$ by Theorem 3.10. Therefore, the
overall running time is $f(|\varphi|)\cdot n$. Since $|\varphi|$ only depends
on $\varepsilon$ and $\mathcal{F}$, we can compute $R$ in
$f(\varepsilon,\mathcal{F})\cdot n$ time. ∎

Next, we consider the while-loop in line 4-5 of Algorithm 1.

######  Lemma 4.18.

For a subgraph $H$ of $G$, whether a vertex $v\in V(H)$ satisfies
$\varGamma_{H}^{*}\subseteq\varGamma_{H-\\{v\\}}$ can be expressed as a first-
order formula whose length depends only on $\varepsilon$ and $\mathcal{F}$.
Thus, the while-loop in line 4-5 of Algorithm 1 can be done in
$f(\varepsilon,\mathcal{F})\cdot n$ time for some function $f$.

###### Proof.

Observe that we need to check that there does not exist a minimal heavy set in
$H$ that contains $v$. We let the variables correspond to vertices in $H$
(rather than $G$). We will use formulas introduced in the proof of Lemma 4.17.
Now, we can directly present the required formula.

$\bigwedge_{\ell\in[\gamma]}\forall
v_{1},v_{2},\ldots,v_{\ell}\left((v=v_{1}\wedge\mathsf{Heavy}(v_{1},v_{2},\ldots,v_{\ell}))\rightarrow\bigvee_{i\in[\ell]}\mathsf{Heavy}(v_{1},\ldots,v_{i-1},v_{i+1},\ldots,v_{\ell})\right).$

In line 3 of Algorithm 1, we set $G_{1}=G$. Let $\phi(v)$ be the above formula
defined on $G_{1}$ that checks whether
$\varGamma_{G_{1}}^{*}\subseteq\varGamma_{G_{1}-\\{v\\}}$. Define $Q=V(G_{1})$
as a unary relation on $V(G_{1})$, and set $\varphi=\exists v(\phi(v)\wedge
Q(v))$. We build in $O(n)$ time the data structure $\mathcal{D}$ of Theorem
3.10 on the graph $G_{1}$ with the unary relation $Q$ and the first-order
formula $\varphi$. As what we did in the proof of Lemma 4.17, we delete all
elements from $Q$ and keep updating $\mathcal{D}$, which takes
$f(|\varphi|)\cdot n$ time. Now to test whether a vertex $v\in V(G_{1})$
satisfies $\varGamma_{G_{1}}^{*}\subseteq\varGamma_{G_{1}-\\{v\\}}$, we only
need to add $v$ back to $Q$ and check whether $(G_{1},Q)$ satisfies $\varphi$
(and delete $v$ from $Q$ afterwards). Thus, we can test whether
$\varGamma_{G_{1}}^{*}\subseteq\varGamma_{G_{1}-\\{v\\}}$ for any vertex $v\in
V(G_{1})$ in $f(|\varphi|)$ time. During the while-loop in line 4-5 of
Algorithm 1, we keep removing vertices from $G_{1}$. Note that the data
structure $\mathcal{D}$ only supports edge deletions. Therefore, when we want
to delete a vertex $v$ from $G_{1}$ in line 5, instead of truly deleting $v$
itself, we delete all edges incident to $v$ from $G_{1}$. In this way, $v$
still exists in $G_{1}$ but becomes an isolated vertex. This is in fact
equivalent to deleting $v$ from $G_{1}$, because the forbidden patterns in
$\mathcal{F}$ are all connected (and thus isolated vertices do not influence
anything). The time cost for updating $\mathcal{D}$ after each edge-deletion
is $f(|\varphi|)$. As each edge can be deleted at most once, the total update
time of $\mathcal{D}$ during the while-loop is $f(|\varphi|)\cdot n$ due to
the sparsity of $G_{1}$. Using $\mathcal{D}$, if we implement the while-loop
in line 4-5 of Algorithm 1 straightforwardly, it takes quadratic time, because
in each iteration we need to check for each $v\in V(G_{1})\cap R$ whether
$\varGamma_{G_{1}}^{*}\subseteq\varGamma_{G_{1}-\\{v\\}}$. To achieve linear
running time, we observe that if a vertex $v$ does not satisfy the condition
$\varGamma_{G_{1}}^{*}\subseteq\varGamma_{G_{1}-\\{v\\}}$ in one iteration of
the loop, then it does not satisfy the condition in all following iterations.
Indeed, $G_{1}$ becomes smaller and smaller during the while-loop, so does
$\varGamma_{G_{1}-\\{v\\}}$. On the other hand, $\varGamma_{G_{1}}^{*}$ never
changes and is always equal to $\varGamma_{G}^{*}$ by Fact 4.5. Therefore, if
$\varGamma_{G_{1}}^{*}\nsubseteq\varGamma_{G_{1}-\\{v\\}}$ at one point, then
$\varGamma_{G_{1}}^{*}\nsubseteq\varGamma_{G_{1}-\\{v\\}}$ afterwards. Based
on this observation, every vertex of $G$ only needs to be checked once during
the loop, which takes $f(|\varphi|)$ time. So the entire while-loop takes
$f(|\varphi|)\cdot n$ time. Since $|\varphi|$ only depends on $\varepsilon$
and $\mathcal{F}$, we can implement the loop in
$f(\varepsilon,\mathcal{F})\cdot n$ time. ∎

By the above two lemmas, line 1-7 can be implemented in
$f(\varepsilon,\mathcal{F})\cdot n$ time.

####  4.4.2 Computing $S$

Consider line 9-14 in Algorithm 1. By Theorem 3.9, line 9 can be done in
$O(n)$ time. So it suffices to show how to compute $\rho_{v}$ for all $v\in
V(G)$ (line 10) in linear time. The key here is an efficient algorithm for
computing the weakly reachable sets.

######  Lemma 4.19.

Let $G$ be a graph of $n$ vertices and $m$ edges. Given an ordering $\sigma$
of $V(G)$ and $r\in[n]$, one can compute in
$O(n+rm\cdot\mathsf{wcol}_{r}(G,\sigma))$ time the sets
$\textnormal{WR}_{r}(G,\sigma,v)$ for all $v\in V(G)$.

###### Proof.

Without loss of generality, we can assume $G$ is connected and thus
$m=\Omega(n)$. We shall compute the sets $\textnormal{WR}_{i}(G,\sigma,v)$
iteratively for $i=0,1,\dots,r$. We have
$\textnormal{WR}_{0}(G,\sigma,v)=\\{v\\}$ for all $v\in V(G)$. Suppose the
sets $\textnormal{WR}_{i-1}(G,\sigma,v)$ are already computed for all $v\in
V(G)$. To compute $\textnormal{WR}_{i}(G,\sigma,v)$, the key observation is
that $\textnormal{WR}_{i}(G,\sigma,v)$ consists of exactly the vertices in
$\bigcup_{u\in N[v]}\textnormal{WR}_{i-1}(G,\sigma,u)$ which are larger than
or equal to $v$ under the ordering $\sigma$; here $N[v]$ is the set of
neighbors of $v$ in $G$ (including $v$ itself). Indeed, if
$x\in\textnormal{WR}_{i}(G,\sigma,v)$, then there exists a path
$(u_{0}=v,u_{1},\dots,u_{i}=x)$ in $G$ on which $x$ is the largest vertex
under the ordering $\sigma$. We have $u_{1}\in N[v]$ and
$x\in\textnormal{WR}_{i-1}(G,\sigma,u_{1})$ because of the sub-path
$(u_{1},\dots,u_{i})$. Thus, $x\in\bigcup_{u\in
N[v]}\textnormal{WR}_{i-1}(G,\sigma,u)$ and $x\geq_{\sigma}v$. On the other
hand, if $x\in\textnormal{WR}_{i-1}(G,\sigma,u)$ for some $u\in N[v]$ and
$x\geq_{\sigma}v$, then there exists a path $(u_{1}=u,\dots,u_{i}=x)$ in $G$
on which $x$ is the largest vertex. In this case, $(v,u_{1},\dots,u_{i})$ is a
path between $v$ and $x$ on which $x$ is the largest vertex, and thus
$x\in\textnormal{WR}_{i}(G,\sigma,v)$. With this observation, to compute
$\textnormal{WR}_{i}(G,\sigma,v)$, we only need to check all vertices in
$\bigcup_{u\in N[v]}\textnormal{WR}_{i-1}(G,\sigma,u)$ and take the ones
larger than $v$, which can be done in
$O(|N[v]|\cdot\mathsf{wcol}_{r}(G,\sigma))$ time because
$|\textnormal{WR}_{i-1}(G,\sigma,u)|\leq\mathsf{wcol}_{i-1}(G,\sigma)\leq\mathsf{wcol}_{r}(G,\sigma)$.
Since $\sum_{v\in V(G)}|N[v]|=O(m)$, computing
$\textnormal{WR}_{i}(G,\sigma,v)$ for all $v\in V(G)$ takes
$O(m\cdot\mathsf{wcol}_{r}(G,\sigma))$ time. We need $r$ iterations to compute
$\textnormal{WR}_{r}(G,\sigma,v)$, so the overall running time is
$O(rm\cdot\mathsf{wcol}_{r}(G,\sigma))$. ∎

To do line 10 in Algorithm 1, we first apply the above lemma to compute
$\textnormal{WR}_{\gamma}(G,\sigma,u)$ for all $u\in V(G)$. Note that
$G\in\mathcal{G}$ and $\mathcal{G}$ is of bounded expansion. Thus, $G$ has
$O(n)$ edges. Furthermore, by Theorem 3.9, we have
$\mathsf{wcol}_{\gamma}(G,\sigma)\leq\mathsf{wcol}_{\gamma}^{\gamma+1}(G)$. By
Theorem 3.7, $\mathsf{wcol}_{\gamma}(G)$ is bounded by
$\chi_{\mathcal{G}}(\gamma)$ for a function $\chi_{\mathcal{G}}$, and thus
$\mathsf{wcol}_{\gamma}(G,\sigma)$ is also bounded by a function of $\gamma$.
As such applying the above lemma takes $O_{\gamma}(n)$ time. After the sets
$\textnormal{WR}_{\gamma}(G,\sigma,u)$ are computed, it is straightforward to
compute all $\rho_{v}$ in $O(\sum_{u\in
V(G)}|\textnormal{WR}_{\gamma}(G,\sigma,u)|)$ time. Note that
$|\textnormal{WR}_{\gamma}(G,\sigma,u)|\leq\mathsf{wcol}_{\gamma}(G,\sigma)\leq\mathsf{wcol}_{\gamma}^{\gamma+1}(G)\leq\chi_{\mathcal{G}}^{\gamma}(\gamma)$
for all $u\in V(G)$. Thus, computing all $\rho_{v}$ takes $O_{\gamma}(n)$
time.

###  4.5 Putting everything together

We pick
$\delta>\frac{2+2\varepsilon}{\varepsilon}\cdot\mathsf{wcol}_{\gamma}^{\gamma+1}(G)+\lceil\frac{4+\varepsilon}{\varepsilon}\cdot\mathsf{wcol}_{2\gamma}(G_{1})\rceil$,
which satisfies the conditions in Corollary 4.7 and 4.16. We then further pick
a sufficiently large $\delta^{\prime}$ that satisfies the condition in
Corollary 4.16. As the weak coloring numbers of $G$ and $G_{1}$ are all
bounded, we can guarantee that $\delta=O_{\varepsilon,\mathcal{F}}(1)$ and
$\delta^{\prime}=O_{\varepsilon,\mathcal{F}}(1)$. Here a small technical issue
is that we cannot compute the weak coloring numbers of $G$ and $G_{1}$
efficiently. However, we can use the admissibility numbers to approximate the
weak coloring numbers. The $r$-admissibility number of $G$,
$\mathsf{adm}_{r}(G)$, satisfies the inequality
$\mathsf{adm}_{r}(G)\leq\mathsf{wcol}_{r}(G)\leq\mathsf{adm}_{r}^{r+1}(G)$
[45]. Furthermore, the $r$-admissibility number of bounded-expansion graphs
can be computed in $O(n)$ time for any $r\geq 0$ [45]. As such, when picking
$\delta$ and $\delta^{\prime}$, we can simply use the upper bound of the weak
coloring numbers provided by admissibility numbers to ensure that $\delta$ and
$\delta^{\prime}$ are sufficiently large while on the other hand still bounded
by $O_{\varepsilon,\mathcal{F}}(1)$. (We omit the definition of admissibility
numbers, as it is not used in the paper.)

Next, we consider the overall running time of Algorithm 1. As shown in Section
4.4, all steps except line 8 can be done in $f(\varepsilon,\mathcal{F})\cdot
n$ time. Since $G_{2}$ is of maximum degree at most
$\delta^{\prime}=O_{\varepsilon,\mathcal{F}}(1)$, line 8 takes
$f(\varepsilon,\mathcal{F})\cdot n^{c}$ time. As such, the time complexity of
Algorithm 1 is $f(\varepsilon,\mathcal{F})\cdot n^{c}$. Combining this with
the reduction in Section 4.1 (Corollary 4.3) completes the proof of Theorem
1.1.

##### Variants.

When the provided degree-sensitive algorithm in Theorem 1.1 has a different
running time or a different approximation factor, the performance of the
algorithm we obtain also changes. Therefore, the same proof can also result in
variants of Theorem 1.1. For example, when the provided algorithm has an
approximation factor $c+\varepsilon$, then we also obtain a
$(c+\varepsilon)$-approximation algorithm. Also, when the provided algorithm
has running time $n^{f_{0}(\varepsilon,\mathcal{F},\Delta)}$,
$f_{0}(\varepsilon,\mathcal{F},\Delta)\cdot n^{g(\varepsilon)}$, and
$f_{0}(\varepsilon,\mathcal{F},\Delta)\cdot n^{g(\mathcal{F})}$, the obtained
algorithm has running time $n^{f(\varepsilon,\mathcal{F})}$,
$f(\varepsilon,\mathcal{F})\cdot n^{g(\varepsilon)}$, and
$f(\varepsilon,\mathcal{F})\cdot n^{g(\mathcal{F})}$, respectively. We believe
that these variants can also find their applications in the future.

##  5 Applications

In this section, we discussion the applications of Theorem 1.1.

###  5.1 Graphs of polynomial expansion

We first apply Theorem 1.1 to graphs of polynomial expansion. To this end, we
need to introduce an important notion called strongly sublinear separator.

######  Definition 5.1.

Let $G$ be an $n$-vertex graph. A vertex subset $X\subseteq V(G)$ is called a
balanced separator if each component of $G-X$ has at most $2n/3$ vertices. Let
$s(G)$ denotes the minimum size of a balanced separator in $G$. For a graph
class $\mathcal{G}$, let
$s_{\mathcal{G}}~{}\colon~{}{\mathbb{N}}_{0}\rightarrow{\mathbb{N}}_{0}$ be
the function defined by $s_{\mathcal{G}}(n)=\max\\{s(H)~{}\colon~{}H\subseteq
G\in\mathcal{G},|V(H)|\leq n\\}$. The graph class $\mathcal{G}$ has strongly
sublinear separators if $s_{\mathcal{G}}(n)=O(n^{\eta})$ for some $\eta<1$.

The following theorem gives a nice characterization of polynomial-expansion
graphs.

######  Theorem 5.2 ([51]).

A graph class is of polynomial expansion iff it has strongly sublinear
separator.

For a graph class $\mathcal{G}$ of polynomial expansion, a separator-
computation algorithm on $\mathcal{G}$ refers to an algorithm that can
compute, for a given graph $G\in\mathcal{G}$ with $n$ vertices, a balanced
separator of $G$ of size $O(n^{\eta})$ for some constant $\eta<1$ (such a
separator exists by Theorem 5.2).

######  Lemma 5.3.

Let $\mathcal{G}$ be any graph class of polynomial expansion. For any constant
$\alpha>0$, there exists a separator-computation algorithm on $\mathcal{G}$
with running time $f(\Delta)\cdot n^{1+\alpha}$ for some function $f$, where
$n$ is the number of vertices in the input graph $G\in\mathcal{G}$ and
$\Delta$ is the maximum degree of $G$.

To prove Lemma 5.3 we use a recent result by Chuzhoy et al.[31]. We define
some notations and a problem to state the result of Chuzhoy et al.[31]. Let
$G$ be a graph. For a partition of $V(G)$ into $A\uplus B$, $E_{G}(A,B)$ is
the set of all edges with one endpoint in $A$ and the other in $B$. For a
subset $S$ of $V(G)$ ${\sf Vol}_{G}(S)$ denotes its volume \- the sum of
degrees of all vertices of $S$. Finally, ${\sf Vol}(G)={\sf Vol}_{G}(V(G))$.
Next we define the Minimum Balanced Cut problem. For this problem the input is
a graph $G$ and the objective is to compute a partition of $V(G)$ into two
subsets $A$ and $B$ with ${\sf Vol}_{G}(A),{\sf Vol}_{G}(B)\geq{\sf
Vol}(G)/3$, while minimizing the cardinality of $E_{G}(A,B)$.

######  Proposition 5.4 ([31]).

There is an algorithm for Minimum Balanced Cut that given a graph $G$ and a
constant $\epsilon>0$, outputs a $(\log m)^{1/\epsilon}$-approximate solution
in time $O(m^{1+O(\sqrt{\epsilon})})$.

Now we are ready to prove Lemma 5.3.

###### Proof of Lemma 5.3.

Recall that $\mathcal{G}$ is a graph class of polynomials expansion. Let $d$
and $\eta<1$ be two constants such that for any $G\in\mathcal{G}$,
$s_{\mathcal{G}}(n)=O(n^{\eta})$ and for any $G\in\mathcal{G}$, $|E(G)|\leq
d\cdot|V(G)|$. Such a constant $\eta$ exists because of Theorem 5.2. Let
$G\in\mathcal{G}$ be the input to our separator-computation algorithm. Let
$n=|V(G)|$ and $\Delta$ be the maximum degree of $G$. Let $\alpha>0$ the
constant mentioned in the statement of the lemma. Since $|E(G)|\leq
d\cdot|V(G)|$, we have that ${\sf Vol}(G)\leq 2d\cdot|V(G)|=2d\cdot n$. Let
$\epsilon,\beta>0$ be two constant which we fix later.

First we consider the case when $\Delta\leq n^{\beta}$. We apply Proposition
5.4 on $G$ and $\epsilon$. Let $(A_{1},B_{1})$ be the output. By Theorem 5.2
and the assumption that $\Delta\leq n^{\beta}$, we get that the cardinality of
an optimum solution to $G$ for the Minimum Balanced Cut problem is at most
$n^{\beta+\eta}$. This implies that $|E_{G}(A_{1},B_{1})|\leq
n^{\beta+\eta+o(1)}$. Let $S_{1}$ be the endpoints of the edges in
$E_{G}(A_{1},B_{1})$ that belong to $B_{1}$. Clearly $S_{1}$ separates $A_{1}$
from $B_{1}\setminus S_{1}$. If $|A_{1}|,|B_{1}|\leq 2n/3$, then we set
$X_{1}=A_{1}$ and $X_{2}=B_{1}\setminus S_{1}$, and $S_{1}$ is the required
output. Otherwise, let $X_{1}\in\\{A_{1},B_{1}\setminus S_{1}\\}$ such that
$|X_{1}|\leq n/3$ and $Y_{1}$ be the unique set in $\\{A_{1},B_{1}\setminus
S_{1}\\}\setminus X_{1}$. By Proposition 5.4, we know that ${\sf
Vol}_{G}(Y_{1})\leq 2{\sf Vol}(G)/3\leq\frac{2}{3}2dn$. We again apply
Proposition 5.4 on $G_{2}=G[Y_{1}]$ and $\epsilon$. Let $(A_{2},B_{2})$ be the
output. Like before, let $S_{2}$ be the endpoints of $E_{G_{2}}(A_{2},B_{2})$
that belong to $B_{2}$. Notice that $S_{1}\cup S_{2}$ is a separator that
separates the vertex subsets $A_{2}$, $B_{2}\setminus(S_{1}\cup S_{2})$, and
$X_{1}$. If their cardinalities are upper bounded by $2n/3$, then we set
$X_{2}=A_{2}$ and $X_{3}=B_{2}\setminus S_{2}$, and $S_{1}\cup S_{2}$ is the
required output. Otherwise, let $X_{2}\in\\{A_{2},B_{2}\setminus S_{2}\\}$
such that $|X_{2}|\leq n/3$ and $Y_{2}$ be the unique set in
$\\{A_{2},B_{2}\setminus S_{2}\\}\setminus X_{2}$. By Proposition 5.4, we know
that ${\sf Vol}_{G}(Y_{2})\leq 2{\sf Vol}(G_{2})/3\leq(\frac{2}{3})^{2}2dn$.
We continue these steps and obtain a series of at most
$q=\lceil\log_{3/2}(2d)\rceil$ separators $S_{1},S_{2},...,S_{q}$ and vertex
subsets $X_{1},X_{2},\ldots,X_{q}$ such that the following properties are
satisfied.

  * (a)

$V(G)=\biguplus_{i\in[q]}(S_{i}\uplus X_{i})$,

  * (b)

for each $i\in[q]$, $|X_{i}|\leq\frac{2}{3}n$, and

  * (c)

for each component $C$ in $G-\bigcup_{i\in[q]}S_{i}$, there exists $j\in[q]$
such that $V(C)\subseteq X_{i}$.

Condition (c) implies that for each component $C$ in
$G-\bigcup_{i\in[q]}S_{i}$, $|V(C)|\leq 2n/3$. Moreover,
$|\bigcup_{i\in[q]}S_{i}|\leq qn^{\beta+\eta+o(1)}$. Let $\eta^{\prime}$ be a
fixed constant such that $\eta<\eta^{\prime}<1$. Due to Proposition 5.4, the
running time of our algorithm is $O(n^{1+O(\sqrt{\epsilon})})$. We choose
$\epsilon$ and $\beta$ in such a way that the running time is
$O(n^{1+\alpha})$ and $|\bigcup_{i\in[q]}S_{i}|$ is upper bounded by a
constant $n^{\eta^{\prime}}$. The set $\bigcup_{i\in[q]}S_{i}$ is the required
output.

When $\Delta>n^{\beta}$, we try all possible vertex subsets and outputs the
best balanced separator of $G$. Clearly, in this case the running time is
upper bounded by $f(\Delta)$ for a suitable function $f$. This completes the
proof of the lemma. ∎

######  Corollary 5.5.

Let $\mathcal{G}$ be any graph class of polynomial expansion. For any constant
$\alpha>0$, there exists an algorithm that can compute, for a given graph
$G\in\mathcal{G}$ with $n$ vertices and maximum degree $\Delta$ and a given
number $\beta>0$, a subset $S\subseteq V(G)$ of size at most $\beta n$ such
that each connected component of $G-S$ contains at most $(1/\beta)^{O(1)}$
vertices, in $f(\Delta)\cdot n^{1+\alpha}$ time for some function $f$.

###### Proof sketch.

The proof of the corollary follows from Lemma 2.2 from [78]. The running time
is not mentioned in the statement of Lemma 2.2 in [81]. The algorithm works as
follows. Let $G$ be the input graph. We apply Lemma 5.3 and obtain a sub-
linear size separator $S_{1}$. Then, partition the vertices of $V(G)\setminus
S_{1}$ into $A\uplus B$ such that there are no edges with one endpoint in $A$
and the other in $B$ and $|A|,|B|\leq 2n/3$. Then, recursively find a solution
$S_{A}$ for $G[A]$ and $S_{B}$ for $G[B]$. Then the required output is
$S_{1}\cup S_{A}\cup S_{B}$. The running time of the algorithm satisfies the
following recurrence relation: $T(n)=T(an)+T(bn)+f(\Delta)n^{1+\alpha}$ where
$a+b\leq 1$ and $1/3\leq a,b\leq 2/3$. The base case is $T(n)=1$ when
$n\leq(1/\beta)^{O(1)}$. The above recurrence solves to
$f(\Delta)n^{1+\alpha}$. ∎

######  Lemma 5.6.

(Induced) Subgraph Hitting on any graph class $\mathcal{G}$ of polynomial
expansion admits an approximation scheme with running time
$f(\varepsilon,\mathcal{F},\Delta)\cdot n^{1+\alpha}$ for any constant
$\alpha>0$, where $n$ is the number of vertices in the input graph
$G\in\mathcal{G}$ and $\Delta$ is the maximum degree of $G$.

###### Proof.

We explain the proof for Subgraph Hitting and the proof is identical for the
case of Induced Subgraph Hitting. Let $(G,\mathcal{F})$ be the input and
$\varepsilon>0$ be the given approximation parameter. By the argument in
Section 4.1, it suffices to consider the case where $\mathcal{F}$ consists of
connected graphs. Indeed, the proof of Corollary 4.3 directly shows that if
the problem on $\mathcal{G}$ with connected forbidden patterns admits an
approximation scheme with running time $f(\varepsilon,\mathcal{F},\Delta)\cdot
n^{c}$, then so does the general problem. ${\sf
opt}(G,\mathcal{F}^{\prime})\leq{\sf
opt}(G,\mathcal{F})+\alpha_{\mathcal{F}}\leq(1+\frac{\varepsilon}{5}){\sf
opt}(G,\mathcal{F})$.

Now for each $v\in V(G)$, we check if there is a subgraph in $G$ containing
$v$ that isomorphic to a graph in $\mathcal{F}$ using Theorem 3.6. We say a
vertex $v\in V(G)$ is irrelevant if it is not contained in any subgraph of $G$
that is isomorphic to some graph in $\mathcal{F}$. Let $I\subseteq V(G)$
denote the set of irrelevant vertices in $G$. Note that to solve the problem,
it suffices to solve the instance $(G-I,\mathcal{F})$. Thus, we shall first
compute the set $I$ and remove it from $G$. This can be done in linear time
using the data structure of Theorem 3.10, similarly to that in Section 4.4.
Recall that in the proof of Lemma 4.17, we defined the first-order formula
$\mathsf{BelongsTo}{\cal V}_{\cal F}(v_{1},v_{2},\ldots,v_{\ell})$ that can
check whether $G[\\{v_{1},\dots,v_{\ell}\\}]$ contains a spanning subgraph
isomorphic to some $F\in\mathcal{F}$. Now we define

$\phi(v)=\bigvee_{\ell\in[\gamma]}\left(\exists
v_{1},\dots,v_{\ell}\left(\bigvee_{i\in[\ell]}v=v_{i}\right)\wedge\mathsf{BelongsTo}{\cal
V}_{\cal F}(v_{1},v_{2},\ldots,v_{\ell})\right),$

which is true iff $v\notin I$. Let $Q=V(G)$ be a unary relation on $V(G)$, and
set $\varphi=\exists v(\neg\phi(v)\wedge Q(v))$. We build the data structure
$\mathcal{D}$ of Theorem 3.10 on the graph $G$, the unary relation $Q$, and
the formula $\varphi$. We then delete all elements from $Q$ and keep updating
$\mathcal{D}$, which takes $f(|\varphi|)\cdot n$ time. To compute $I$, we
iteratively consider the vertex of $G$. For a vertex $v\in V(G)$, to check
whether $v\in I$, we add back $v$ to $Q$ and check whether $(G,Q)$ satisfies
$\varphi$ (and delete $v$ from $Q$ afterwards). In this way, we can test
whether a vertex is in $I$ in $f(|\varphi|)$ time, and hence compute $I$ in
$f(|\varphi|)\cdot n$ time. Therefore, without loss of generality, we can now
assume that $G$ does not contain any irrelevant vertices, i.e., every vertex
of $G$ is contained in a subgraph of $G$ that is isomorphic to some
$F\in\mathcal{F}$. In this situation, we observe the following.

Claim 1. ${\sf opt}(G,\mathcal{F})\geq\frac{n}{\Delta^{2\gamma}}$.

Proof of Claim 1. It is enough to prove that there are
$\frac{n}{\Delta^{2\gamma}}$ vertex disjoint subgraphs of $G$ each of which is
isomorphic to some $F\in\mathcal{F}$. Towards that we prove that there is a
subset $Z\subseteq V(G)$ of size $\frac{n}{\Delta^{2\gamma}}$ such that for
any pair $(u,v)$ of distinct vertices in $Z$, the distance between them in $G$
is at least $2\gamma$. Since no vertex in $G$ is irrelevant, and the graphs in
$\mathcal{F}$ are connected and contain at most $\gamma$ vertices, there are
$|Z|$ vertex disjoint subgraphs each of which contains exactly one vertex from
$Z$. We construct $Z$ as follows. Initially, we set $Z=\emptyset$. Then we
pick a vertex $v_{1}\in V(G)$, add to $Z$, and mark all the vertices which are
at a distance at most $2\gamma$ from $v_{1}$. There are at most
$\Delta^{2}\gamma$ such vertices. In the next round, we further pick an
unmarked vertex $v_{2}$, add to $Z$ and again mark all the vertices which are
at a distance at most $2\gamma$ from $v_{2}$. We continue this process until
all the vertices are marked. Since in each step we mark at most
$\Delta^{2\gamma}$ vertices, the number of vertices in $Z$ will be at least
$\frac{n}{\Delta^{2\gamma}}$. This completes the proof of the claim. $\lhd$

Set $\beta=\frac{\varepsilon}{\Delta^{2\gamma}}$. Now we apply Corollary 5.5
to compute a subset $S\subseteq V(G)$ of size $\beta n$ such that each
connected component of $G-S$ contains $(1/\beta)^{O(1)}$ vertices. Now, for
each connected component $C$ of $G-S$, we find an optimal solution for the
instance $(C,\mathcal{F})$ by brute-force. Note that the size of the union $U$
of these solutions is upper bounded by ${\sf opt}(G,\mathcal{F})$. Also,
$S\cup U$ is a solution for the entire instance $(G,\mathcal{F})$. By Claim 1
above, the size of $S\cup U$ is upper bounded by $|S|+{\sf
opt}(G,\mathcal{F})\leq\beta n+{\sf
opt}(G,\mathcal{F})=\frac{\varepsilon}{\Delta^{2\gamma}}n+{\sf
opt}(G,\mathcal{F})\leq(1+\varepsilon){\sf opt}(G,\mathcal{F})$. Thus, $S\cup
U$ a $(1+\varepsilon)$-approximation solution for $(G,\mathcal{F})$.

Due to Corollary 5.5, computing $S$ can be done in $f(\Delta)\cdot
n^{1+\alpha}$ time for any constant $\alpha>0$. Computing $U$ can be done in
$f(\beta)\cdot n$ time, because each component of $G-S$ contains
$(1/\beta)^{O(1)}$ vertices. As $\beta$ only depends on $\varepsilon$,
$\mathcal{F}$, and $\Delta$, the overall running time is
$f(\varepsilon,\mathcal{F},\Delta)\cdot n^{1+\alpha}$. ∎

For $H$-minor-free graphs, we can obtain an even faster approximation scheme
by using the seminal result of Klein-Plotkin-Rao [90] instead of Corollary
5.5.

######  Lemma 5.7 ([90]).

Let $H$ be a fixed graph. Given an $H$-minor-free graph $G$ with $n$ vertices
and a number $\beta>0$, one can compute in $O(n)$ time a subset $S\subseteq
V(G)$ of $\beta n$ vertices such that $\mathsf{dist}_{G}(u,v)\leq O(1/\beta)$
for any two vertices $u,v$ in the same connected component of $G-S$.

###### Proof.

In the original article [90], the authors claimed a polynomial-time algorithm
to compute the set $S$. The algorithm in fact runs in $O(n)$ time, as it
consists of $O(1)$ rounds of breath-first search in the graph (where the
constant depends on $H$). ∎

######  Lemma 5.8.

(Induced) Subgraph Hitting on $H$-minor-free graphs (for a fixed $H$) admits
an approximation scheme with running time
$f(\varepsilon,\mathcal{F},\Delta)\cdot n$, where $n$ is the number of
vertices in the input graph $G\in\mathcal{G}$ and $\Delta$ is the maximum
degree of $G$.

###### Proof.

Let $G$ be an $H$-minor-free graph, and $\mathcal{F}$ be the set of forbidden
patterns. As argued in the proof of Lemma 5.6, it suffices to consider the
case where $\mathcal{F}$ consists of connected graphs and no vertex of $G$ is
irrelevant; in this case, we have ${\sf
opt}(G,\mathcal{F})\geq\frac{n}{\Delta^{2\gamma}}$, where
$\gamma=\max_{F\in\mathcal{F}}|V(F)|$. Set
$\beta=\frac{\varepsilon}{\Delta^{2\gamma}}$. Now we apply Lemma 5.7 to
compute in $O(n)$ time a subset $S\subseteq V(G)$ of size $\beta n$ such that
$\mathsf{dist}_{G}(u,v)\leq O(1/\beta)$ for any two vertices $u,v$ in the same
connected component of $G-S$. We observe that each connected component $C$ of
$G-S$ contains $\Delta^{O(1/\beta)}$ vertices. Consider a vertex $v\in C$.
There can be at most $\sum_{i=0}^{r}\Delta^{i}=\Delta^{O(r)}$ vertices in $G$
within distance $r$ from $v$. As all vertices in $C$ are within distance
$O(1/\beta)$ from $v$ in $G$, the size of $C$ is $\Delta^{O(1/\beta)}$. Now we
do the same thing as in the proof of Lemma 5.6: find an optimal solution for
the instance $(C,\mathcal{F})$ for each component $C$ of $G-S$, and output
$S\cup U$ as our solution where $U$ is the union of the solutions for the
components of $G-S$. By the same argument as in the proof of Lemma 5.6, we see
that $S\cup U$ is a $(1+\varepsilon)$-approximation solution of
$(G,\mathcal{F})$ and the running time is
$f(\varepsilon,\mathcal{F},\Delta)\cdot n$. ∎

See 1.2

###### Proof.

If a graph class is of polynomial expansion, then its closure under taking
induced subgraphs is also of polynomial expansion. Thus, we can assume that
$\mathcal{G}$ is hereditary without loss of generality. Then combining Lemma
5.6 and Lemma 5.8 with Theorem 1.1 completes the proof. ∎

###  5.2 Graphs of (bi)clique-dependent polynomial expansion

A graph class $\mathcal{G}$ has bounded clique-size if there exists an integer
$k\in\mathbb{N}$ such that $\omega(G)\leq k$ for all $G\in\mathcal{G}$. We say
a graph class $\mathcal{G}$ is of clique-dependent bounded (resp., polynomial)
expansion if any sub-class $\mathcal{G}^{\prime}\subseteq\mathcal{G}$ that has
bounded clique-size is of bounded (resp., polynomial) expansion. Similarly, we
say a graph class $\mathcal{G}$ is of clique-dependent bounded degeneracy if
any sub-class $\mathcal{G}^{\prime}\subseteq\mathcal{G}$ that has bounded
clique-size is of bounded degeneracy. By definition, it is clear that if a
graph class is of clique-dependent bounded expansion, then it is also of
clique-dependent bounded degeneracy.

For a graph $G$ and an integer $k\geq 1$, a $k$-clique decomposition of $G$ is
a partition of $V(G)$ into $V_{0},V_{1},\dots,V_{r}$ such that
$\omega(G[V_{0}])<k$ and $G[V_{i}]$ is a $k$-clique for all $i\in[r]$. Note
that a $k$-clique decomposition always exists for any graph and any $k$.
Indeed, one can keep removing $k$-cliques from the graph until the maximum
clique is of size smaller than $k$.

######  Lemma 5.9.

Given a graph $G$ and an integer $k\geq 1$, one can compute a $k$-clique
decomposition of $G$ in $f(d)\cdot n$ time for some function $f$, where
$n=|V(G)|$ and $d$ is the degeneracy of $G$.

###### Proof.

Using the classical algorithm by Matula and Beck [105], one can compute a
degeneracy ordering of $G$ in $O(n+|E(G)|)$ time, i.e., $O(dn)$ time. Let
$v_{1},\dots,v_{n}$ be the degeneracy ordering computed. Define
$E_{i}=\\{(v_{j},v_{i})\in E(G):j<i\\}$ for $i\in[n]$. By the property of a
degeneracy ordering, $|E_{i}|\leq d$ for all $i\in[n]$. Furthermore, one can
easily compute $E_{1},\dots,E_{n}$ in $O(dn)$ time. Next, we consider each
vertex $v_{i}$ for $i$ from $1$ to $n$. During this procedure, we maintain a
$k$-clique decomposition of the graph $G[\\{v_{1},\dots,v_{i}\\}]$. Suppose
$V_{0},V_{1},\dots,V_{r}$ is a $k$-clique decomposition of the graph
$G[\\{v_{1},\dots,v_{i-1}\\}]$. In order to obtain a $k$-clique decomposition
of $G[\\{v_{1},\dots,v_{i}\\}]$, we consider the graph
$G[V_{0}\cup\\{v_{i}\\}]$. If $\omega(G[V_{0}\cup\\{v_{i}\\}])<k$, then
$V_{0}\cup\\{v_{i}\\},V_{1},\dots,V_{r}$ is a $k$-clique decomposition of
$G[\\{v_{1},\dots,v_{i}\\}]$. Otherwise, there exists a $k$-clique $K$ in
$G[V_{0}\cup\\{v_{i}\\}]$, which must contain $v_{i}$ since
$\omega(G[V_{0}])<k$. In this case, $V_{0}\backslash V(K),V_{1},\dots,V_{r},K$
is a $k$-clique decomposition of $G[\\{v_{1},\dots,v_{i}\\}]$, because
$\omega(G[V_{0}\backslash V(K)])\leq\omega(G[V_{0}])<k$. So it suffices to
find the clique $K$ (or verify its non-existence). Since we know $v_{i}\in
V(K)$, the other vertices of $K$ are all in $N_{G}(v_{i})\cap V_{0}$. The
problem now becomes finding a $(k-1)$-clique in $G[N_{G}(v_{i})\cap V_{0}]$.
Note that the vertices in $N_{G}(v_{i})\cap V_{0}$ are exactly those incident
to the edges in $E_{i}$ and contained in $V_{0}$. As $|E_{i}|\leq d$, by
checking all endpoints of the edges in $E_{i}$, we can compute
$N_{G}(v_{i})\cap V_{0}$ in $O(d)$ time. Indeed, we can determine whether a
vertex is in $V_{0}$ or not in $O(1)$ time by maintaining a mark on each
vertex in $V_{0}$. After obtaining $N_{G}(v_{i})\cap V_{0}$, we then retrieve
the edges of $G[N_{G}(v_{i})\cap V_{0}]$. This can be done in $O(d^{2})$ time
since every edge of $G[N_{G}(v_{i})\cap V_{0}]$ is contained in $E_{j}$ for
some $v_{j}\in N_{G}(v_{i})\cap V_{0}$. Once we have the graph
$G[N_{G}(v_{i})\cap V_{0}]$ in hand, we can find a $(k-1)$-clique in
$G[N_{G}(v_{i})\cap V_{0}]$ or determine no such a clique in $2^{O(d)}$ time
by brute-force, because $G[N_{G}(v_{i})\cap V_{0}]$ has at most $d$ vertices.
In this way, we obtain a $k$-clique decomposition of
$G[\\{v_{1},\dots,v_{i}\\}]$ from the $k$-clique decomposition of
$G[\\{v_{1},\dots,v_{i-1}\\}]$ in $2^{O(d)}$ time. After considering all
vertices $v_{1},\dots,v_{n}$, we finally obtain a $k$-clique decomposition of
$G$, and the total time cost is $f(d)\cdot n$ for some function $f$. ∎

######  Lemma 5.10.

Let $\mathcal{G}$ be a hereditary graph class of clique-dependent bounded
degeneracy. Given a graph $G\in\mathcal{G}$ and an integer $k\geq 1$, one can
compute a $k$-clique decomposition of $G$ in $f(k)\cdot n\log n+O(m)$ time for
some function $f$, where $n=|V(G)|$ and $m=|E(G)|$.

###### Proof.

For $p\in\mathbb{N}$, we write
$\mathcal{G}_{p}=\\{G\in\mathcal{G}:\omega(G)\leq p\\}$. Since $\mathcal{G}$
is of clique-dependent bounded degeneracy, there exists a function
$d:\mathbb{N}\rightarrow\mathbb{N}$ such that all graphs in $\mathcal{G}_{p}$
has degeneracy at most $d(p)$ for every $p\in\mathbb{N}$. We compute a
$k$-clique decomposition of a given graph $G\in\mathcal{G}$ using a simple
divide-and-conquer algorithm. First, we evenly partition the vertices of $G$
into two sets $V^{\prime}$ and $V^{\prime\prime}$, each of which contains
$n/2$ vertices. Then we recursively compute a $k$-clique decomposition
$V_{0}^{\prime},V_{1}^{\prime},\dots,V_{r^{\prime}}^{\prime}$ of
$G[V^{\prime}]$ and a $k$-clique decomposition
$V_{0}^{\prime\prime},V_{1}^{\prime\prime},\dots,V_{r^{\prime\prime}}^{\prime\prime}$
of $G[V^{\prime\prime}]$. Finally, we compute a $k$-clique decomposition
$V_{0},V_{1},\dots,V_{r}$ of $G[V_{0}^{\prime}\cup V_{0}^{\prime\prime}]$
using the algorithm in Lemma 5.9. Observe that
$V_{0},V_{1},\dots,V_{r},V_{0}^{\prime},V_{1}^{\prime},\dots,V_{r^{\prime}}^{\prime},V_{1}^{\prime\prime},\dots,V_{r^{\prime\prime}}^{\prime\prime}$
is a $k$-clique decomposition of $G$. Indeed, this is clearly a partition of
$V(G)$ in which $\omega(G[V_{0}])<k$ and all the other parts induce
$k$-cliques. Therefore, we can return it as our output. To analyze the running
time of our algorithm, note that $\omega(G[V_{0}^{\prime}\cup
V_{0}^{\prime\prime}])<2k$, because $\omega(G[V_{0}^{\prime}])<k$ and
$\omega(G[V_{0}^{\prime\prime}])<k$. Also, $G[V_{0}^{\prime}\cup
V_{0}^{\prime\prime}]\in\mathcal{G}$ since $\mathcal{G}$ is hereditary. It
follows that $G[V_{0}^{\prime}\cup V_{0}^{\prime\prime}]\in\mathcal{G}_{2k}$
and the degeneracy of $G[V_{0}^{\prime}\cup V_{0}^{\prime\prime}]$ is at most
$d(2k)$. Therefore, applying the algorithm in Lemma 5.9 takes
$f_{0}(d(2k))\cdot n$ time for some function $f_{0}$. Besides, before the
recursive calls of the algorithm on $G[V^{\prime}]$ and $G[V^{\prime\prime}]$,
we need to construct these two graphs. Also, we need to construct
$G[V_{0}^{\prime}\cup V_{0}^{\prime\prime}]$ before working on it. If we do
these graph constructions explicitly, it takes $O(m)$ time. In this way, the
running time of our algorithm satisfies the recurrence

$T(n,m)=T(n/2,m^{\prime})+T(n/2,m^{\prime\prime})+f_{0}(d(2k))\cdot n+O(m),$

where $m^{\prime}$ and $m^{\prime\prime}$ are the numbers of edges in
$G[V^{\prime}]$ and $G[V^{\prime\prime}]$, respectively. As
$m^{\prime}+m^{\prime\prime}\leq m$, This recurrence solves to
$T(n,m)=f(k)\cdot n\log n+O(m\log n)$ for some function $f$.

In fact, we can further improve the running time to $f(k)\cdot n\log n+O(m)$
as follows. The recursion tree of the above algorithm is a binary tree $T$ of
depth $O(\log n)$ whose leaves one-to-one correspond to the $n$ vertices in
$G$. Each node of $T$ corresponds to a recursive call of the algorithm. For
each node $t\in T$, let $G_{t}$ denote the subgraph of $G$ induced by the
vertices corresponding to the leaves of the subtree of $T$ rooted at $t$. The
call at the node $t$ returns a $k$-clique decomposition of $G_{t}$. In order
to avoid the $O(m\log n)$ term in the above algorithm, we do a preprocessing
as follows. We first build the recursion tree $T$, which can be done in $O(n)$
time. Next, we store every edge $e=(u,v)\in E(G)$ at the lowest common
ancestor of the two leaves of $T$ corresponding to $u$ and $v$. Using the
classical algorithm by Harel and Tarjan [80], the lowest common ancestor can
be found in $O(1)$ time. Thus, this step can be done in $O(m)$ time in total.
Let $E_{t}$ denote the set of edges stored at each node $t\in T$. After this
preprocessing, we apply the above recursive algorithm with some small
modifications. First, in the call at a node $t\in T$, we not only return a
$k$-clique decomposition $V_{0},V_{1},\dots,V_{k}$ of $G_{t}$, but also return
the induced subgraph $G[V_{0}]$. Achieving this is not difficult, as the part
$V_{0}$ is finally obtained by the algorithm of Lemma 5.9 and that algorithm
can actually also return the induced subgraph $G[V_{0}]$ in the same running
time. Second, when we recursively call the algorithm at the children of a
node, we do not construct the corresponding graphs of the children beforehand.
This modification brings us an issue: when solving the problem at a node $t$,
we do not have the graph $G_{t}$ in hand. In this situation, we can still do
the recursive calls at the children $t^{\prime}$ and $t^{\prime\prime}$ of $t$
(as we do not need to construct the corresponding graphs). However, after we
obtain the $k$-clique decomposition
$V_{0}^{\prime},V_{1}^{\prime},\dots,V_{r^{\prime}}^{\prime}$ of
$G_{t^{\prime}}$ and the $k$-clique decomposition
$V_{0}^{\prime\prime},V_{1}^{\prime\prime},\dots,V_{r^{\prime\prime}}^{\prime\prime}$
of $G_{t^{\prime\prime}}$ returned by the recursive calls, we have to
efficiently construct the graph $G[V_{0}^{\prime}\cup V_{0}^{\prime\prime}]$
without knowing $G_{t}$ and then apply the algorithm of Lemma 5.9 on
$G[V_{0}^{\prime}\cup V_{0}^{\prime\prime}]$. By assumption, the recursive
calls already return us the graphs $G[V_{0}^{\prime}]$ and
$G[V_{0}^{\prime\prime}]$. Observe that all edges of $G[V_{0}^{\prime}\cup
V_{0}^{\prime\prime}]$ except those in $G[V_{0}^{\prime}]$ and
$G[V_{0}^{\prime\prime}]$ are in the set $E_{t}$. Therefore, to construct
$G[V_{0}^{\prime}\cup V_{0}^{\prime\prime}]$ provided $G[V_{0}^{\prime}]$ and
$G[V_{0}^{\prime\prime}]$, we only need to check every edge in $E_{t}$ and
find those with one endpoint in $V_{0}^{\prime}$ and the other endpoint in
$V_{0}^{\prime}$, which can be done in $O(|E_{t}|)$ time. Now if we use $T(t)$
to denote the running time of the call at the node $t$, it satisfies the
recurrence

$T(t)=T(t^{\prime})+T(t^{\prime\prime})+f_{0}(d(2k))\cdot|V(G_{t})|+O(|E_{t}|).$

Since $\sum_{t\in T}|E_{t}|=m$, the recurrence solves to
$T(\mathsf{rt})=f(k)\cdot n\log n+O(m)$ for some function $f$, where
$\mathsf{rt}\in T$ is the root of $T$. ∎

See 1.3

###### Proof.

For $p\in\mathbb{N}$, we write
$\mathcal{G}_{p}=\\{G\in\mathcal{G}:\omega(G)\leq p\\}$. Since $\mathcal{G}$
is of clique-dependent bounded expansion, $\mathcal{G}_{p}$ is of bounded
expansion for every $p\in\mathbb{N}$. As
$\mathcal{G}_{p}\subseteq\mathcal{G}$, Subgraph Hitting on $\mathcal{G}_{p}$
admits an approximation scheme with running time
$f_{0}(\varepsilon,\mathcal{F},\Delta)\cdot n^{c}$. Thus, by Theorem 1.1, for
each $p\in\mathbb{N}$, there exists a function $f_{p}$ such that Subgraph
Hitting on $\mathcal{G}_{p}$ admits an approximation scheme $\mathbf{A}_{p}$
which runs in $f_{p}(\varepsilon,\mathcal{F})\cdot n^{c}$ time. Now we
consider how to solve Subgraph Hitting on $\mathcal{G}$. Let $(G,\mathcal{F})$
be a Subgraph Hitting instance where $G\in\mathcal{G}$, and $\varepsilon>0$ be
the approximation factor. As before, set
$\gamma=\max_{F\in\mathcal{F}}|V(F)|$. Define
$k=\frac{1+\varepsilon}{\varepsilon}\cdot(\gamma-1)$. We first apply the
algorithm of Lemma 5.10 to compute a $k$-clique decomposition
$V_{0},V_{1},\dots,V_{r}$ of $G$. We have $\omega(G[V_{0}])<k$. It follows
that $\omega(G[V_{0}])\in\mathcal{G}_{k}$, since $\mathcal{G}$ is hereditary.
So we can apply the approximation scheme $\mathbf{A}_{k}$ on the instance
$(G[V_{0}],\mathcal{F})$ with approximation factor $\varepsilon$, which
returns us a $(1+\varepsilon)$-approximation solution $S_{0}\subseteq V_{0}$.
Finally, we simply return $S=S_{0}\cup(\bigcup_{i=1}^{r}V_{i})$ as the final
solution. The algorithm for computing the $k$-clique decomposition takes
$f(k)\cdot n\log n+O(m)$ time. Applying $\mathbf{A}_{k}$ takes
$f_{k}(\varepsilon,\mathcal{F})\cdot n^{c}$ time. Since $k$ only depends on
$\varepsilon$ and $\mathcal{F}$, the overall running time of our algorithm is
$f(\varepsilon,\mathcal{F})\cdot(n^{c}+n\log n)+O(m)$ for some function $f$.

Next, we show the correctness of the above algorithm. Clearly, $S$ is a
feasible solution of the instance $(G,\mathcal{F})$. Indeed,
$G-S=G[V_{0}]-S_{0}$ and the latter contains no forbidden pattern in
$\mathcal{F}$ as a subgraph since $S_{0}$ is a solution of
$(G[V_{0}],\mathcal{F})$. It suffices to show that
$|S|\leq(1+\varepsilon)\cdot|S^{\prime}|$ for any solution
$S^{\prime}\subseteq V(G)$ of $(G,\mathcal{F})$. First observe that
$S^{\prime}\cap V_{0}$ is a feasible solution of $(G[V_{0}],\mathcal{F})$, for
otherwise the graph $G[V_{0}]-S^{\prime}\cap V_{0}$ contains a forbidden
pattern in $\mathcal{F}$ as a subgraph and so does $G-S^{\prime}$, which
contradicts that $S^{\prime}$ is a solution of $(G,\mathcal{F})$. Therefore,
$|S_{0}|\leq(1+\varepsilon)\cdot|S^{\prime}\cap V_{0}|$. Now we consider the
sets $V_{1},\dots,V_{r}$, which induce $k$-cliques in $G$. For each $i\in[r]$,
we must have $|V_{i}\backslash S^{\prime}|\leq\gamma-1$, for otherwise
$G-S^{\prime}$ contains a $\gamma$-clique and thus contains any forbidden
pattern in $\mathcal{F}$. It follows that $|S^{\prime}\cap V_{i}|\geq
k-(\gamma-1)=\frac{k}{1+\varepsilon}$ for each $i\in[r]$. So we have

$|S|=|S_{0}|+rk\leq(1+\varepsilon)\cdot|S^{\prime}\cap
V_{0}|+(1+\varepsilon)\cdot\sum_{i=1}^{r}|S^{\prime}\cap
V_{i}|=(1+\varepsilon)\cdot|S^{\prime}|,$

which implies the correctness of our algorithm and completes the proof. ∎

Lemma 5.10 also gives us a byproduct for $k$-Subgraph Isomorphism.

######  Theorem 5.11.

$k$-Subgraph Isomorphism on any graph class $\mathcal{G}$ of clique-dependent
polynomial expansion can be solved in $f(k)\cdot n\log n+O(m)$ time for some
function $f$, where $n$ and $m$ are the number of vertices and edges in the
input graph $G\in\mathcal{G}$, respectively.

###### Proof.

For $p\in\mathbb{N}$, we write
$\mathcal{G}_{p}=\\{G\in\mathcal{G}:\omega(G)\leq p\\}$. Since $\mathcal{G}$
is of clique-dependent polynomial expansion, $\mathcal{G}_{p}$ is of
polynomial expansion for every $p\in\mathbb{N}$. Thus, by Theorem 3.6, for
each $p\in\mathbb{N}$, there exists a function $f_{p}$ such that $k$-Subgraph
Isomorphism on $\mathcal{G}_{p}$ can be solved in $f_{p}(k)\cdot n$ time. Now
consider a graph $G\in\mathcal{G}$, and let $H$ be the $k$-vertex graph we are
looking for. We first apply Lemma 5.10 to compute a $k$-clique decomposition
$V_{0},V_{1},\dots,V_{r}$ of $G$ in $f(k)\cdot n\log n+O(m)$ time. If $r\geq
1$, then we find a $k$-clique which contains $H$ as a subgraph. Otherwise,
$r=0$ and $G=G[V_{0}]$, which implies that $\omega(G)<k$, i.e.,
$G\in\mathcal{G}_{k}$. In this case, we can solve $k$-Subgraph Isomorphism on
$G$ in $f_{k}(k)\cdot n$ time. Finally, the total running time is bounded by
$f(k)\cdot n\log n+O(m)$ time for some function $f$. ∎

A graph class $\mathcal{G}$ has bounded biclique-size if there exists an
integer $k\in\mathbb{N}$ such that $\omega^{\prime}(G)\leq k$ for all
$G\in\mathcal{G}$. We say a graph class $\mathcal{G}$ is of biclique-dependent
bounded (resp., polynomial) expansion if any sub-class
$\mathcal{G}^{\prime}\subseteq\mathcal{G}$ that has bounded biclique-size is
of bounded (resp., polynomial) expansion.

For a graph $G$ and an integer $k\geq 1$, a $k$-biclique decomposition of $G$
is a partition of $V(G)$ into $V_{0},V_{1},\dots,V_{r}$ such that
$\omega^{\prime}(G[V_{0}])<k$ and $G[V_{i}]$ is a $(k,k)$-biclique for all
$i\in[r]$. We show that $k$-biclique decompositions can be computed
efficiently on graph classes of biclique-dependent bounded expansion.

######  Lemma 5.12.

Let $\mathcal{G}$ be a hereditary graph class of biclique-dependent bounded
expansion. Given a graph $G\in\mathcal{G}$ and an integer $k$, one can compute
a $k$-biclique decomposition of $G$ in $f(k)\cdot n^{2}$ time for some
function $f$, where $n=|V(G)|$.

###### Proof.

For $p\in\mathbb{N}$, we write
$\mathcal{G}_{p}=\\{G\in\mathcal{G}:\omega^{\prime}(G)\leq p\\}$. Since
$\mathcal{G}$ is of biclique-dependent bounded expansion, each
$\mathcal{G}_{p}$ is a graph class of bounded expansion. So Subgraph
Isomorphism (for a fixed subgraph) can be solved in linear time on
$\mathcal{G}_{p}$ [49]. In other words, there exists a function $f_{p}$ such
that one can find a subgraph of $q$ vertices in a given $G\in\mathcal{G}_{p}$
in $f_{p}(q)\cdot n$ time. For convenience, we denote this Subgraph
Isomorphism algorithm by $\mathbf{A}_{p}$.

We compute a $k$-biclique decomposition of a given graph $G\in\mathcal{G}$ as
follows. Suppose $V(G)=\\{v_{1},\dots,v_{n}\\}$. We consider each $v_{i}$
iteratively for $i=1,\dots,n$ and maintain a $k$-biclique decomposition of the
induced subgraph $G[\\{v_{1},\dots,v_{i}\\}]$. Let $V_{0},V_{1},\dots,V_{r}$
be a $k$-biclique decomposition of $G[\\{v_{1},\dots,v_{i-1}\\}]$. To compute
a $k$-biclique decomposition of $G[\\{v_{1},\dots,v_{i}\\}]$, we simply call
the algorithm $\mathbf{A}_{k}$ to find a $(k,k)$-biclique in
$G[V_{0}\cup\\{v_{i}\\}]$. Note that $\mathbf{A}_{k}$ can be applied to
$G[V_{0}\cup\\{v_{i}\\}]$, and it takes $f_{k}(2k)\cdot n$ time. Indeed, we
have
$\omega^{\prime}(G[V_{0}\cup\\{v_{i}\\}])\leq\omega^{\prime}(G[V_{0}])+1\leq
k$, since $\omega^{\prime}(G[V_{0}])<k$ by the definition of a $k$-biclique
decomposition. If $G[V_{0}\cup\\{v_{i}\\}]$ does not contain a
$(k,k)$-biclique, then $V_{0}\cup\\{v_{i}\\},V_{1},\dots,V_{r}$ is a
$k$-biclique decomposition of $G[\\{v_{1},\dots,v_{i}\\}]$. Otherwise, let
$V_{r+1}$ be (the vertex set of) a $(k,k)$-biclique in
$G[V_{0}\cup\\{v_{i}\\}]$. Observe that $v_{i}\in V_{r+1}$, for otherwise
$G[V_{0}]$ contains a $(k,k)$-biclique, which contradicts the fact
$\omega^{\prime}(G[V_{0}])<k$. Therefore,
$\omega^{\prime}(G[(V_{0}\cup\\{v_{i}\\})\backslash V_{r+1}])<k$, as
$(V_{0}\cup\\{v_{i}\\})\backslash V_{r+1}\subseteq V_{0}$. In this case,
$(V_{0}\cup\\{v_{i}\\})\backslash V_{r+1},V_{1},\dots,V_{r},V_{r+1}$ is a
$k$-biclique decomposition of $G[\\{v_{1},\dots,v_{i}\\}]$. After the last
vertex $v_{n}$ is considered, we obtain a $k$-biclique decomposition of $G$.
The overall time complexity of the algorithm is $f(k)\cdot n^{2}$ for some
function $k$, since each iteration takes linear time. ∎

See 1.4

###### Proof.

The proof is almost the same as that of Theorem 1.3. For $p\in\mathbb{N}$, we
write $\mathcal{G}_{p}=\\{G\in\mathcal{G}:\omega^{\prime}(G)\leq p\\}$. Since
$\mathcal{G}$ is of biclique-dependent bounded expansion, $\mathcal{G}_{p}$ is
of bounded expansion for every $p\in\mathbb{N}$. As
$\mathcal{G}_{p}\subseteq\mathcal{G}$, Bipartite Subgraph Hitting on
$\mathcal{G}_{p}$ admits a $(2+\varepsilon)$-approximation algorithm with
running time $f_{0}(\varepsilon,\mathcal{F},\Delta)\cdot n^{c}$. Notice that
Theorem 1.1 also holds for $(2+\varepsilon)$-approximation algorithms; see the
discussion at the end of Section 4.5. Furthermore, Theorem 1.1 reduces an
instance of Bipartite Subgraph Hitting to instances of Bipartite Subgraph
Hitting. Therefore, applying (this variant of) Theorem 1.1, we know that for
each $p\in\mathbb{N}$, there exists a function $f_{p}$ such that Bipartite
Subgraph Hitting on $\mathcal{G}_{p}$ admits a $(2+\varepsilon)$-approximation
algorithm $\mathbf{A}_{p}$ which runs in $f_{p}(\varepsilon,\mathcal{F})\cdot
n^{c}$ time. Now we consider how to solve Bipartite Subgraph Hitting on
$\mathcal{G}$. Let $(G,\mathcal{F})$ be a Bipartite Subgraph Hitting instance
where $G\in\mathcal{G}$, and $\varepsilon>0$ be the approximation factor. By
definition, there exists a bipartite graph $F\in\mathcal{F}$. Set
$\gamma=|V(F)|$ and $k=\frac{2+\varepsilon}{\varepsilon}\cdot(\gamma-1)$. We
first apply the algorithm of Lemma 5.12 to compute a $k$-biclique
decomposition $V_{0},V_{1},\dots,V_{r}$ of $G$. We have $\omega(G[V_{0}])<k$.
It follows that $\omega(G[V_{0}])\in\mathcal{G}_{k}$, since $\mathcal{G}$ is
hereditary. So we can apply the approximation scheme $\mathbf{A}_{k}$ on the
instance $(G[V_{0}],\mathcal{F})$ with approximation factor $\varepsilon$,
which returns us a $(1+\varepsilon)$-approximation solution $S_{0}\subseteq
V_{0}$. Finally, we simply return $S=S_{0}\cup(\bigcup_{i=1}^{r}V_{i})$ as the
final solution. The algorithm for computing the $k$-biclique decomposition
takes $f(k)\cdot n^{2}$ time for some function $f$. Applying $\mathbf{A}_{k}$
takes $f_{k}(\varepsilon,\mathcal{F})\cdot n^{c}$ time. Since $c\geq 2$ and
$k$ only depends on $\varepsilon$ and $\mathcal{F}$, the overall running time
of our algorithm is $f(\varepsilon,\mathcal{F})\cdot n^{c}$ for some function
$f$.

Next, we show the correctness of the above algorithm. Clearly, $S$ is a
feasible solution of the instance $(G,\mathcal{F})$. Indeed,
$G-S=G[V_{0}]-S_{0}$ and the latter contains no forbidden pattern in
$\mathcal{F}$ as a subgraph since $S_{0}$ is a solution of
$(G[V_{0}],\mathcal{F})$. It suffices to show that
$|S|\leq(2+\varepsilon)\cdot|S^{\prime}|$ for any solution
$S^{\prime}\subseteq V(G)$ of $(G,\mathcal{F})$. First observe that
$S^{\prime}\cap V_{0}$ is a feasible solution of $(G[V_{0}],\mathcal{F})$, for
otherwise the graph $G[V_{0}]-S^{\prime}\cap V_{0}$ contains a forbidden
pattern in $\mathcal{F}$ as a subgraph and so does $G-S^{\prime}$, which
contradicts that $S^{\prime}$ is a solution of $(G,\mathcal{F})$. Therefore,
$|S_{0}|\leq(2+\varepsilon)\cdot|S^{\prime}\cap V_{0}|$. Now we consider the
sets $V_{1},\dots,V_{r}$, each of which forms a $(k,k)$-biclique in $G$. For
each $i\in[r]$, $S$ must intersect one side of $G[V_{i}]$ with at least
$k-(\gamma-1)$ vertices, for otherwise $G-S^{\prime}$ contains a
$(\gamma,\gamma)$-biclique and thus contains the bipartite forbidden pattern
$F$. It follows that $|S^{\prime}\cap V_{i}|\geq
k-(\gamma-1)=\frac{2k}{2+\varepsilon}$ for each $i\in[r]$. So we have

$|S|=|S_{0}|+2rk\leq(2+\varepsilon)\cdot|S^{\prime}\cap
V_{0}|+(2+\varepsilon)\cdot\sum_{i=1}^{r}|S^{\prime}\cap
V_{i}|=(2+\varepsilon)\cdot|S^{\prime}|,$

which implies the correctness of our algorithm and completes the proof. ∎

###  5.3 Geometric intersection graphs

A geometric object $X$ in $\mathbb{R}^{d}$ is $\alpha$-fat for a number
$\alpha\geq 1$ if $X$ is convex and there are two balls
$B_{\mathsf{in}},B_{\mathsf{out}}$ in $\mathbb{R}^{d}$ such that
$B_{\mathsf{in}}\subseteq X\subseteq B_{\mathsf{out}}$ and
$\mathsf{rad}(B_{\mathsf{out}})\leq\alpha\cdot\mathsf{rad}(B_{\mathsf{in}})$.
Clearly, balls are exactly the $1$-fat geometric objects. We say $\mathcal{G}$
is a class of fat-object graphs if there exist $\alpha\geq 1$ and
$d\in\mathbb{N}$ such that every graph in $\mathcal{G}$ is the intersection
graph of a set of $\alpha$-fat geometric objects in $\mathbb{R}^{d}$. Theorem
1.3 can be applied to fat-object graphs, yielding the following result.

######  Corollary 5.13.

Subgraph Hitting on any class $\mathcal{G}$ of fat-object graphs admits an
approximation scheme with running time $f(\varepsilon,\mathcal{F})\cdot
n^{1+\alpha}+O(m)$ for some function $f$ and any constant $\alpha>0$, where
$n$ and $m$ are the numbers of vertices and edges in the input graph
$G\in\mathcal{G}$, respectively.

###### Proof.

It was known that fat-object graphs with bounded clique size form a graph
class with strongly sublinear separators [37, 48, 55]. Thus, $\mathcal{G}$ is
of clique-dependent polynomial expansion. By Theorem 1.3, to prove the
corollary, it suffices to give an approximation scheme for Subgraph Hitting on
$\mathcal{G}$ with running time $f(\varepsilon,\mathcal{F},\Delta)\cdot
n^{1+\alpha}$, where $\Delta$ is the maximum degree of the input graph
$G\in\mathcal{G}$. Define $\mathcal{G}_{\Delta}\subseteq\mathcal{G}$ as the
subclass consisting of graphs of maximum degree at most $\Delta$. Note that
$\omega(G)\leq\Delta+1$ for all $G\in\mathcal{G}_{\Delta}$. So
$\mathcal{G}_{\Delta}$ is of polynomial expansion for all $\Delta\mathbb{N}$.
By Theorem 1.2, for each $\Delta\mathbb{N}$, there exists a function
$f_{\Delta}$ such that Subgraph Hitting on $\mathcal{G}_{\Delta}$ admits an
approximation scheme with running time
$f_{\Delta}(\varepsilon,\mathcal{F})\cdot n^{1+\alpha}$. Writing
$f(\varepsilon,\mathcal{F},\Delta)=f_{\Delta}(\varepsilon,\mathcal{F})$
completes the proof. ∎

A set of geometric objects in the plane are called pseudo-disks if each of
them is homeomorphic to a disk and the boundaries of any two objects are
either disjoint or intersect exactly twice. A graph is a pseudo-disk graph if
it is the intersection graph of a set of pseudo-disks in the plane. We show
that pseudo-disk graphs with bounded clique size have strongly sublinear
separators.

######  Lemma 5.14.

The class of pseudo-disk graphs is of clique-dependent polynomial expansion.

###### Proof.

Consider a set $\mathcal{S}$ of pseudo-disks in the plane and let $G$ be the
intersection graph of $\mathcal{S}$. Suppose $\omega(G)\leq p$. For each
$S\in\mathcal{S}$, we denote by $v_{S}\in V(G)$ its corresponding vertex. The
boundaries of the pseudo-disks in $\mathcal{S}$ subdivide the plane into
connected regions called faces. The depth of a face is the number of pseudo-
disks in $\mathcal{S}$ containing it. Two faces are adjacent if their
boundaries share a common arc. The arrangement graph $A(\mathcal{S})$ of $S$
is a planar graph whose vertices are the faces contained in at least one
pseudo-disk in $\mathcal{S}$ and two vertices are connected by an edge if they
are adjacent. Observe that each $S\in\mathcal{S}$, the subgraph of
$A(\mathcal{S})$ induced by the faces contained in $S$ is connected, because
$S$ is connected. It is well-known [88] that the number of faces of depth at
most $d$ is bounded by $O(dn)$, where $n=|\mathcal{S}|$. Since $\omega(G)\leq
p$, all faces are of depth at most $p$ and thus the total number of faces is
$O(pn)$, which implies that $A(\mathcal{S})$ has $O(pn)$ vertices. By
recursively applying the separator theorem for planar graphs, we can find a
set $X$ of $f(p)\cdot\sqrt{n}$ vertices of $A(\mathcal{S})$ such that each
connected component of $A(\mathcal{S})-X$ has at most $n/(2p)$ vertices. Let
$\mathcal{S}^{\prime}\subseteq S$ be the subset consisting of pseudo-disks
which contains a face corresponding to some $x\in X$. Since the depth of each
face is at most $p$, we have $|\mathcal{S}^{\prime}|\leq
p\cdot|X|=f^{\prime}(p)\cdot\sqrt{n}$ where $f^{\prime}(p)=pf(p)$. We claim
that $\mathcal{S}^{\prime}$ is a balanced separator of $G$. Let
$C_{1},\dots,C_{r}$ be the connected components of $A(\mathcal{S})-X$. For
each pseudo-disk $S\in\mathcal{S}\backslash\mathcal{S}^{\prime}$, let $Y_{S}$
be the set of vertices of $A(\mathcal{S})$ whose corresponding faces are
contained in $S$. Observe that the vertices in $Y_{S}$ belong to the same
connected component of $A(\mathcal{S})-X$, because $Y_{S}\cap X=\emptyset$ and
$Y_{S}$ induces a connected subgraph of $A(\mathcal{S})$; we say $S$ belongs
to $C_{i}$ if the vertices in $Y_{S}$ belong to $C_{i}$. Also notice that if
$S,S^{\prime}\in\mathcal{S}\backslash\mathcal{S}^{\prime}$ belong to different
connected components of $A(\mathcal{S})-X$, then there is no edge between $S$
and $S^{\prime}$ in $G$, since $S$ and $S^{\prime}$ do not intersect.
Therefore, the vertices in one connected component of $G-\mathcal{S}^{\prime}$
must belong to the same $C_{i}$. Since each $C_{i}$ has at most $n/(2p)$
vertices and the face corresponding to each vertex can be contained in at most
$p$ pseudo-disks in $\mathcal{S}$, the number of vertices of
$G-\mathcal{S}^{\prime}$ belonging to $C_{i}$ is at most $n/2$. As a result,
each connected component of $G-\mathcal{S}^{\prime}$ contains at most $n/2$
vertices and thus $\mathcal{S}^{\prime}$ is a balanced separator of $G$. Now
we see every $n$-vertex pseudo-disk graph with maximum clique size at most $p$
has a balanced separator of size $f(p)\cdot\sqrt{n}$ for some function $f$.
Thus, the class of pseudo-disk graphs is of clique-dependent polynomial
expansion. ∎

Based on some technique developed for plane geometric intersection graphs very
recently by Lokshtanov et al. [100], we can obtain a linear-time approximation
scheme for Subgraph Hitting on pseudo-disk graphs with bounded degree.

######  Lemma 5.15.

Subgraph Hitting on the class $\mathcal{G}$ of pseudo-disk graphs admits an
approximation scheme with running time $f(\varepsilon,\mathcal{F},\Delta)\cdot
n$, where $n$ is the number of vertices in the input graph $G\in\mathcal{G}$
and $\Delta$ is the maximum degree of $G$.

###### Proof.

The lemma directly follows from the algorithm given in [100] based on Baker’s
approach. For the sake of completeness, and since the time complexity is not
proven to have a linear dependency on $n$, we reiterate the description here.
To this end, we need two definitions and a proposition.

######  Definition 5.16 ([100]).

Let $G$ be a graph, $s\in V(G)$ and $\alpha,\beta\in\mathbb{N}$. An
$(s,\alpha,\beta)$-layering is a pair $({\cal L},f)$ where ${\cal
L}=(L_{0},L_{1},\ldots,L_{\ell})$ for $\ell$ being the longest distance of a
vertex from $s$, such that each $L_{i}\in{\cal L}$ (called a layer) contains
all vertices at distance $i$ from $s$, and $f:{\cal
L}\rightarrow\\{0,1,\ldots,\alpha-1\\}$ such that for each $L_{i}\in{\cal L}$,
$f(L_{i})$ (called the label of $L_{i}$) equals
$\lfloor\frac{i}{\beta}\rfloor\mod\alpha$.

######  Definition 5.17 ([100]).

Let $G$ be a graph with an $(s,\alpha,\beta)$-layering $({\cal L},f)$. Given
$q\in\\{0,1,\ldots,\alpha-1\\}$, a $q$-piece of $({\cal L},f)$ is any maximal
set of consecutive layers ${\cal P}=(L_{i},L_{i+1},\ldots,L_{j})\subseteq{\cal
L}$ such that no $x,y,z\in\\{i,i+1,\ldots,j\\}$ satisfy $f(L_{x})=f(L_{z})\neq
q$, $x<y<z$, and $f(L_{x})\neq f(L_{y})$.

######  Proposition 5.18 ([32]).

Subgraph Hitting is in FPT parameterized by the treewidth $\mathsf{tw}$ of the
input graph. Specifically, it is solvable in time $g(\mathsf{tw},{\cal
F})\cdot n$.

Having these two definitions and proposition at hand, we can reiterate the
algorithm of [100]. Fix some $\varepsilon>0$, $\alpha=\frac{1}{\varepsilon}$
and $\beta=c_{\cal F}$ where $c_{\cal F}$ be the maximum size of a graph in
the forbidden set $\cal F$. Given a (presumably) pseudo-disk graph $G$, pick
some $s\in V(G)$ (arbitrarily), and compute the $(s,\alpha,\beta)$-layering
$({\cal L},f)$. Then, for every $i\in\\{0,1,\ldots,\alpha-1\\}$, it performs
the following procedure:

  1. 1.

Let ${\bf P}_{i}$ be the collection of $i$-pieces.

  2. 2.

For every piece ${\cal P}\in{\bf P}_{i}$, if the treewidth of $G[\bigcup{\cal
P}]$ is not bounded by $c\cdot\alpha\cdot\beta\cdot r^{2}$ where $c$ is some
constant specified in [100] and $r$ is the local-radius of $G$ (which is upper
bounded by $\Delta$), then output “invalid input”; otherwise, use the
algorithm in Proposition 5.18 to solve $\Pi$ optimally on input
$G[\bigcup{\cal P}]$, and let $S_{\cal P}$ denote the result.

  3. 3.

Compute $S_{i}=\bigcup_{{\cal P}\in{\bf P}_{i}}S_{\cal P}$.

Afterwards, return the set $S$ of minimum size among the sets
$S_{1},S_{2},\ldots,S_{\alpha}$.

In [100], it is proved that this algorithm returns a
$(1+\epsilon)$-approximate solution for Subgraph Hitting on the class of disk
graphs. It is immediate that all of the arguments also work for pseudo-disk
graphs. Now, we consider the time complexity of the algorithm. Clearly, in
each iteration, the first step can be done in time $O(\Delta\cdot n)$ by using
breadth-first search. Then, by Proposition 5.18 and since $\sum_{{\cal
P}\in{\cal P}_{i}}V(G[\bigcup{\cal P}])=O(n)$, the second step can be done in
time $g(\epsilon,{\cal F},\Delta)\cdot n$. The third step can clearly be done
in linear time. So, since there are $O(\frac{1}{\epsilon})$ iterations, we
conclude that the total running time is of the form
$f(\varepsilon,\mathcal{F},\Delta)\cdot n$. ∎

######  Corollary 5.19.

Subgraph Hitting on the class $\mathcal{G}$ of pseudo-disk graphs admits an
approximation scheme with running time $f(\varepsilon,\mathcal{F})\cdot n\log
n+O(m)$ for some function $f$, where $n$ and $m$ are the numbers of vertices
and edges in the input graph $G\in\mathcal{G}$, respectively.

###### Proof.

By Lemma 5.14, we know that $\mathcal{G}$ is of clique-dependent polynomial
expansion (and in particular, clique-dependent bounded expansion). Then
combining Lemma 5.15 and Theorem 1.3 directly proves the corollary. ∎

Also, the result for $k$-Subgraph Isomorphism in Theorem 5.11 has the
following corollary.

######  Corollary 5.20.

$k$-Subgraph Isomorphism on any class $\mathcal{G}$ of fat-object graphs or
pseudo-disk graphs can be solved in $f(k)\cdot n\log n+O(m)$ time for some
function $f$, where $n$ and $m$ are the number of vertices and edges in the
input graph $G\in\mathcal{G}$, respectively.

A graph is a string graph if it is the intersection graph of a set of
connected geometric objects in the plane. Theorem 1.4 can be applied to string
graphs, yielding the following result.

See 1.6

###### Proof.

It was known that string graphs with an excluded biclique form a graph class
with strongly sublinear separators [66]. Thus, the class of string graphs is
of biclique-dependent polynomial expansion (and in particular, biclique-
dependent bounded expansion). By Theorem 1.4, to prove the corollary, it
suffices to give a $(2+\varepsilon)$-approximation algorithm for Bipartite
Subgraph Hitting on $\mathcal{G}$ with running time
$f(\varepsilon,\mathcal{F},\Delta)\cdot n^{2}$, where $\Delta$ is the maximum
degree of the input graph $G\in\mathcal{G}$. Define
$\mathcal{G}_{\Delta}\subseteq\mathcal{G}$ as the subclass consisting of
graphs of maximum degree at most $\Delta$. Note that $\omega(G)\leq\Delta+1$
for all $G\in\mathcal{G}_{\Delta}$. So $\mathcal{G}_{\Delta}$ is of polynomial
expansion for all $\Delta\mathbb{N}$. By Theorem 1.2, for each
$\Delta\mathbb{N}$, there exists a function $f_{\Delta}$ such that Subgraph
Hitting on $\mathcal{G}_{\Delta}$ admits an approximation scheme with running
time $f_{\Delta}(\varepsilon,\mathcal{F})\cdot n^{1+\alpha}$. An approximation
scheme for Subgraph Hitting naturally implies a
$(2+\varepsilon)$-approximation algorithm for Bipartite Subgraph Hitting.
Therefore, writing
$f(\varepsilon,\mathcal{F},\Delta)=f_{\Delta}(\varepsilon,\mathcal{F})$
completes the proof. ∎

##  6 Hitting shallow minors

In this section, we show that the (Induced) Shallow-Minor Hitting problem can
be reduced to (Induced) Subgraph Hitting, and thus Theorem 1.1 as well as all
its applications can be extended to (Induced) Shallow-Minor Hitting.

######  Lemma 6.1.

Given a finite set $\mathcal{F}$ of graphs and an integer $d\geq 0$, one can
compute another finite set $\mathcal{F}^{\prime}$ of graphs such that a graph
contains a (induced) $d$-shallow minor in $\mathcal{F}$ iff it contains a
(induced) subgraph in $\mathcal{F}^{\prime}$.

###### Proof.

Let $\delta=\max_{F\in\mathcal{F}}|V(F)|$. We define $\mathcal{F}^{\prime}$ as
the set of all graphs $F^{\prime}$ such that
$|V(F^{\prime})|\leq(d+1)\delta^{2}$ and $F^{\prime}$ contains $F$ as an
induced $d$-shallow minor for some $F\in\mathcal{F}$. Clearly, if a graph $G$
contains some $F^{\prime}\in\mathcal{F}^{\prime}$ as a (induced) subgraph,
then it contains some $F\in\mathcal{F}$ as a (induced) $d$-shallow minor. For
the other direction, assume $G$ contains some $F\in\mathcal{F}$ as a (induced)
$d$-shallow minor. For a vertex $v\in V(F)$, denote by $G_{v}$ the connected
subgraph of $G$ that is contracted to $v$. In each $G_{v}$, we pick a
reference vertex $\xi_{v}\in V(G_{v})$. The diameter of $G_{v}$ is at most
$d$. Thus, for each edge $(u,v)\in E(F)$, there exists a path
$\pi_{u,v}=(v_{0},v_{1},\dots,v_{r})$ in $G$ between $\xi_{u}$ and $\xi_{v}$
such that (i) $\pi_{u,v}$ contains at most $2(d+1)$ vertices and (ii) there
exists $i\in[r]$ such that $v_{0},\dots,v_{i-1}\in V(G_{u})$ and
$v_{i},\dots,v_{r}\in V(G_{v})$. Let $F_{0}^{\prime}$ be the subgraph of $G$
consisting of the paths $\pi_{u,v}$ for all $(u,v)\in E(F)$. We now add to
$F_{0}^{\prime}$ some extra edges. Specifically, for each $v\in V(F)$, we add
to $F_{0}^{\prime}$ all edges of $G_{v}$ with both endpoints in
$V(F_{0}^{\prime})$. Also, for each $(u,v)\in E(F)$, we add to
$F_{0}^{\prime}$ all edges of $G$ with one endpoint in $F_{0}^{\prime}\cap
G_{u}$ and the other endpoint in $F_{0}^{\prime}\cap G_{v}$. Let $F^{\prime}$
denote the resulting new graph, which is still a subgraph of $G$. As
$|E(F)|\leq\delta^{2}/2$, we have
$|V(F^{\prime})|=|V(F_{0}^{\prime})|\leq(d+1)\delta^{2}$. Furthermore,
$F^{\prime}$ contains $F$ as an induced $d$-shallow minor. To see this, notice
that $F^{\prime}\cap G_{v}$ is connected for all $v\in V(F)$, simply because
$F_{0}^{\prime}\cap G_{v}$ is connected. Furthermore, there is an edge in
$F^{\prime}$ between $F^{\prime}\cap G_{u}$ and $F^{\prime}\cap G_{v}$ iff
$(u,v)\in E(F)$. Thus, $F$ can be obtained from $F^{\prime}$ by contracting
each $F^{\prime}\cap G_{v}$ to a single vertex. It follows that
$F^{\prime}\in\mathcal{F}^{\prime}$. Clearly, $F^{\prime}$ is a subgraph of
$G$. If $F$ is an induced minor of $G$, we claim that $F^{\prime}$ is an
induced subgraph of $G$. Consider two vertices $x,y\in V(F^{\prime})$ such
that $(x,y)\in E(G)$. If $x,y\in G_{v}$ for some $v\in V(F)$, then $(x,y)\in
E(F^{\prime})$ by our construction. If $x\in G_{u}$ and $y\in G_{v}$ where
$u\neq v$, then $(u,v)\in E(F)$ because $F$ is an induced minor of $G$. Again
by our construction, $(x,y)\in E(F^{\prime})$. ∎

Recall that in (Induced) Shallow-Minor Hitting, we are given a graph $G$, a
forbidden list $\mathcal{F}$, an integer $d\geq 0$, and the goal is to compute
a minimum set $S\subseteq V(G)$ such that $G-S$ does not contain any graph in
$\mathcal{F}$ as a $d$-shallow minor. Consider an instance $(G,\mathcal{F},d)$
of (Induced) Shallow-Minor Hitting. We can use the above lemma to compute a
set $\mathcal{F}^{\prime}$ of graphs, which only depends on $\mathcal{F}$ and
$d$. Now a subset $S\subseteq V(G)$ is a solution of the (Induced) Shallow-
Minor Hitting instance $(G,\mathcal{F},d)$ iff it is a solution of the
(Induced) Subgraph Hitting instance $(G,\mathcal{F}^{\prime})$. On the other
hand, there is a trivial reduction from (Induced) Subgraph Hitting to
(Induced) Shallow-Minor Hitting, because (induced) subgraphs are exactly
(induced) 0-shallow minors. As such, Theorem 1.1 can be extended to (Induced)
Shallow-Minor Hitting.

######  Theorem 6.2.

Let $\mathcal{G}$ be any hereditary graph class of bounded expansion. If
(Induced) Shallow-Minor Hitting on $\mathcal{G}$ admits an approximation
scheme with running time $f_{0}(\varepsilon,\mathcal{F},d,\Delta)\cdot n^{c}$
for some function $f_{0}$, then the same problem also admits an approximation
scheme with running time $f(\varepsilon,\mathcal{F},d)\cdot n^{c}$ for some
function $f$, where $n$ is the number of vertices in the input graph
$G\in\mathcal{G}$ and $\Delta$ is the maximum degree of $G$.

Also, all of our algorithmic results derived from Theorem 1.1 can be extended
to (Induced) Shallow-Minor Hitting, with the same running time.

## Acknowledgement

The authors would like to thank anonymous reviewers for their detailed
comments on an earlier version of this paper. Specifically, the comments of
one reviewer helped us substantially improve the running time of our
approximation schemes.

## References

  * [1] Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi.  Polylogarithmic approximation algorithms for weighted-$\mathcal{F}$-deletion problems.  ACM Trans. Algorithms, 16(4):51:1–51:38, 2020.  doi:10.1145/3389338.
  * [2] Manuel Aprile, Matthew Drescher, Samuel Fiorini, and Tony Huynh.  A tight approximation algorithm for the cluster vertex deletion problem.  In Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021, Proceedings 22, pages 340–353. Springer, 2021.
  * [3] Per Austrin, Subhash Khot, and Muli Safra.  Inapproximability of vertex cover and independent set in bounded degree graphs.  Theory of Computing, 7(1):27–43, 2011.
  * [4] Zongwen Bai, Jianhua Tu, and Yongtang Shi.  An improved algorithm for the vertex cover p${}_{\mbox{3}}$ problem on graphs of bounded treewidth.  CoRR, abs/1603.09448, 2016.  URL: http://arxiv.org/abs/1603.09448.
  * [5] Brenda S. Baker.  Approximation algorithms for np-complete problems on planar graphs.  J. ACM, 41(1):153–180, 1994.  URL: http://doi.acm.org/10.1145/174644.174650, doi:10.1145/174644.174650.
  * [6] R Balasubramanian, Michael R Fellows, and Venkatesh Raman.  An improved fixed-parameter algorithm for vertex cover.  Information Processing Letters, 65(3):163–168, 1998.
  * [7] Reuven Bar-Yehuda and Shimon Even.  A local-ratio theorem for approximating the weighted vertex cover problem.  Annals of Discrete Mathematics, 25(27-46):50, 1985.
  * [8] Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz.  Minimum vertex cover in rectangle graphs.  Computational Geometry, 44(6-7):356–364, 2011.
  * [9] Nadja Betzler, Robert Bredereck, Rolf Niedermeier, and Johannes Uhlmann.  On bounded-degree vertex deletion parameterized by treewidth.  Discrete Applied Mathematics, 160(1-2):53–60, 2012.
  * [10] Rodica Boliac, Kathie Cameron, and Vadim V. Lozin.  On computing the dissociation number and the induced matching number of bipartite graphs.  Ars Comb., 72, 2004.
  * [11] Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk.  A fast branching algorithm for cluster vertex deletion.  Theory of Computing Systems, 58:357–376, 2016.
  * [12] Marin Bougeret and Ignasi Sau.  How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?  Algorithmica, 81(10):4043–4068, 2019.
  * [13] Christoph Brause and Rastislav Krivos-Bellus.  On a relation between k-path partition and k-path vertex cover.  Discret. Appl. Math., 223:28–38, 2017.
  * [14] Boštjan Brešar, Marko Jakovac, Ján Katrenič, Gabriel Semanišin, and Andrej Taranenko.  On the vertex k-path cover.  Discrete Applied Mathematics, 161(13-14):1943–1949, 2013.
  * [15] Bostjan Bresar, Tim Kos, Rastislav Krivos-Bellus, and Gabriel Semanisin.  Hitting subgraphs in _P_ ${}_{\mbox{4}}$-tidy graphs.  Appl. Math. Comput., 352:211–219, 2019.
  * [16] Noah Brüstle, Tal Elbaz, Hamed Hatami, Onur Kocer, and Bingchan Ma.  Approximation algorithms for hitting subgraphs.  In Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings 32, pages 370–384. Springer, 2021.
  * [17] Jonathan F Buss and Judy Goldsmith.  Nondeterminism within p^.  SIAM Journal on Computing, 22(3):560–572, 1993.
  * [18] Leizhen Cai and Yufei Cai.  Incompressibility of h-free edge modification problems.  Algorithmica, 71(3):731–757, 2015.
  * [19] Kathie Cameron and Pavol Hell.  Independent packings in structured graphs.  Math. Program., 105(2-3):201–213, 2006.
  * [20] Radovan Cervený, Pratibha Choudhary, and Ondrej Suchý.  On kernels for d-path vertex cover.  CoRR, abs/2107.12245, 2021.
  * [21] Radovan Cervený and Ondrej Suchý.  Faster FPT algorithm for 5-path vertex cover.  In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, pages 32:1–32:13, 2019.
  * [22] Radovan Cervený and Ondrej Suchý.  Generating faster algorithms for d-path vertex cover.  CoRR, abs/2111.05896, 2021.  URL: https://arxiv.org/abs/2111.05896.
  * [23] Timothy M. Chan.  Finding triangles and other small subgraphs in geometric intersection graphs.  In 34rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2023\.
  * [24] L Sunil Chandran and Fabrizio Grandoni.  Refined memorisation for vertex cover.  In Parameterized and Exact Computation: First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings 1, pages 61–70. Springer, 2004.
  * [25] Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Yi-Zhi Liu, Peter Rossmanith, and Somnath Sikdar.  An $o^{*}(1.4658^{n})$-time exact algorithm for the maximum bounded-degree-1 set problem.  In Proceedings of the 31st workshop on combinatorial mathematics and computation theory, pages 9–18, 2014.
  * [26] Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Yi-Zhi Liu, Peter Rossmanith, and Somnath Sikdar.  Moderately exponential time algorithms for the maximum bounded-degree-1 set problem.  Discrete Applied Mathematics, 251:114–125, 2018.
  * [27] Jianer Chen, Henning Fernau, Iyad A. Kanj, and Ge Xia.  Parametric duality and kernelization: Lower bounds and upper bounds on kernel size.  In Volker Diekert and Bruno Durand, editors, STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings, volume 3404 of Lecture Notes in Computer Science, pages 269–280. Springer, 2005.
  * [28] Jianer Chen, Iyad A Kanj, and Weijia Jia.  Vertex cover: further observations and further improvements.  Journal of Algorithms, 41(2):280–301, 2001.
  * [29] Jianer Chen, Iyad A. Kanj, and Ge Xia.  Improved upper bounds for vertex cover.  Theor. Comput. Sci., 411(40-42):3736–3756, 2010.
  * [30] Miroslav Chlebík and Janka Chlebíková.  Crown reductions for the minimum weighted vertex cover problem.  Discret. Appl. Math., 156(3):292–312, 2008.
  * [31] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak.  A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond.  In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1158–1167. IEEE, 2020.  doi:10.1109/FOCS46700.2020.00111.
  * [32] Bruno Courcelle.  The monadic second-order logic of graphs. i. recognizable sets of finite graphs.  Information and computation, 85(1):12–75, 1990.
  * [33] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.  doi:10.1007/978-3-319-21275-3.
  * [34] Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk.  Hitting forbidden subgraphs in graphs of bounded treewidth.  Information and Computation, 256:62–82, 2017.
  * [35] Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan Van Leeuwen, and Marcin Wrochna.  Polynomial kernelization for removing induced claws and diamonds.  Theory of Computing Systems, 60:615–636, 2017.
  * [36] Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt.  Approximation schemes for first-order definable optimisation problems.  In 21st Annual IEEE Symposium on Logic in Computer Science (LICS’06), pages 411–420. IEEE, 2006.
  * [37] Mark De Berg, Hans L Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C Van Der Zanden.  A framework for exponential-time-hypothesis–tight algorithms and lower bounds in geometric intersection graphs.  SIAM Journal on Computing, 49(6):1291–1331, 2020.
  * [38] Holger Dell and Dieter Van Melkebeek.  Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses.  Journal of the ACM (JACM), 61(4):1–27, 2014.
  * [39] Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos.  Subexponential parameterized algorithms on bounded-genus graphs and _H_ -minor-free graphs.  J. ACM, 52(6):866–893, 2005.  doi:10.1145/1101821.1101823.
  * [40] Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew 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, pages 37:1–37:15, 2019.
  * [41] Anders Dessmark, Klaus Jansen, and Andrzej Lingas.  The maximum k-dependent and f-dependent set problem.  In Algorithms and Computation, 4th International Symposium, ISAAC ’93, Hong Kong, December 15-17, 1993, Proceedings, pages 88–98, 1993\.
  * [42] N Safina Devi, Aniket C Mane, and Sounaka Mishra.  Computational complexity of minimum p4 vertex cover problem for regular and k1, 4-free graphs.  Discrete Applied Mathematics, 184:114–121, 2015.
  * [43] Irit Dinur and Samuel Safra.  On the hardness of approximating minimum vertex cover.  Annals of mathematics, pages 439–485, 2005.
  * [44] Pål Grønås Drange, Markus Dregi, and Pim van’t Hof.  On the computational complexity of vertex integrity and component order connectivity.  Algorithmica, 76(4):1181–1202, 2016.
  * [45] Zdeněk Dvořák.  Constant-factor approximation of the domination number in sparse graphs.  European Journal of Combinatorics, 34(5):833–840, 2013.
  * [46] Zdenek Dvorák.  Thin graph classes and polynomial-time approximation schemes.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1685–1701, 2018.  doi:10.1137/1.9781611975031.110.
  * [47] Zdeněk Dvořák.  Baker game and polynomial-time approximation schemes.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2227–2240. SIAM, 2020.
  * [48] Zdeněk Dvořák.  Approximation metatheorems for classes with bounded expansion.  arXiv preprint arXiv:2103.08698, 2021.
  * [49] Zdeněk Dvořák, Daniel Král, and Robin Thomas.  Testing first-order properties for subclasses of sparse graphs.  Journal of the ACM (JACM), 60(5):1–24, 2013.
  * [50] Zdeněk Dvořák and Abhiruk Lahiri.  Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs.  arXiv preprint arXiv:2105.01780, 2021.
  * [51] Zdeněk Dvořák and Sergey Norin.  Strongly sublinear separators and polynomial expansion.  SIAM Journal on Discrete Mathematics, 30(2):1095–1101, 2016.  arXiv:https://doi.org/10.1137/15M1017569, doi:10.1137/15M1017569.
  * [52] Eduard Eiben, William Lochet, and Saket Saurabh.  A polynomial kernel for paw-free editing.  In 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), pages 10:1–10:15, 2020.
  * [53] Eduard Eiben, Diptapriyo Majumdar, and MS Ramanujan.  On the lossy kernelization for connected treedepth deletion set.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 201–214. Springer, 2022.
  * [54] Jessica Enright and Kitty Meeks.  Deleting edges to restrict the size of an epidemic: a new application for treewidth.  Algorithmica, 80(6):1857–1889, 2018.
  * [55] Thomas Erlebach, Klaus Jansen, and Eike Seidel.  Polynomial-time approximation schemes for geometric intersection graphs.  SIAM J. Comput., 34(6):1302–1323, 2005.  doi:10.1137/S0097539702402676.
  * [56] Michael R. Fellows, Jiong Guo, Hannes Moser, and Rolf Niedermeier.  A generalization of nemhauser and trotter’s local optimization theorem.  J. Comput. Syst. Sci., 77(6):1141–1158, 2011.
  * [57] Samuel Fiorini, Gwenaël Joret, and Oliver Schaudt.  Improved approximation algorithms for hitting 3-vertex paths.  In Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings 18, pages 238–249. Springer, 2016.
  * [58] Samuel Fiorini, Gwenaël Joret, and Oliver Schaudt.  Improved approximation algorithms for hitting 3-vertex paths.  Mathematical Programming, 182(1-2):355–367, 2020.
  * [59] Samuel Fiorini, R Krithika, NS Narayanaswamy, and Venkatesh Raman.  Approximability of clique transversal in perfect graphs.  Algorithmica, 80(8):2221–2239, 2018.
  * [60] Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi.  Subquadratic kernels for implicit 3-hitting set and 3-set packing problems.  ACM Trans. Algorithms, 15(1):13:1–13:44, 2019.
  * [61] Fedor V Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh.  Planar f-deletion: Approximation, kernelization and optimal fpt algorithms.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 470–479. IEEE, 2012.
  * [62] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Decomposition of map graphs with applications.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 60:1–60:15, 2019.
  * [63] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Finding, hitting and packing cycles in subexponential time on unit disk graphs.  Discret. Comput. Geom., 62(4):879–911, 2019.  doi:10.1007/s00454-018-00054-x.
  * [64] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh.  Bidimensionality and geometric graphs.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1563–1575, 2012.
  * [65] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh.  Excluded grid minors and efficient polynomial-time approximation schemes.  J. ACM, 65(2):10:1–10:44, 2018.  doi:10.1145/3154833.
  * [66] Jacob Fox and János Pach.  A separator theorem for string graphs and its applications.  Combinatorics, Probability and Computing, 19(3):371–390, 2010.
  * [67] Jacob Fox and János Pach.  Computing the independence number of intersection graphs.  In Proceedings of the twenty-second annual ACM-SIAM Symposium on Discrete algorithms, pages 1161–1165. SIAM, 2011.
  * [68] Ajinkya Gaikwad and Soumen Maity.  Further parameterized algorithms for the f-free edge deletion problem.  Theoretical Computer Science, 933:125–137, 2022.
  * [69] Jakub Gajarskỳ, Petr Hliněnỳ, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar.  Kernelization using structural parameters on sparse graph classes.  Journal of Computer and System Sciences, 84:219–242, 2017.
  * [70] Esther Galby, Andrea Munaro, and Shizhou Yang.  Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs.  To appear in the 39th International Symposium on Computational Geometry (SoCG), 2023.
  * [71] Robert Ganian, Fabian Klute, and Sebastian Ordyniak.  On structural parameterizations of the bounded-degree vertex deletion problem.  Algorithmica, 83(1):297–336, 2021.
  * [72] Lito Julius Goldmann.  Parameterized Complexity of Modifying Graphs to be Biclique-free.  PhD thesis, Institute of Software, 2021.
  * [73] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz.  Deciding first-order properties of nowhere dense graphs.  Journal of the ACM (JACM), 64(3):1–32, 2017.
  * [74] Marina Groshaus, Pavol Hell, Sulamita Klein, Loana Tito Nogueira, and Fábio Protti.  Cycle transversals in bounded degree graphs.  Electronic Notes in Discrete Mathematics, 35:189–195, 2009.
  * [75] Daniel Gross, Monika Heinig, Lakshmi Iswara, L William Kazmierczak, Kristi Luttrell, John T Saccoman, and Charles Suffel.  A survey of component order connectivity models of graph theoretic networks.  WSEAS Transactions on Mathematics, 12:895–910, 2013.
  * [76] Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michał Włodarczyk.  Losing treewidth by separating subsets.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1731–1749. SIAM, 2019.
  * [77] Eran Halperin.  Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs.  SIAM Journal on Computing, 31(5):1608–1623, 2002.
  * [78] Sariel Har-Peled and Kent Quanrud.  Notes on approximation algorithms for polynomial-expansion and low-density graphs.  CoRR, abs/1603.03098, 2016.  URL: http://arxiv.org/abs/1603.03098, arXiv:1603.03098.
  * [79] Sariel Har-Peled and Kent Quanrud.  Approximation algorithms for polynomial-expansion and low-density graphs.  SIAM Journal on Computing, 46(6):1712–1744, 2017.
  * [80] Dov Harel and Robert Endre Tarjan.  Fast algorithms for finding nearest common ancestors.  siam Journal on Computing, 13(2):338–355, 1984.
  * [81] Monika R Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian.  Faster shortest-path algorithms for planar graphs.  Journal of Computer and System Sciences, 55(1):3–23, 1997.  URL: https://www.sciencedirect.com/science/article/pii/S0022000097914938, doi:https://doi.org/10.1006/jcss.1997.1493.
  * [82] Sun-Yuan Hsieh, Van Bang Le, and Sheng-Lung Peng.  On the d-claw vertex deletion problem.  In Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings 27, pages 591–603. Springer, 2021.
  * [83] Falk Hüffner, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier.  Fixed-parameter algorithms for cluster vertex deletion.  Theory of Computing Systems, 47(1):196–217, 2010.
  * [84] Bart MP Jansen and Michał Włodarczyk.  Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 900–913, 2022.
  * [85] George Karakostas.  A better approximation ratio for the vertex cover problem.  ACM Transactions on Algorithms (TALG), 5(4):1–8, 2009.
  * [86] František Kardoš, Ján Katrenič, and Ingo Schiermeyer.  On computing the minimum 3-path vertex cover and dissociation number of graphs.  Theoretical Computer Science, 412(50):7009–7017, 2011.
  * [87] Marek Karpinski and Alexander Zelikovsky.  Approximating dense cases of covering problems.  Citeseer, 1996.
  * [88] Klara Kedem, Ron Livne, János Pach, and Micha Sharir.  On the union of jordan regions and collision-free translational motion amidst polygonal obstacles.  Discrete & Computational Geometry, 1(1):59–71, 1986.
  * [89] Subhash Khot and Oded Regev.  Vertex cover might be hard to approximate to within 2- $\varepsilon$.  Journal of Computer and System Sciences, 74(3):335–349, 2008.
  * [90] Philip Klein, Serge A Plotkin, and Satish Rao.  Excluded minors, network decomposition, and multicommodity flow.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 682–690, 1993.
  * [91] Mithilesh Kumar and Daniel Lokshtanov.  A 2lk kernel for l-component order connectivity.  In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017\.
  * [92] Mrinal Kumar, Sounaka Mishra, N Safina Devi, and Saket Saurabh.  Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization.  Theoretical Computer Science, 526:90–96, 2014.
  * [93] Michael Lampis.  A kernel of order 2k- clogk for vertex cover.  Information Processing Letters, 111(23-24):1089–1091, 2011.
  * [94] Hoang-Oanh Le and Van Bang Le.  Complexity of the cluster vertex deletion problem on h-free graphs.  In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [95] Hung Le and Cuong Than.  Greedy spanners in euclidean spaces admit sublinear separators.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3287–3310. SIAM, 2022.