A quadratic kernel for 3-set packing

Abstract

We present a reduction procedure that takes an arbitrary instance of the 3-Set Packing problem and produces an equivalent instance whose number of elements is bounded by a quadratic function of the input parameter. Such parameterized reductions are known as kernelization algorithms, and each reduced instance is called a problem kernel. Our result improves on previously known kernelizations and can be generalized to produce improved kernels for the r-Set Packing problem whenever r is a fixed constant. Improved kernelization for r-Dimensional-Matching can also be inferred.