Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm

Björklund, Andreas LU and Husfeldt, Thore LU (2018) 29th International Symposium on Algorithms and Computation, ISAAC 2018

 p.1-19
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:
author
and
organization
publishing date
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 - Leibniz-Zentrum für Informatik
conference name
29th International Symposium on Algorithms and Computation, ISAAC 2018<br/><br/>
conference location
Jiaoxi, Yilan, Taiwan
conference dates
2018-12-16 - 2018-12-19
external identifiers
  • scopus:85063688304
ISBN
978-3-95977-094-1
DOI
10.4230/LIPIcs.ISAAC.2018.19
language
English
LU publication?
yes
id
984ab423-a221-4433-b566-c8a53a458faa
date added to LUP
2019-02-01 08:37:10
date last changed
2022-03-17 21:09:53
@inproceedings{984ab423-a221-4433-b566-c8a53a458faa,
  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}},
  booktitle    = {{29th International Symposium on Algorithms and Computation  (ISAAC 2018)}},
  isbn         = {{978-3-95977-094-1}},
  keywords     = {{Shortest disjoint paths; Cubic planar graph}},
  language     = {{eng}},
  pages        = {{1--19}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  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}},
  doi          = {{10.4230/LIPIcs.ISAAC.2018.19}},
  year         = {{2018}},
}