Shortest Two Disjoint Paths in Polynomial Time
(2014) Automata, Languages, and Programming : 41st International Colloquium, ICALP 2014 8572. p.211-222- 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 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}$.
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
- 2014-07-08 - 2014-08-11
- external identifiers
-
- wos:000352643300020
- scopus:84904214727
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 978-3-662-43947-0
- DOI
- 10.1007/978-3-662-43948-7_18
- project
- Exact algorithms
- language
- English
- LU publication?
- yes
- id
- 988ffff4-5e2d-489b-a1ff-6e3883a9a421 (old id 5152872)
- date added to LUP
- 2016-04-01 10:31:45
- date last changed
- 2024-06-30 20:21:01
@inproceedings{988ffff4-5e2d-489b-a1ff-6e3883a9a421, 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 edge-disjoint 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 = {{978-3-662-43947-0}}, issn = {{1611-3349}}, language = {{eng}}, pages = {{211--222}}, publisher = {{Springer}}, title = {{Shortest Two Disjoint Paths in Polynomial Time}}, url = {{http://dx.doi.org/10.1007/978-3-662-43948-7_18}}, doi = {{10.1007/978-3-662-43948-7_18}}, volume = {{8572}}, year = {{2014}}, }