An O*(3.53(3k))-time parameterized algorithm for the 3-set packing problem

作者：Wang Jianxin^*; Feng Qilong; Chen Jianer

来源：Theoretical Computer Science, 2011, 412(18): 1745-1753.

DOI：10.1016/j.tcs.2010.12.048

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

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.53(3k)) for the 3-SET PACKING problem, improving the previous best upper bound O*(4.61(3k)).

• 出版日期2011-4-15
• 单位中南大学