Improved deterministic algorithms for weighted matching and packing problems

Based on the method of ( n, k ) -universal sets, we present a deterministic parameterized algorithm for the weighted r d-matching problem with time complexity O ∗ ( 4 ( r − 1 ) k + o ( k ) ), improving the previous best upper bound O ∗ ( 4 r k + o ( k ) ). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O ∗ ( 1 6 k + o ( k ) ), improving the previous best result O ∗ ( 21. 2 6 k ). For the weighted r -set packing problem, we present a deterministic parameterized algorithm with time complexity O ∗ ( 2 ( 2 r − 1 ) k + o ( k ) ), improving the previous best result O ∗ ( 2 2 r k + o ( k ) ). The algorithm, when applied to the unweighted 3-set packing problem, has running time O ∗ ( 3 2 k + o ( k ) ), improving the previous best result O ∗ ( 43. 6 2 k + o ( k ) ). Moreover, for the weighted r -set packing and weighted r d-matching problems, we give a kernel of size O ( k r ), which is the first kernelization algorithm for the problems on weighted versions.

Authors

• Jianer Chen
• Qilong Feng
• Yang Liu College of Computer Science and Software Engineering, Shenzhen University
• Songjian Lu
• Jianxin Wang

Keywords

• r d-matching
• r -set packing
• Randomized divide-and-conquer
• ( n, k ) -universal set