Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
复制标题
DOI：
10.1016/j.jcss.2018.01.004
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
G. Gutin;F. Reidl;Magnus Wahlström;M. Zehavi
中科院分区：
文献类型：
--
作者：
G. Gutin;F. Reidl;Magnus Wahlström;M. Zehavi
我们引入了颜色编码的增强来设计确定性多项式空间参数化算法。我们的方法旨在通过利用解决方案的特殊结构来减少随机选择的数量。使用我们的方法，我们推导出用于 k 内部分支的多项式空间 O⁎(3.86 k)-时间（指数空间 O⁎(3.41 k)-时间）确定性算法，改进了之前解决此问题的最快指数空间 O⁎(5.14 k)-时间算法。（符号 O⁎ 隐藏了多项式因子。）我们还设计了多项式空间 O⁎((2 e) k+ o (k))-时间（指数空间 O⁎(4.32 k)-时间）确定性算法，用于弧形有向图上的 k-彩色分支和平面边缘彩色图上的 k-彩色完美匹配。在 k-Colorful Out-Branching 中，给定一个弧色有向图 D，确定 D 是否具有至少具有 k 种颜色的弧的外分支。 k-Colorful Perfect Matching 的定义类似。为了获得我们的多项式空间算法，我们证明了（n，k，α k）-分裂器（α⩾ 1），特别是（n，k）-完美哈希族可以使用多项式空间以多项式延迟一一枚举。
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.86 k)-time (exponential-space O⁎(3.41 k)-time) deterministic algorithm for k-Internal Out-Branching, improving upon the previously fastest exponential-space O⁎(5.14 k)-time algorithm for this problem.(The notation O⁎ hides polynomial factors.) We also design polynomial-space O⁎((2 e) k+ o (k))-time (exponential-space O⁎(4.32 k)-time) deterministic algorithms for k-Colorful Out-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.