* [96] Euiwoong Lee.  Partitioning a graph into small pieces with applications to path transversal.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1546–1558. SIAM, 2017.
  * [97] Wenjun Li, Huan Peng, and Yongjie Yang.  Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations.  Theoretical Computer Science, 906:83–93, 2022.
  * [98] Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi.  Fpt-approximation for FPT problems.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 199–218, 2021.
  * [99] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi.  Subexponential parameterized algorithms on disk graphs (extended abstract).  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2005–2031. SIAM, 2022.
  * [100] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi.  A framework for approximation schemes on disk graphs.  In 34rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2023\.
  * [101] Vadim V. Lozin and Dieter Rautenbach.  Some results on graphs without long induced paths.  Inf. Process. Lett., 88(4):167–171, 2003.
  * [102] Carsten Lund and Mihalis Yannakakis.  The approximation of maximum subgraph problems.  In International Colloquium on Automata, Languages, and Programming, pages 40–51. Springer, 1993.
  * [103] Dániel Marx.  Efficient approximation schemes for geometric problems?  In Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, pages 448–459, 2005\.
  * [104] Dániel Marx and RB Sandeep.  Incompressibility of h-free edge modification problems: Towards a dichotomy.  Journal of Computer and System Sciences, 125:25–58, 2022.
  * [105] David W Matula and Leland L Beck.  Smallest-last ordering and clustering and graph coloring algorithms.  Journal of the ACM (JACM), 30(3):417–427, 1983.
  * [106] Balázs F Mezei, Marcin Wrochna, and Stanislav Živnỳ.  Ptas for sparse general-valued csps.  ACM Transactions on Algorithms, 19(2):1–31, 2023.
  * [107] Gary L Miller, Shang-Hua Teng, William Thurston, and Stephen A Vavasis.  Separators for sphere-packings and nearest neighbor graphs.  Journal of the ACM (JACM), 44(1):1–29, 1997.
  * [108] Burkhard Monien and Ewald Speckenmeyer.  Ramsey numbers and an approximation algorithm for the vertex cover problem.  Acta Informatica, 22(1):115–123, 1985.
  * [109] Hannes Moser, Rolf Niedermeier, and Manuel Sorge.  Exact combinatorial algorithms and experiments for finding maximum k-plexes.  J. Comb. Optim., 24(3):347–373, 2012.
  * [110] Jaroslav Nešetřil and Patrice Ossona De Mendez.  Grad and classes with bounded expansion i. decompositions.  European Journal of Combinatorics, 29(3):760–776, 2008.
  * [111] Jaroslav Nešetřil and Patrice Ossona De Mendez.  Grad and classes with bounded expansion ii. algorithmic aspects.  European Journal of Combinatorics, 29(3):777–791, 2008.
  * [112] Jaroslav Nešetřil and Patrice Ossona De Mendez.  On nowhere dense graphs.  European Journal of Combinatorics, 32(4):600–617, 2011.
  * [113] Jaroslav Nešetřil and Patrice Ossona De Mendez.  Sparsity: graphs, structures, and algorithms, volume 28.  Springer Science & Business Media, 2012.
  * [114] Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R Wood.  Characterisations and examples of graph classes with bounded expansion.  European Journal of Combinatorics, 33(3):350–373, 2012.
  * [115] Jaroslav Nešetřil and Patrice Ossona de Mendez.  Grad and classes with bounded expansion ii. algorithmic aspects.  European Journal of Combinatorics, 29(3):777–791, 2008.  URL: https://www.sciencedirect.com/science/article/pii/S0195669807000571, doi:https://doi.org/10.1016/j.ejc.2006.07.014.
  * [116] Rolf Niedermeier and Peter Rossmanith.  Upper bounds for vertex cover further improved.  In STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science Trier, Germany, March 4–6, 1999 Proceedings 16, pages 561–570. Springer, 1999.
  * [117] Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos.  Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover.  Discret. Appl. Math., 152(1-3):229–245, 2005.
  * [118] Yury L. Orlovich, Alexandre Dolgui, Gerd Finke, Valery S. Gordon, and Frank Werner.  The complexity of dissociation set problems in graphs.  Discret. Appl. Math., 159(13):1352–1366, 2011.
  * [119] Michał Pilipczuk.  Problems parameterized by treewidth tractable in single exponential time: A logical approach.  In International Symposium on Mathematical Foundations of Computer Science, pages 520–531. Springer, 2011.
  * [120] Felix Reidl, Fernando Sánchez Villaamil, and Konstantinos Stavropoulos.  Characterising bounded expansion by neighbourhood complexity.  European Journal of Combinatorics, 75:152–168, 2019.
  * [121] Miguel Romero, Marcin Wrochna, and Stanislav Živnỳ.  Treewidth-pliability and ptas for max-csps.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 473–483. SIAM, 2021.
  * [122] Ignasi Sau and Uéverton dos Santos Souza.  Hitting forbidden induced subgraphs on bounded treewidth graphs.  Information and Computation, 281:104812, 2021.
  * [123] Hadas Shachnai and Meirav Zehavi.  A multivariate framework for weighted FPT algorithms.  J. Comput. Syst. Sci., 89:157–189, 2017.
  * [124] Arezou Soleimanfallah and Anders Yeo.  A kernel of order $2k-c$ for vertex cover.  Discrete Mathematics, 311(10):892–895, 2011.
  * [125] Ulrike Stege and Michael Ralph Fellows.  An improved fixed parameter tractable algorithm for vertex cover.  Technical report/Departement Informatik, ETH Zürich, 318, 1999\.
  * [126] Jirı Sgall Tomas Ebenlendr, Petr Kolman.  An approximation algorithm for bounded degree deletion.  In Preprint, 2009.
  * [127] Dekel Tsur.  l-path vertex cover is easier than l-hitting set for small l.  CoRR, abs/1906.10523, 2019.  URL: http://arxiv.org/abs/1906.10523.
  * [128] Dekel Tsur.  Faster parameterized algorithm for cluster vertex deletion.  Theory of Computing Systems, 65(2):323–343, 2021.
  * [129] Dekel Tsur.  An o∗(2.619k) algorithm for 4-path vertex cover.  Discret. Appl. Math., 291:1–14, 2021.
  * [130] Jianhua Tu.  A survey on the k-path vertex cover problem.  Axioms, 11(5):191, 2022.
  * [131] Jianhua Tu and Zemin Jin.  An FPT algorithm for the vertex cover p${}_{\mbox{4}}$ problem.  Discret. Appl. Math., 200:186–190, 2016.
  * [132] Jianhua Tu, Lidong Wu, Jing Yuan, and Lei Cui.  On the vertex cover p${}_{\mbox{3}}$ problem parameterized by treewidth.  J. Comb. Optim., 34(2):414–425, 2017.
  * [133] Jianhua Tu and Wenli Zhou.  A factor 2 approximation algorithm for the vertex cover p3 problem.  Information Processing Letters, 111(14):683–686, 2011.
  * [134] Erik Jan van Leeuwen.  Better approximation schemes for disk graphs.  In Lars Arge and Rusins Freivalds, editors, Algorithm Theory - SWAT 2006, 10th ScandinavianWorkshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings, volume 4059 of Lecture Notes in Computer Science, pages 316–327. Springer, 2006.  doi:10.1007/11785293\\_30.
  * [135] David P Williamson and David B Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.
  * [136] Mingyu Xiao.  Linear kernels for separating a graph into components of bounded size.  J. Comput. Syst. Sci., 88:260–270, 2017.
  * [137] Mingyu Xiao.  On a generalization of nemhauser and trotter’s local optimization theorem.  J. Comput. Syst. Sci., 84:97–106, 2017.
  * [138] Mingyu Xiao and Shaowei Kou.  Kernelization and parameterized algorithms for 3-path vertex cover.  In Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, pages 654–668, 2017.
  * [139] Mingyu Xiao and Hiroshi Nagamochi.  Exact algorithms for maximum independent set.  Information and Computation, 255:126–146, 2017.
  * [140] Jie You, Jianxin Wang, and Yixin Cao.  Approximate association via dissociation.  Discrete Applied Mathematics, 219:202–209, 2017.
  * [141] An Zhang, Yong Chen, Zhi-Zhong Chen, and Guohui Lin.  Improved approximation algorithms for path vertex covers in regular graphs.  Algorithmica, 82(10):3041–3064, 2020.
  * [142] Zhao Zhang, Xiaoting Li, Yishuo Shi, Hongmei Nie, and Yuqing Zhu.  Ptas for minimum k-path vertex cover in ball graph.  Information Processing Letters, 119:9–13, 2017.
  * [143] Zhao Zhang, Xiaoting Li, Yishuo Shi, Hongmei Nie, and Yuqing Zhu.  PTAS for minimum k-path vertex cover in ball graph.  Inf. Process. Lett., 119:9–13, 2017.
  * [144] Zhao Zhang, Weili Wu, Lidan Fan, and Ding-Zhu Du.  Minimum vertex cover in ball graphs through local search.  Journal of Global Optimization, 59(2):663–671, 2014.
  * [145] Xuding Zhu.  Colouring graphs with bounded generalized colouring number.  Discrete Mathematics, 309(18):5562–5568, 2009.

##  Appendix A Other Related Works

We first remark that constant-approximation algorithms are known for various
problems on bounded-expansion graphs, including various versions of
Independent Set and Dominating Set [45] as well as all monotone maximization
problems expressible in first-order logic [48]. Next, we consider the generic
(Induced) Subgraph Hitting problem and some (though not all) of its special
cases that were studied independently in the literature. A thorough survey is
beyond the scope of our work. Here, our goal is only to mention some of the
known results. Further, we do not survey results concerning Subgraph
Isomorphism since the literature about it is as rich as the literature on
Subgraph Hitting. Still, since it is highly relevant to our work, we note that
on graphs of bounded expansion, testing first-order properties can be done in
linear time [49], which implies that Subgraph Isomorphism can be solved in
linear time for any fixed $k$ (the size of the pattern).

The generic (Induced) Subgraph Hitting problem is a special case of (or, more
precisely, trivially reducible to) $d$-Hitting Set, and hence all results for
$d$-Hitting Set (e.g., approximation algorithm, FPT algorithms and kernels
[135, 33]) directly transfer. For further discussion on the possibility of
better approximation algorithms for (Induced) Subgraph Hitting, we refer to
[16]. On bounded-treewidth graphs, the problem was studied in [34, 122] from
the perspective of parameterized complexity. We remind that, on planar graphs,
the classical work of Baker [5] yields a PTAS, which can be extended to minor-
free graphs [36, 47] and unit-disk graphs [65]. We remark that the generic
edge-deletion version of the problem was also considered in the literature
(e.g., see [54, 68]). Further, there is a substantial body of works on special
cases of the edge-deletion version dedicated to hitting specific graphs on
only few vertices such as claws, paws and diamonds, particularly from the
perspective of kernelization (see, e.g., [97, 35, 52, 18, 104] for a few
examples).

Vertex Cover: The Vertex Cover problem is widely considered to be the most
extensively studied problem in parameterized complexity, and is often
considered a testbed for the introduction of new notions and techniques [33].
It is long known that this problem can be approximated within ratio $2$ [135],
while ratio $(2-\epsilon)$ is impossible under the Unique Games Conjecture
(UGC) [89]. More involved techniques yield slightly better ratios [7, 108, 77,
85]; for example, consider the ratio of $2-\Theta(\frac{1}{\sqrt{\log n}})$ by
[85]. Under the assumption P$\neq$NP, the known lower bound is weaker [43].
Constants better than $2$ are known for various graph classes, such as bounded
degree graphs, where we know of matching upper [77] and lower [3] bounds
(under the UGC) for the approximation ratio, dense graphs [87], and rectangle
graphs [8]. Further, Vertex Cover was already known to admit a PTAS on bounded
expansion graphs [79] and an EPTAS on disk graphs [55, 134, 100].

From the perspective of parameterized complexity, there has been long races to
achieve the best possible running times on general graphs and on bounded
degree graphs, as well as when considering exact exponential-time algorithms
(see [6, 17, 28, 24, 28, 116, 29, 125, 139] for a few of the papers); we only
briefly mention that the best known parameterized algorithm for general graphs
achieves the bound $1.28^{k}\cdot n^{O(1)}$ [29]. The problem is long known to
admit a kernel of size $O(k^{2})$ [17], which is essentially optimal unless
the polynomial hierarchy collapses [38]. Nevertheless, the number of vertices
in the kernel can be reduced to $2k$ [28] with slight improvements given in
[124, 30], but it is unlikely that it can be reduced to $(2-\epsilon)k$ [27].
Further, Bidimesnionality theory for minor-free and unit-disk graphs [39, 64,
63] as well as map graphs [62] yields subexponential FPT algorithms.

(Induced) $P_{k}$-Hitting: Clearly, Vertex Cover is the special case of
$P_{k}$-Hitting (also known as $k$-Path Vertex Cover) when $k=2$. Still, even
for small values of $k$, it is harder. For example, for $k=3$, it is APX-
complete on bipartite graphs [92] (whereas Vertex Cover is solvable in
polynomial time), and for $k=4$, it is APX-complete on cubic bipartite graphs
[42]. Still, for $k=3$, it is solvable in polynomial-time on various graph
classes [10, 13, 15, 19, 101, 118] such as $P_{5}$-free graphs [13]. Lee [96]
gave an FPT $O(\log k)$-approximation algorithm where the parameter is $k$.
His result was generalized and improved upon (in terms of running time) by
Gupta et al. [76]. For $k=3$, a $2$-approximation algorithm was given in [133]
(improving upon [86]). Recently, for $k\geq 3$, Brüstle [16] presented a
($k-\frac{1}{2}$)-approximation algorithm (even for a more general case of
hitting trees). Other approximation algorithms for this problem can be found
in [26, 141]. We note that the problem admits an EPTAS on disk graphs [100]
for $3\leq k\leq 5$, and a PTAS on ball graphs for any fixed $k$ [143]. Exact
exponential-time algorithms for $k=3$ were developed in [86, 26, 25, 139].
Also, for various fixed values of $k\geq 3$, the problem was intensively
studied in parameterized complexity: parameterized algorithms were developed
in [21, 22, 127, 129, 131, 4, 123, 132] and kernels were developed in [138,
20, 56, 137, 138]. Further, the Bidimesnionality theory for minor-free and
unit-disk graphs [39, 64, 63] as well as map graphs [62] yields subexponential
FPT algorithms. For more information on $P_{k}$-Hitting, we refer to the
survey of [130].

It is known that Induced $P_{3}$-Hitting is equivalent to the Cluster Vertex
Deletion problem (where the objective is to delete a minimum number of
vertices to attain a cluster graph, which is a collection of cliques), which
has been extensively studied in the literature. As such, it trivially has a
$3$-approximation (polynomial-time) algorithm. The first non-trivial
approximation algorithm was a $\frac{5}{3}$\- approximation due to You et al.
[140]. Shortly afterward, Fiorini et al. gave a $\frac{7}{3}$-approximation
[57], and subsequently a $\frac{9}{4}$-approximation [58]. Afterwards, a
$2$-approximation was found [2], which is easily seen to be optimal under the
UGC (by a simple reduction from Vertex Cover). The problem also received
attention from the perspectives of FPT algorithms [11, 83, 128] and
kernelization [60]. Further, it was studied on special graph classes such as
$H$-free graphs [94].

Degree Modulator: Notice that Degree Modulator, where the goal is to delete a
minimum number of vertices to reduce the maximum degree of the graph to be
$k$, is equivalent to hitting stars of size $k+1$. When $k=0$, we derive
Vertex Cover, and when $k=1$, we derive $P_{2}$-Hitting, both discussed
earlier. So, here, we only consider the case where $k\geq 2$. First, we remark
that the FPT $O(\log k)$-approximation algorithm by Gupta et al. [76] is also
noted to apply to this problem. However, previously, a randomized (polynomial-
time) $O(\log k)$-approximation algorithm was already known [126]. A matching
inapproximability result was given in [40]. The problem is also known to admit
an EPTAS on disk graphs [100]. Moreover, FPT algorithms, kernels and
W[1]-hardness results for this problem (sometimes referred to by a different
name) parameterized by $k$ plus (or only by) the solution size or a structural
measure such as treewidth of the graph were given in [9, 71, 117, 56, 109, 41,
98]. We note that the complexity of the problem of hitting induced stars on
$k+1$ vertices, also known as induced $k$-claws, was also previously studied
(see, e.g., [82]).

(Induced) $C_{k}$-Hitting: First, note that the (Induced) $C_{k}$-Hitting
problem only makes sense for $k\geq 3$. The restriction of the case where
$k=3$ (i.e., when we aim to hit triangles) to disk graphs admits a
subexponential FPT algorithm (when parameterized by solution size) [99] as
well as an EPTAS [100]. Further, the parameterized complexity of (Induced)
$C_{k}$-Hitting with respect to treewidth was studied in [119], and a
dichotomy concerning its membership in P was given in [74].

$K_{k}$-Hitting and (Induced) Biclique Hitting: Approximation and
parameterized algorithms for $K_{k}$-Hitting on perfect graphs were given in
[59]. Additionally, the parameterized complexity of (Induced) Biclique Hitting
was studied in [72].

Component Order Connectivity: The objective of this problem is delete a
minimum number of vertices in order to hit all connected graphs of size at
most $k$. Clearly, Vertex Cover is its special case when $k=2$. For Component
Order Connectivity, Bidimesnionality theory for minor-free and unit-disk
graphs [39, 64, 63] as well as map graphs [62] yields subexponential FPT
algorithms. Drange et al. [44] provided an FPT and a kernel for Component
Order Connectivity parameterized by $k$ plus the solution size, and, in
addition, studied the complexity of the problem on special graph classes.
Iproved $O(ks)$-vertex kernels were given by [91, 136], where $s$ is the
solution size. Moreover, an FPT approximation scheme with respect to treewidth
was given in [98]. Additional results can be found in the survey [75].

Treedepth Modulator: The objective of this problem is to delete a minimum-
sized $t$-treedepth modulator in the given graph, that is, a minimum number of
vertices whose deletion from the given graph yields a graph of treedepth at
most $t$. Here, $t\in\mathbb{N}$ is a given fixed constant. The problem can be
phrased as a subgraph hitting problem where all subgraphs are of size bounded
by a function of $t$. The computation and utility of treedepth modulators were
studied from the perspective of parameterized complexity (see, e.g., [12, 53,
69]).