Shortest Two Disjoint Paths in Polynomial Time
Andreas Björklund, Thore Husfeldt · SIAM Journal on Computing · 2019
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 ring $Z_4[X]$ in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring $Z_t[X]$, where $t$ is a power of $2$, by modifying Valiant's 1979 algorithm for the permanent over $Z_t$.