Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm
(2018) 29th International Symposium on Algorithms and Computation, ISAAC 2018p.119
 Abstract
 Given an undirected graph and two disjoint vertex pairs s_1,t_1 and s_2,t_2, the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disjoint paths connecting s_1 with t_1, and s_2 with t_2, respectively. We show that for cubic planar graphs there are NC algorithms, uniform circuits of polynomial size and polylogarithmic depth, that compute the S2DP and moreover also output the number of such minimum length path pairs. Previously, to the best of our knowledge, no deterministic polynomial time algorithm was known for S2DP in cubic planar graphs with arbitrary placement of the terminals. In contrast, the randomized polynomial time algorithm by Björklund and Husfeldt, ICALP 2014, for general graphs is... (More)
 Given an undirected graph and two disjoint vertex pairs s_1,t_1 and s_2,t_2, the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disjoint paths connecting s_1 with t_1, and s_2 with t_2, respectively. We show that for cubic planar graphs there are NC algorithms, uniform circuits of polynomial size and polylogarithmic depth, that compute the S2DP and moreover also output the number of such minimum length path pairs. Previously, to the best of our knowledge, no deterministic polynomial time algorithm was known for S2DP in cubic planar graphs with arbitrary placement of the terminals. In contrast, the randomized polynomial time algorithm by Björklund and Husfeldt, ICALP 2014, for general graphs is much slower, is serial in nature, and cannot count the solutions. Our results are built on an approach by Hirai and Namba, Algorithmica 2017, for a generalisation of S2DP, and fast algorithms for counting perfect matchings in planar graphs.
(Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/984ab423a2214433b566c8a53a458faa
 author
 Björklund, Andreas ^{LU} and Husfeldt, Thore ^{LU}
 organization
 publishing date
 2018
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 Shortest disjoint paths, Cubic planar graph
 host publication
 29th International Symposium on Algorithms and Computation (ISAAC 2018)
 pages
 1  19
 publisher
 Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing
 conference name
 29th International Symposium on Algorithms and Computation, ISAAC 2018<br/><br/>
 conference location
 Jiaoxi, Yilan, Taiwan, Province of China
 conference dates
 20181216  20181219
 external identifiers

 scopus:85063688304
 ISBN
 9783959770941
 DOI
 10.4230/LIPIcs.ISAAC.2018.19
 language
 English
 LU publication?
 yes
 id
 984ab423a2214433b566c8a53a458faa
 date added to LUP
 20190201 08:37:10
 date last changed
 20190414 04:08:31
@inproceedings{984ab423a2214433b566c8a53a458faa, abstract = {Given an undirected graph and two disjoint vertex pairs s_1,t_1 and s_2,t_2, the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disjoint paths connecting s_1 with t_1, and s_2 with t_2, respectively. We show that for cubic planar graphs there are NC algorithms, uniform circuits of polynomial size and polylogarithmic depth, that compute the S2DP and moreover also output the number of such minimum length path pairs. Previously, to the best of our knowledge, no deterministic polynomial time algorithm was known for S2DP in cubic planar graphs with arbitrary placement of the terminals. In contrast, the randomized polynomial time algorithm by Björklund and Husfeldt, ICALP 2014, for general graphs is much slower, is serial in nature, and cannot count the solutions. Our results are built on an approach by Hirai and Namba, Algorithmica 2017, for a generalisation of S2DP, and fast algorithms for counting perfect matchings in planar graphs.<br/>}, author = {Björklund, Andreas and Husfeldt, Thore}, isbn = {9783959770941}, keyword = {Shortest disjoint paths,Cubic planar graph}, language = {eng}, location = {Jiaoxi, Yilan, Taiwan, Province of China}, pages = {119}, publisher = {Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing}, title = {Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm}, url = {http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.19}, year = {2018}, }