Shortest Two Disjoint Paths in Polynomial Time

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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}$.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikationLecture Notes in Computer Science
RedaktörerEsparza Javier, Fraigniaud Pierre, Husfeldt Thore, Koutsoupias Elias
FörlagSpringer
Sidor211-222
Antal sidor12
Volym8572
ISBN (tryckt)978-3-662-43947-0
StatusPublished - 2014
PublikationskategoriForskning
Peer review utfördJa
EvenemangAutomata, Languages, and Programming : 41st International Colloquium, ICALP 2014 - Copenhagen, Danmark
Varaktighet: 2014 jul 82014 aug 11

Publikationsserier

Namn
Volym8572
ISSN (tryckt)1611-3349
ISSN (elektroniskt)0302-9743

Konferens

KonferensAutomata, Languages, and Programming : 41st International Colloquium, ICALP 2014
LandDanmark
OrtCopenhagen
Period2014/07/082014/08/11