License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.19
URN: urn:nbn:de:0030-drops-99183
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9918/
Datta, Samir ;
Iyer, Siddharth ;
Kulkarni, Raghav ;
Mukherjee, Anish
Shortest k-Disjoint Paths via Determinants
Abstract
The well-known k-disjoint path problem (k-DPP) asks for pairwise vertex-disjoint paths between k specified pairs of vertices (s_i, t_i) in a given graph, if they exist. The decision version of the shortest k-DPP asks for the length of the shortest (in terms of total length) such paths. Similarly, the search and counting versions ask for one such and the number of such shortest set of paths, respectively.
We restrict attention to the shortest k-DPP instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms for the search versions of the problem answering one of the main open questions raised by Colin de Verdière and Schrijver [Éric Colin de Verdière and Alexander Schrijver, 2011] for the general one-face problem. We do so by providing a randomised NC^2 algorithm along with an O(n^{omega/2}) time randomised sequential algorithm, for any fixed k. We also obtain deterministic algorithms with similar resource bounds for the counting and search versions. In contrast, previously, only the sequential complexity of decision and search versions of the "well-ordered" case has been studied. For the one-face case, sequential versions of our routines have better running times for constantly many terminals.
The algorithms are based on a bijection between a shortest k-tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusion-exclusion to produce a polynomial sum of determinants such that all "bad" cycle covers cancel out in the sum allowing us to count "pure" cycle covers.
BibTeX - Entry
@InProceedings{datta_et_al:LIPIcs:2018:9918,
author = {Samir Datta and Siddharth Iyer and Raghav Kulkarni and Anish Mukherjee},
title = {{Shortest k-Disjoint Paths via Determinants}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {19:1--19:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-093-4},
ISSN = {1868-8969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9918},
URN = {urn:nbn:de:0030-drops-99183},
doi = {10.4230/LIPIcs.FSTTCS.2018.19},
annote = {Keywords: disjoint paths, planar graph, parallel algorithm, cycle cover, determinant, inclusion-exclusion}
}
|
Keywords: |
|
disjoint paths, planar graph, parallel algorithm, cycle cover, determinant, inclusion-exclusion |
|
Collection: |
|
38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
05.12.2018 |
