An improved kernelization for P2-packing
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
The P 2 -packing problem is a generalized matching problem and is known to be NP-hard. A kernelization algorithm for the parameterized P 2 -packing problem is a polynomial time algorithm that on an instance (G, k) of the problem produces another instance (G , k ) such that k k and that (G, k) is a yes-instance if and only if (G , k ) is a yes-instance. The graph G in the reduced instance is called a kernel. We provide new structural analysis and develop a new kernelization algorithm for the problem that produces a kernel of at most 7k vertices. This improves the previous best kernelization algorithm that produces a kernel of 15k vertices. Based on the new kernel, we present a parameterized algorithm of running time O * (17.66 k ) for the problem, improving the previous best upper bound O * (32 k ). 2009 Elsevier B.V.