2026-07-30T13:34:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19307 2024-03-06T11:03:43Z ddc:004 open_access

Unified Almost Linear Kernels for Generalized Covering and Packing Problems on Nowhere Dense Classes Ahn, Jungho Kim, Jinha Kwon, O-joung kernelization independent set dominating set covering packing Let ℱ be a family of graphs, and let p,r be nonnegative integers. For a graph G and an integer k, the (p,r,ℱ)-Covering problem asks whether there is a set D ⊆ V(G) of size at most k such that if the p-th power of G has an induced subgraph isomorphic to a graph in ℱ, then it is at distance at most r from D. The (p,r,ℱ)-Packing problem asks whether G^p has k induced subgraphs H₁,…,H_k such that each H_i is isomorphic to a graph in ℱ, and for i,j ∈ {1,…,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 ℱ of connected graphs, (p,r,ℱ)-Covering with p ≤ 2r+1 and (p,r,ℱ)-Packing with p ≤ 2⌊r/2⌋+1 admit almost linear kernels on every nowhere dense class of graphs, parameterized by the solution size k. As corollaries, we prove that Distance-r Vertex Cover, Distance-r Matching, ℱ-Free Vertex Deletion, and Induced-ℱ-Packing for any fixed finite family ℱ of connected graphs admit almost linear kernels on every nowhere dense class of graphs. Our results extend the results for Distance-r Dominating Set by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017), and for Distance-r Independent Set by Pilipczuk and Siebertz (EJC 2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jungho Ahn and Jinha Kim and O-joung Kwon 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.5 urn:nbn:de:0030-drops-193072 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.5 eng https://creativecommons.org/licenses/by/4.0/legalcode