An O ∗ ( 3.5 3 3 k ) -time parameterized algorithm for the 3-set packing problem

A parameterized algorithm for the well-known NP-complete problem 3-set packing is presented. The algorithm is based on the following new approaches: (1) an efficient algorithm for problem instances in which one element is known for each of the 3-sets in a solution packing (i. e. , type-1 instances); (2) an efficient algorithm for problem instances in which at least two elements are known for each of the 3-sets in a solution packing (i. e. , type-2 instances); and (3) an effective decomposition of a general instance of 3-set packing into two instances of type-1 and type-2, respectively, whose base sets are disjoint. This technique results in an improved parameterized algorithm of running time O ∗ ( 3. 5 3 3 k ) for the 3-set packing problem, improving the previous best upper bound O ∗ ( 4. 6 1 3 k ).

Authors

• Jianxin Wang
• Qilong Feng
• Jianer Chen

Keywords

• 3-set packing
• Divide and conquer
• ( n, k ) -universal set