RANDOMIZED DIVIDE-AND-CONQUER: IMPROVED PATH, MATCHING, AND PACKING ALGORITHMS
We propose a randomized divide-and-conquer technique that leads to improved randomized and deterministic algorithms for NP-hard PATH, MATCHING, and PACKING problems. For the parameterized max-path problem, our randomized algorithm runs in time O(4(k)k(2.7)m) and polynomial space (where m is the number of edges in the input graph), improving the previous best randomized algorithm for the problem that runs in time O(5.44(k)km) and exponential space. Our randomized algorithms for the parameterized MAX r-d MATCHING and MAX r-set PACKING problems run in time 4((r-1)k)n(O(1)) and polynomial space, improving the previous best algorithms for the problems that run in time 10.88(rk)n(O(1)) and exponential space. Moreover, our randomized algorithms can be derandomized to result in significantly improved deterministic algorithms for the problems, and they can be extended to solve other matching and packing problems.
divide-and-conquer path matching randomized algorithm set packing