2026-07-26T02:20:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19448 2024-03-06T11:04:05Z ddc:004 open_access

Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs Jansen, Bart M. P. Roy, Shivesh K. kernelization weighted problems graph packing sunflower lemma bounded expansion nowhere dense We study the kernelization complexity of the Weighted H-Packing problem on sparse graphs. For a fixed connected graph H, in the Weighted H-Packing problem the input is a graph G, a vertex-weight function w : V(G) → ℕ, and positive integers k, t. The question is whether there exist k vertex-disjoint subgraphs H₁, …, H_k of G such that H_i is isomorphic to H for each i ∈ [k] and the total weight of these k ⋅ |V(H)| vertices is at least t. It is known that the (unweighted) H-Packing problem admits a kernel with 𝒪(k^{|V(H)|-1}) vertices on general graphs, and a linear kernel on planar graphs and graphs of bounded genus. In this work, we focus on case that H is a clique on h ≥ 3 vertices (which captures Triangle Packing) and present a linear-vertex kernel for Weighted K_h-Packing on graphs of bounded expansion, along with a kernel with 𝒪(k^{1+ε}) vertices on nowhere-dense graphs for all ε > 0. To obtain these results, we combine two powerful ingredients in a novel way: the Erdős-Rado Sunflower lemma and the theory of sparsity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bart M. P. Jansen and Shivesh K. Roy 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.29 urn:nbn:de:0030-drops-194488 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.29 eng https://creativecommons.org/licenses/by/4.0/legalcode