English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate a fundamental vertex-deletion problem called (Induced)Subgraph Hitting: given a graph $G$ and a set $\mathcal{F}$ of forbiddengraphs, the goal is to compute a minimum-sized set $S$ of vertices of $G$ suchthat $G-S$ does not contain any graph in $\mathcal{F}$ as an (induced)subgraph. This is a generic problem that encompasses many well-known problemsthat were extensively studied on their own, particularly (but not only) fromthe perspectives of both approximation and parameterization.  In this paper, we study the approximability of the problem on a large varietyof graph classes. Our first result is a linear-time$(1+\varepsilon)$-approximation reduction from (Induced) Subgraph Hitting onany graph class $\mathcal{G}$ of bounded expansion to the same problem onbounded degree graphs within $\mathcal{G}$. This directly yields linear-size$(1+\varepsilon)$-approximation lossy kernels for the problems on anybounded-expansion graph classes. Our second result is a linear-timeapproximation scheme for (Induced) Subgraph Hitting on any graph class$\mathcal{G}$ of polynomial expansion, based on the local-search framework ofHar-Peled and Quanrud [SICOMP 2017]. This approximation scheme can be appliedto a more general family of problems that aim to hit all subgraphs satisfying acertain property $\pi$ that is efficiently testable and has bounded diameter.Both of our results have applications to Subgraph Hitting (not induced) on wideclasses of geometric intersection graphs, resulting in linear-size lossykernels and (near-)linear time approximation schemes for the problem.

Efficient Approximation for Subgraph-Hitting Problems in Sparse Graphs and Geometric Intersection Graphs