论文标题
统一的几乎线性内核，用于一般覆盖和包装问题，无处浓密的班级
Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
论文作者
论文摘要
令$ \ mathcal {f} $为图形家庭，让$ p，r $为非负整数。 The \textsc{$(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[D]$ has no induced subgraph isomorphic to a graph in $ \ Mathcal {f} $，其中$ g^p $是$ g $的$ p $ - th power。 \ textsc {$（p，r，\ nathcal {f}）$ - 包装}问题是否询问是否适用于图$ g $和整数$ k $，$ g^p $具有$ k $ watused $ k $诱导子$ h_1，\ ldots，\ ldots，h_k $，h_k $ $ i，j \ in \ {1，\ ldots，k \} $，$ v（h_i）$和$ v（h_j）$ g $ in $ g $之间的距离大于$ r $。 我们表明，对于每个固定的非负整数$ p，r $和每个固定的有限族$ \ Mathcal {f} $连接的图形，\ textsc {$（p，p，r，r，\ nathcal {f}）$ - covering} $ p \ p \ leq2r+1 $和 \textsc{$(p,r,\mathcal{F})$-Packing} problem with $p\leq2\lfloor r/2\rfloor+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$.我们为其带注释的变体获得了相同的内核。作为定性，我们证明\ textsc {distry- $ r $ pertex cover}，\ textsc {distry- $ r $匹配}，\ textsc {$ \ natercal {f} $ - 免费的vertex deletion}，\ textsc {induccation-prackcal- $ \ $ \ nive fircal {$ packing part}连接的图形在每个无处可构成的图形和线性内核上几乎是线性内核，并具有有界膨胀的每个图形。我们的结果扩展了Drange等人的\ textsc {distaimsc {distaim-$ r $ opination set}的结果。 （Stacs 2016）和Eickmeyer等。 （ICALP 2017），以及Pilipczuk和Siebertz（EJC 2021）的\ textsc {distem- $ r $独立set}的结果。
Let $\mathcal{F}$ be a family of graphs, and let $p,r$ be nonnegative integers. The \textsc{$(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[D]$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$, where $G^p$ is the $p$-th power of $G$. The \textsc{$(p,r,\mathcal{F})$-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 $\mathcal{F}$, and for distinct $i,j\in \{1, \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 $\mathcal{F}$ of connected graphs, the \textsc{$(p,r,\mathcal{F})$-Covering} problem with $p\leq2r+1$ and the \textsc{$(p,r,\mathcal{F})$-Packing} problem with $p\leq2\lfloor r/2\rfloor+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 \textsc{Distance-$r$ Vertex Cover}, \textsc{Distance-$r$ Matching}, \textsc{$\mathcal{F}$-Free Vertex Deletion}, and \textsc{Induced-$\mathcal{F}$-Packing} for any fixed finite family $\mathcal{F}$ 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 \textsc{Distance-$r$ Dominating Set} by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017), and the result for \textsc{Distance-$r$ Independent Set} by Pilipczuk and Siebertz (EJC 2021).
