A Problem Kernelization for Graph Packing

摘要

For a fixed connected graph H, we consider the NP-complete H-packing problem, where, given an undirected graph G and an integer k≥0, one has to decide whether there exist k vertex-disjoint copies of H in G. We give a problem kernel of O(k{sup}(|V(H)|-1) vertices, that is, we provide a polynomial-time algorithm that reduces a given instance of H-packing to an equivalent instance with at most O(k{sup}(|V(H)|-1) vertices. In particular, this result specialized to H being a triangle improves a problem kernel for Triangle Packing from O(k{sup}3) vertices by Fellows et al. [WG 2004] to O(k{sup}2) vertices.