Jungho Ahn (안정호), Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
Jungho Ahn (안정호), Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
Let $\mathcal{F}$ be a family of graphs, and let $p$ and $r$ be nonnegative integers. The $(p,r,\mathcal{F})$-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$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$, where …