Shortest two disjoint paths in polynomial time

Given an undirected graph and two pairs of vertices (si, ti) for i ϵ{ 1, 2} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ϵ{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 Z4[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 Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Z