Kernelization for Weighted 3-Set Packing Problem

Packing and Matching problems form an important class of NP-hard problems, which have attracted lots of attention in the study of parameterized algorithms and kernelization of the problems. In this paper, we mainly study the kernelization algorithm for weighted 3-Set Packing problem. By further analyzing the problem structure, this paper proposes and proves two reduction rules for the weighted 3-Set Packing problem. Firstly, the numbers of sets in given instance of weighted 3-Set Packing problem containing two fixed elements and containing only one element are bounded. Based on the two bounded numbers, the total number of sets in the instance is bounded. Moreover, the processes of getting the two bounded numbers bring two efficient reduction rules for the weighted 3-Set Packing problem. Applying the two reduction rules, a kernel of size 27k\+3-36k\+2+12k can be obtained, which is the first kernel result for weighted 3-Set Packing problem. The kernelization process for weighted 3-Set Packing problem can also be applied to the weighted 3D-Matching problem, which results in the same kernel size as that of the weighted 3-Set Packing problem.