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.
The idea of using fast perfect matching counting in restricted graph classes to solve other combinatorial optimisation problems is not new, a prominent example is the polynomial time algorithm for Maximum Cut in an unweighted graph of bounded genus by Galluccio, Loebl, and Vondr ' ak @cite_18 .
@cite_18
2013200539
We present a polynomial time algorithm to find the maximum weight of an edge-cut in graphs embeddable on an arbitrary orientable surface, with integral weights bounded in the absolute value by a polynomial of the size of the graph.<