2017/06/12 by Gregory Gutin, Felix Reidl, Gutin, Gregory +5
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1706.03698
openalex publication_date 2017/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In recent years, several powerful techniques have been developed to design\n em randomized polynomial-space parameterized algorithms. In this paper, we\nintroduce an enhancement of color coding to design deterministic\npolynomial-space parameterized algorithms. Our approach aims at reducing the\nnumber of random choices by exploiting the special structure of a solution.\nUsing our approach, we derive the following deterministic algorithms (see\nIntroduction for problem definitions).\n 1. Polynomial-space O^*(3.86k)-time (exponential-space O^*(3.41k)-time)\nalgorithm for sc k-Internal Out-Branching, improving upon the previously\nfastest em exponential-space O^*(5.14k)-time algorithm for this problem.\n 2. Polynomial-space O^*((2e)k+o(k))-time (exponential-space\nO^*(4.32k)-time) algorithm for sc k-Colorful Out-Branching on\narc-colored digraphs and sc k-Colorful Perfect Matching on planar\nedge-colored graphs.\n To obtain our polynomial space algorithms, we show that (n,k,\α\nk)-splitters (\α\≥ 1) and in particular (n,k)-perfect hash families\ncan be enumerated one by one with polynomial delay.\n