Shortest Two Disjoint Paths in Polynomial Time
Author
Editor
- Esparza Javier
- Fraigniaud Pierre
- Husfeldt Thore
- Koutsoupias Elias
Summary, in English
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}$.
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}$.
Department/s
Publishing year
2014
Language
English
Pages
211-222
Publication/Series
Lecture Notes in Computer Science
Volume
8572
Document type
Conference paper
Publisher
Springer
Topic
- Computer Science
Conference name
Automata, Languages, and Programming : 41st International Colloquium, ICALP 2014
Conference date
2014-07-08 - 2014-08-11
Conference place
Copenhagen, Denmark
Status
Published
Project
- Exact algorithms
Research group
- Algorithms
ISBN/ISSN/Other
- ISSN: 0302-9743
- ISSN: 1611-3349
- ISBN: 978-3-662-43947-0