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 (2019) In SIAM Journal on Computing 48(6). p.1698-1710
Abstract

Given an undirected graph and two pairs of vertices (si, ti) for i ϵ{ 1, 2} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ϵ{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 ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying... (More)

Given an undirected graph and two pairs of vertices (si, ti) for i ϵ{ 1, 2} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ϵ{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 ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Zt

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Graph algorithms, Graph theory, Randomized algorithms
in
SIAM Journal on Computing
volume
48
issue
6
pages
13 pages
publisher
Society for Industrial and Applied Mathematics
external identifiers
  • scopus:85076882804
ISSN
0097-5397
DOI
10.1137/18M1223034
language
English
LU publication?
yes
id
b01033cf-bb81-4d6f-9572-78debb66907f
date added to LUP
2020-01-10 12:17:45
date last changed
2025-04-04 14:17:26
@article{b01033cf-bb81-4d6f-9572-78debb66907f,
  abstract     = {{<p>Given an undirected graph and two pairs of vertices (s<sub>i</sub>, t<sub>i</sub>) for i ϵ{ 1, 2} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining s<sub>i</sub> and t<sub>i</sub> for i ϵ{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 ring Z<sub>4</sub>[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Z<sub>t</sub>[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Z<sub>t</sub>                             </p>}},
  author       = {{Björklund, Andreas and Husfeldt, Thore}},
  issn         = {{0097-5397}},
  keywords     = {{Graph algorithms; Graph theory; Randomized algorithms}},
  language     = {{eng}},
  month        = {{11}},
  number       = {{6}},
  pages        = {{1698--1710}},
  publisher    = {{Society for Industrial and Applied Mathematics}},
  series       = {{SIAM Journal on Computing}},
  title        = {{Shortest two disjoint paths in polynomial time}},
  url          = {{http://dx.doi.org/10.1137/18M1223034}},
  doi          = {{10.1137/18M1223034}},
  volume       = {{48}},
  year         = {{2019}},
}