Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials

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.