Shortest Two Disjoint Paths in Polynomial Time
Shortest Two Disjoint Paths in Polynomial Time
复制标题
多项式时间内最短两条不相交路径
DOI：
10.1007/978-3-662-43948-7_18
复制
发表时间：
2014
影响因子：
0.5
通讯作者：
T. Husfeldt
中科院分区：
文献类型：
--
作者：
Andreas Björklund;T. Husfeldt
给定一个无向图和两对顶点$（s_i，t_i）$，对于$i\in\{1，2\}$，我们证明了存在一个多项式时间的Monte Carlo算法，该算法可以找到连接$s_i$和$t_i$的最小总长度的不相交路径，或者得出结论，很可能根本不存在这样的路径。我们的算法适用于顶点和边不相交的版本的问题。
我们的算法是代数的，并结合Mulmuley，Vazirani和Vazirani的隔离引理使用多项式环$Z_2[x]$和$Z_4[x]$上的永久式来检测解。本文通过对Valiant 1979年关于环Z_{2^l}$上积和式的算法的改进，给出了一个求环Z_{2^l}$上积和式的快速算法.
Given an undirected graph and two pairs of vertices $(s_i,t_i)$ for $i\in\{1,2\}$ we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining $s_i$ and $t_i$ for $i\in\{1,2\}$ respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem.
Our algorithm is algebraic and uses permanents over the polynomial rings $Z_2[x]$ and $Z_4[x]$ in combination with Mulmuley, Vazirani and Vazirani's isolation lemma to detect a solution. We develop a fast algorithm for permanents over these rings by modifying Valiant's 1979 algorithm for the permanent over $Z_{2^l}$.