Kernelization for weighted 3-Set Packing problem
Academic Article
Overview
Additional Document Info
View All
Overview
abstract
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 27 k 3-36 k 2+12 k 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.
