2026-08-25T17:34:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27223 2026-08-25T13:18:18Z ddc:004 open_access

Kernelization for H-Packing Revisited Koana, Tomohiro Kumabe, Soh Parameterized Complexity Kernelization H-Packing H-Packing asks whether a graph G contains k vertex-disjoint copies of a fixed pattern graph H. Via the standard reduction to d-Set Packing, one obtains generic kernels with O(k^{|V(H)|-1}) vertices and O(k^|V(H)|) edges. We revisit the question of beating these bounds for specific patterns H. Our main results concern subdivided stars. Let S_{d₁,d₂} denote the subdivided star with d₁ branches of length 1 and d₂ branches of length 2. We obtain kernels with O(k²) vertices and O(k³) edges for P₅ = S_{0,2}, for S_{1,2}, and for every S_{d₁,1}, kernels with O(k⁴) vertices and O(k⁶) edges for every fixed S_{d₁,d₂} with d₁ ≥ 1, and a kernel with O(k²) vertices and O(k⁴) edges for the paw. Our proofs proceed in two steps. First, we reduce to instances in which all but a small part of the graph is independent, or in which the graph has a small vertex cover. Second, we reduce the independent side by keeping only a bounded number of witness vertices for each subset of the small part. On the negative side, we prove a lower bound for the line S_{0,d}. For every d ≥ 3 and every ε > 0, S_{0,d}-Packing does not admit a compression of size O(k^{d-ε}) unless NP ⊆ coNP/poly. Thus, deleting a single vertex from the pattern may, surprisingly, make kernelization provably harder, showing that compressibility of H-Packing is not monotone under taking induced subgraphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomohiro Koana and Soh Kumabe 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.87 urn:nbn:de:0030-drops-272239 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.87 eng https://creativecommons.org/licenses/by/4.0/legalcode