Parameterized algorithms for weighted matching and packing problems

The weighted mm-d matching and mm-set packing problems (m≥3m≥3) are usually solved through approximation algorithms. In this paper, we define the parameterized versions of these problems and study their algorithms. For the weighted mm-set packing problem, we develop a parameterized algorithm of running time O(12.8mknO(1))O(12.8mknO(1)), which is based on the recently improved color-coding technology and dynamic programming. By refining the techniques, we also develop a more efficient parameterized algorithm of running time O(12.8(m−1)knO(1))O(12.8(m−1)knO(1)) for the weighted mm-d matching problem, which is a restricted version of the weighted mm-set packing problem.