Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes

arXiv2207.06660MaRDI QIDQ6404945FDOQ6404945

Authors: Jung-Ho Ahn, Jinha Kim, O-joung Kwon 

Publication date: 14 July 2022

Abstract: Let $mathcalF$ be a family of graphs, and let $p,r$ be nonnegative integers. The extsc{$(p,r,mathcalF)$-Covering} problem asks whether for a graph $G$ and an integer $k$, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^{p}setminus{N}_G^r[D]$ has no induced subgraph isomorphic to a graph in $mathcalF$, where $G^p$ is the $p$-th power of $G$. The extsc{$(p,r,mathcalF)$-Packing} problem asks whether for a graph $G$ and an integer $k$, $G^p$ has $k$ induced subgraphs $H_1,ldots,H_k$ such that each $H_i$ is isomorphic to a graph in $mathcalF$, and for distinct $i,jin1,ldots,k$, the distance between $V(H_i)$ and $V(H_j)$ in $G$ is larger than $r$. We show that for every fixed nonnegative integers $p,r$ and every fixed nonempty finite family $mathcalF$ of connected graphs, the extsc{$(p,r,mathcalF)$-Covering} problem with $pleq2r+1$ and the extsc{$(p,r,mathcalF)$-Packing} problem with $pleq2lfloorr/2floor+1$ admit almost linear kernels on every nowhere dense class of graphs, and admit linear kernels on every class of graphs with bounded expansion, parameterized by the solution size $k$. We obtain the same kernels for their annotated variants. As corollaries, we prove that extsc{Distance-$r$ Vertex Cover}, extsc{Distance-$r$ Matching}, extsc{$mathcalF$-Free Vertex Deletion}, and extsc{Induced-$mathcalF$-Packing} for any fixed finite family $mathcalF$ of connected graphs admit almost linear kernels on every nowhere dense class of graphs and linear kernels on every class of graphs with bounded expansion. Our results extend the results for extsc{Distance-$r$ Dominating Set} by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017), and the result for extsc{Distance-$r$ Independent Set} by Pilipczuk and Siebertz (EJC 2021).

This page was built for publication: Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404945)