Abstract
The wellknown kdisjoint path problem (kDPP) asks for pairwise vertexdisjoint paths between k specified pairs of vertices (s_i, t_i) in a given graph, if they exist. The decision version of the shortest kDPP 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 kDPP 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 oneface 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 "wellordered" case has been studied. For the oneface case, sequential versions of our routines have better running times for constantly many terminals.
The algorithms are based on a bijection between a shortest ktuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to nontrivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusionexclusion 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 kDisjoint Paths via Determinants}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {19:119:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770934},
ISSN = {18688969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9918},
URN = {urn:nbn:de:0030drops99183},
doi = {10.4230/LIPIcs.FSTTCS.2018.19},
annote = {Keywords: disjoint paths, planar graph, parallel algorithm, cycle cover, determinant, inclusionexclusion}
}
Keywords: 

disjoint paths, planar graph, parallel algorithm, cycle cover, determinant, inclusionexclusion 
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 