Given an undirected graph and two disjoint vertex pairs @math and @math , the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disjoint paths connecting @math with @math , and @math with @math , 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 "orklund 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.
Bj "orklund and Husfeldt @cite_5 showed that Shortest two disjoint paths in a general unweighted undirected graph has a polynomial time Monte Carlo algorithm. Colin de Verdi 'ere and Schrijver @cite_16 , and Kobayachi and Sommer @cite_9 showed that for planar graphs, deterministic polynomial-time algorithms for the Shortest two disjoint paths exist if the four terminals lie on the boundary of at most two faces. Our new algorithm works for all cubic planar cases, but is much slower. Still it is significantly faster than the general @math time algorithm by Bj "orklund and Husfeldt @cite_5 .
@cite_5 @cite_9 @cite_16
65356316 2004779317 2111716715
Given an undirected graph and two pairs of vertices (s i ,t i ) for i ∈ 1,2 we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining s i and t i for i ∈ 1,2 respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem. For a graph G and a collection of vertex pairs (s"1,t"1),...,(s"k,t"k) , the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P"i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3. Min-Sum: We extend recent results by Colin de Verdiere and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time. Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3. Let G be a directed planar graph of complexity n, each arc having a nonnegative length. Let s and t be two distinct faces of G let s1,…,sk be vertices incident with s let t1,…,tk be vertices incident with t. We give an algorithm to compute k pairwise vertex-disjoint paths connecting the pairs (si,ti) in G, with minimal total length, in O(knlog n) time.