2026/07/16 by Tomohiro Koana, Soh Kumabe
#cs.DS
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 Sd1,d2 denote the subdivided star with d1 branches of length 1 and d2 branches of length 2. We obtain kernels with O(k2) vertices and O(k3) edges for P5=S0,2, for S1,2, and for every Sd1,1, kernels with O(k4) vertices and O(k6) edges for every fixed Sd1,d2 with d1≥ 1, and a kernel with O(k2) vertices and O(k4) 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 S0,d. For every d≥ 3 and every ε>0, \textscS0,d-Packing does not admit a compression of size O(kd-ε) 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.