A parallel algorithm for the odd two-face shortest k k -disjoint path problem

Srijan Chakraborty, Samir Datta · 2025

Read A parallel algorithm for the odd two-face shortest k k -disjoint path problem by Srijan Chakraborty, Samir Datta (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-16336.txt.

Introduction

Srijan Chakraborty and Samir Datta give a parallel algorithm in two thousand twenty-five for a graph routing problem. The task is to find shortest paths between pairs of terminals that never share a vertex, minimizing total length. They restrict it to planar graphs whose terminals sit on two faces, each holding an odd number of terminals.

Their randomized algorithm solves this odd two-face case in polynomial time and even in parallel. The authors call it the first such solution for the problem. The method merges ideas from earlier two-pair and one-face algorithms. Its proof turns a system of equations into triangular form using two involutions, read as a directed acyclic graph. They also give a parallel algorithm for a related variant.

Catalog record

CREATORSrijan Chakraborty, Samir Datta
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-16336

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A parallel algorithm for the odd two-face shortest k k -disjoint path problem Srijan Chakraborty, Samir Datta Abstract The shortest Disjoint Path problem ( 𝖲𝖣𝖯𝖯 {\mathsf{SDPP}} ) requires us to find pairwise vertex disjoint paths between k k designated pairs of terminal vertices such that the sum of the path lengths is minimum. The focus here is on 𝖲𝖣𝖯𝖯 {\mathsf{SDPP}} restricted to planar graphs where all terminals are arbitrarily partitioned over two distinct faces with the additional restriction that each face is required to contain an odd number of terminals. We call this problem the Odd two-face planar 𝖲𝖣𝖯𝖯 {\mathsf{SDPP}} . It is shown that this problem is solvable in randomized polynomial time and even in 𝖱𝖭𝖢 {\mathsf{RNC}} . This is the first parallel (or even polynomial time) solution for the problem. Our algorithm combines ideas from the randomized solution for 2 2 - 𝖲𝖣𝖯𝖯 {\mathsf{SDPP}} by Björklund and Huslfeldt with its parallelization by Datta and Jaiswal along with the deterministic algorithm for One-face planar 𝖲𝖣𝖯𝖯 {\mathsf{SDPP}} by Datta, Iyer, Kulkarni and Mukherjee. The proof uses a combination of two involutions to reduce a system of linear equations modulo a power of 2 2 to a system of triangular form that is, therefore, invertible. This, in turn, is proved by showing that the matrix of the equations, can be interpreted as (the adjacency matrix of) a directed acyclic graph (DAG). While our algorithm is primarily algebraic the proof remains combinatorial. We also give a parallel algorithm for the ( A + B ) (A+B) - 𝖲𝖣𝖯𝖯 {\mathsf{SDPP}} introduced by Hirai and Namba. \declaretheorem [name=Theorem,numberwithin=section]thm Chennai Mathematical [email protected] Chennai Mathematical [email protected] I want to thank … ccs Theory of computation Parallel algorithms keywords disjoint paths, planar graph, parallel algorithm, cycle cover, permanent, involution † † runningauthor: S. Chakraborty and S. Datta † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Let G be a graph and \vec{S}=(s_{1},\ldots,s_{k}),\vec{T}=(t_{1},\ldots,t_{k}) be two sequences of vertices, all distinct, the Disjoint Path Problem ( {\mathsf{DPP}} ) is to determine if there are pairwise vertex disjoint paths 1 1 1 For us {\mathsf{DPP}} is synonymous with vertex disjoint paths and we will not have occasion to delve into the extant, large literature on edge disjoint paths. Also notice that {\mathsf{DPP}} is more specific than finding disjoint paths between two sets of vertices S,T . Our problem is distinct from disjoint shortest paths which has a polynomial time algorithm [ 20 ] . between the terminals s_{i},t_{i} for each i\in\{1,\ldots,k\} . Motivation {\mathsf{DPP}} and its variants have played an important role in theoretical computer science with applications ranging from network routing [ 23 , 28 ] , VLSI design [ 1 ] to the celebrated Graph Minor project of Robertson and Seymour [ 26 ] . It was also one of the problems that figured in Karp’s classic paper [ 16 ] on {\mathsf{NP}} -completeness. The planar restrictions of {\mathsf{DPP}} remain of current interest to the parameterized community [ 21 , 32 , 6 ] . {\mathsf{DPP}} can also be cast as an optimization problem and approximation algorithms for it form an active area of research [ 7 , 8 ] . Related Work {\mathsf{DPP}} is {\mathsf{NP}} -complete for both undirected and directed graphs [ 16 , 30 ] . Somewhat more restrictive is the k - {\mathsf{DPP}} where the terminal sequences are of length precisely k . The directed problem remains {\mathsf{NP}} -complete even for k=2 , [ 13 ] . For undirected graphs, Robertson and Seymour [ 26 ] proved that the problem is in cubic time with a galactic dependence on k . More recently, Kawarabayashi et al [ 17 ] have reduced the time to quadratic from cubic. Meanwhile, for certain subclasses of directed graphs viz. planar directed graphs, polynomial time algorithms (with exponents depending on k ) are known [ 27 ] for k - {\mathsf{DPP}} . Based on these parameterized algorithms have been developed for various variants of planar problems [ 24 , 21 ] . We will be concerned with the problem of determining if there is a k - {\mathsf{DPP}} solution with sum of weights at most a given value. In other words we will be interested in solving the shortest k - {\mathsf{DPP}} or {\mathsf{SDPP}} . For k>2 it is not known if the problem tractable in (randomized) polynomial time or not. For k=2 , Björklund and Husfeldt [ 3 ] give a randomized polynomial time algorithm for the problem based on computing a univariate polynomial permanent modulo 4 . Notice that permanent modulo 2 is identical to determinant modulo 2 since the only difference between determinant and permanent is the sign and {{-1\equiv 1}}\bmod{2} . This can be lifted to yield the value of the permanent of a univariate polynomial matrix modulo 4 in polynomial time. Using the isolation lemma [ 22 ] it was shown in [ 3 ] that finding the least degree monomial in the linear combination of three permanents modulo 4 yields a method to infer the weight of 2 - {\mathsf{SDPP}} . The above technique was based on a thread originating from Valiant [ 29 ] who showed that the permanent of an integer matrix modulo 4 can be computed in polytime which was refined to {\mathsf{\oplus L}}\subseteq{\mathsf{NC}}^{2} in [ 5 ] . This technique was extended to univariate polynomials in [ 10 ] to yield the first (randomized) parallel algorithm for univariate permanent modulo 2^{t} for a constant t . Combined with [ 3 ] this yielded the first (randomized) parallel algorithm for 2 - {\mathsf{SDPP}} . In a different thread, [ 9 ] showed that k - {\mathsf{SDPP}} in planar graphs where all terminals lie on a single face can be reduced to the sum of 4^{k} univariate determinants. The basic idea was to add “demand” edges inside the one face containing terminals and compute a generating function for cycle covers where each cycle cover is in correspondence with some k disjoint paths (though not always in the desired pairing). This leads to 4^{k} linear equations with the right hand side being the sum of cycle covers compatible with the applied demand edges which can therefore can be evaluated as a determinant. The left hand side consisted of the sum of various types of k disjoint paths. It was noticed in [ 9 ] that the left hand side gave rise to a square matrix that is upper triangular and so can be inverted to supply the generating function of the k disjoint paths of various types. This was generalised to one-face k - {\mathsf{SDPP}} with one extra arbitrarily placed terminal, by Kobayashi and Terao [ 19 ] . They generalised the technique from Hirai and Namba [ 14 ] who gave an alternate proof of Björklund and Husfeldt [ 3 ] based on computing Hafnian modulo 4 . The algorithms from [

Read the complete text