Shortest Two Disjoint Paths in Polynomial Time
(2014) Automata, Languages, and Programming : 41st International Colloquium, ICALP 2014 8572. p.211222 Abstract
 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 edgedisjoint 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}$.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/5152872
 author
 Björklund, Andreas ^{LU} and Husfeldt, Thore ^{LU}
 organization
 publishing date
 2014
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Lecture Notes in Computer Science
 editor
 Javier, Esparza ; Pierre, Fraigniaud ; Thore, Husfeldt and Elias, Koutsoupias
 volume
 8572
 pages
 12 pages
 publisher
 Springer
 conference name
 Automata, Languages, and Programming : 41st International Colloquium, ICALP 2014
 conference location
 Copenhagen, Denmark
 conference dates
 20140708  20140811
 external identifiers

 wos:000352643300020
 scopus:84904214727
 ISSN
 03029743
 16113349
 ISBN
 9783662439470
 DOI
 10.1007/9783662439487_18
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 988ffff45e2d489ba1ff6e3883a9a421 (old id 5152872)
 date added to LUP
 20160401 10:31:45
 date last changed
 20211006 02:41:12
@inproceedings{988ffff45e2d489ba1ff6e3883a9a421, abstract = {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 edgedisjoint versions of the problem. <br/><br> <br/><br> 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}$.}, author = {Björklund, Andreas and Husfeldt, Thore}, booktitle = {Lecture Notes in Computer Science}, editor = {Javier, Esparza and Pierre, Fraigniaud and Thore, Husfeldt and Elias, Koutsoupias}, isbn = {9783662439470}, issn = {03029743}, language = {eng}, pages = {211222}, publisher = {Springer}, title = {Shortest Two Disjoint Paths in Polynomial Time}, url = {http://dx.doi.org/10.1007/9783662439487_18}, doi = {10.1007/9783662439487_18}, volume = {8572}, year = {2014}, }