Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
and
organization
publishing date
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
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
2016-04-01 10:31:45
date last changed
2024-01-06 18:59:47
@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}},
  doi          = {{10.1007/978-3-662-43948-7_18}},
  volume       = {{8572}},
  year         = {{2014}},
}