Solving Parameterized Problems by Mixing Color Coding-Related Techniques.
Meirav Zehavi · arXiv (Cornell University) · 2014
Abstract. In the past two decades, several breakthrough techniques, known as “color coding-related techniques”, lead to the design of extremely fast parameterized algorithms. In this paper, we introduce a family of strategies, that we call “mixing strategies”, for applying these techniques, developing even faster, closer to optimal, parameterized algorithms. Our strategies combine the following novel ideas. • Mixing narrow sieves and representative sets, two independent color coding-related techniques. • For certain “disjointness conditions”, improving the best known computation of representative sets. • Mixing divide-and-color-based preprocessing with the computation mentioned in the previous item, speeding-up standard representative sets-based algorithms. • Cutting the universe into small pieces in two special manners, one used in the mix mentioned in the previous item, and the other mixed with a non-standard representative sets-based algorithm to improve its running time. Note that the first item implies that representative sets are relevant to the design of fast randomized parameterized algorithms, and not only deterministic ones. We demonstrate the usefulness of our strate-gies by obtaining the following results. We first solve the well-studied k-Internal Out-Branching problem in deterministic time O∗(5.139k) and randomized time O∗(3.617k), improving upon the pre-vious best deterministic time O∗(6.855k) and randomized time O∗(4k). To this end, we establish a relation between “problematic ” out-trees and maximum matching computations in graphs. We then present a unified approach to improve the O ∗ running times of the previous best deterministic algo-rithms for the classic k-Path, k-Tree, r-Dimensional k-Matching and Graph Motif problems, including their weighted versions, from O∗(2.619k), O∗(2.619k), O∗(2.619(r−1)k) and O∗(2.6192k) to O∗(2.597k), O∗(2.597k), O∗(2.597(r−1)k) and O∗(2.5972k), respectively. Finally, we solve the Weighted 3-Set k-Packing problem in deterministic time O∗(8.097k), significantly improving upon the previous best O∗(12.155k) deterministic time. ar X iv