Advanced

Shortest Two Disjoint Paths in Polynomial Time

Björklund, Andreas LU and Husfeldt, Thore LU (2014) Automata, Languages, and Programming : 41st International Colloquium, ICALP 2014 In Lecture Notes in Computer Science 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Lecture Notes in Computer Science
editor
Javier, Esparza; Pierre, Fraigniaud; Thore, Husfeldt; Elias, Koutsoupias; ; ; and
volume
8572
pages
12 pages
publisher
Springer
conference name
Automata, Languages, and Programming : 41st International Colloquium, ICALP 2014
external identifiers
  • wos:000352643300020
  • scopus:84904214727
ISSN
0302-9743
1611-3349
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
2015-03-10 10:39:16
date last changed
2017-10-22 03:17:24
@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         = {0302-9743},
  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},
  volume       = {8572},
  year         = {2014},
}