×

Randomized divide-and-conquer: improved path, matching, and packing algorithms. (English) Zbl 1191.68849

Summary: 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.

MSC:

68W20 Randomized algorithms
68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI Link