An improved kernelization for P-2-packing
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)). (C) 2009 Elsevier B.V. All rights reserved.
kernelization p-2-packing combinatorial problems crown decomposition