#
Shortest two disjoint paths in polynomial time

##
Jack Cheng

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 quotient ring
$\mathbb{Z}_4[X]/(X^m)$ in combination with Mulmuley, Vazirani and Vazirani's
isolation lemma to detect a solution. We develop a fast algorithm for
permanents over said ring by modifying Valiant's 1979 algorithm for the
permanent over $\mathbb{Z}_{2^l}$.

(From a paper by Andreas Björklund and Thore Husfeldt at
ICALP 2014.)