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

Andreas Björklund, Thore Husfeldt

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

Abstract

Given an undirected graph and two disjoint vertex pairs s1 , t1 and s2 , t2 , the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disjoint paths connecting s1 with t1, and s2 with t2, 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 general- isation of S2DP, and fast algorithms for counting perfect matchings in planar graphs.
Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation (ISAAC 2018)
Number of pages13
Volume123
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Publication date2018
Pages19:1-19:13
ISBN (Electronic)ISBN 978-3-95977-094-1
DOIs
Publication statusPublished - 2018
SeriesLeibniz International Proceedings in Informatics
ISSN1868-8969

Keywords

  • Shortest two disjoint paths
  • Cubic planar graphs
  • NC algorithms
  • Deterministic polynomial time
  • Perfect matchings in planar graphs

Fingerprint

Dive into the research topics of 'Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm'. Together they form a unique fingerprint.

Cite this