Abstract:
We present a reduction procedure that takes an arbitrary instance of the r -Set Packing problem and produces an equivalent instance whose number of elements is in O(kr−1), where k is the input parameter. Such parameterized reductions are known as kernelization algorithms, and a reduced instance is called a problem kernel. Our result improves on previously known kernelizations by a factor of k. In particular, the number of elements in a 3-Set Packing kernel is improved from a cubic function of the parameter to a quadratic one.
Citation:
Abu-Khzam, F. N. (2010). An improved kernelization algorithm for r-Set Packing. Information Processing Letters, 110(16), 621-624.
