Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874673 | Journal of Computer and System Sciences | 2018 | 17 Pages |
Abstract
We introduce an enhancement of color coding to design deterministic polynomial-space parameterized algorithms. Our approach aims at reducing the number of random choices by exploiting the special structure of a solution. Using our approach, we derive polynomial-space Oâ(3.86k)-time (exponential-space Oâ(3.41k)-time) deterministic algorithm for k-Internal Out-Branching, improving upon the previously fastest exponential-space Oâ(5.14k)-time algorithm for this problem. (The notation Oâ hides polynomial factors.) We also design polynomial-space Oâ((2e)k+o(k))-time (exponential-space Oâ(4.32k)-time) deterministic algorithms for k-ColorfulOut-Branching on arc-colored digraphs and k-Colorful Perfect Matching on planar edge-colored graphs. In k-Colorful Out-Branching, given an arc-colored digraph D, decide whether D has an out-branching with arcs of at least k colors. k-Colorful Perfect Matching is defined similarly. To obtain our polynomial-space algorithms, we show that (n,k,αk)-splitters (α⩾1) and in particular (n,k)-perfect hash families can be enumerated one by one with polynomial delay using polynomial space.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gregory Gutin, Felix Reidl, Magnus Wahlström, Meirav Zehavi,