Improved deterministic algorithms for weighted matching and packing problems

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