Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP

Adam Karczmarz, Wojciech Nadara, Marek Sokołowski · 2025

Read Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP by Adam Karczmarz, Wojciech Nadara, Marek Sokołowski (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-2510-19780.txt.

Introduction

Adam Karczmarz, Wojciech Nadara, and Marek Sokołowski improve the parallel cost of the single-source shortest path problem in directed graphs with non-negative weights. Shortest paths are a bedrock task. The open challenge is to do much less total work while finishing in far fewer parallel steps. Running times should be polynomial in the input size, not in the weight values. Their main result reaches near-linear work bounds with sublinear depth.

For dense graphs, this is the first nearly work-efficient strongly polynomial parallel algorithm with sublinear depth. Gains flow at once to min-cost flow and the assignment problem. The result also yields the first non-trivial strongly polynomial dynamic algorithm for minimum mean cycle. The team also handles variants with huge edge weights in the word RAM model.

Catalog record

CREATORAdam Karczmarz, Wojciech Nadara, Marek Sokołowski
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19780

Browse the full library · About the Tower of Babel

Full text

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

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP Adam Karczmarz, Wojciech Nadara, Marek Sokołowski Abstract In this paper, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly, we prove that directed SSSP can be solved within O ~ ​ ( m + n 2 − ϵ ) \widetilde{O}(m+n^{2-\epsilon}) work and O ~ ​ ( n 1 − ϵ ) \widetilde{O}(n^{1-\epsilon}) depth for some positive ϵ > 0 \epsilon>0 . In particular, for dense graphs with non-negative real weights, we provide the first nearly work-efficient strongly polynomial algorithm with sublinear depth. Our result immediately yields improved strongly polynomial parallel algorithms for min-cost flow and the assignment problem. It also leads to the first non-trivial strongly polynomial dynamic algorithm for minimum mean cycle. Moreover, we develop efficient parallel algorithms in the Word RAM model for several variants of SSSP in graphs with exponentially large edge weights. 1 Introduction Single-source shortest paths (SSSP) is one of the most fundamental and well-studied graph problems. The famous Dijkstra‘s algorithm [ Dij59 ] solves the problem on directed graphs {G=(V,E)} with n vertices, m edges, and non-negative real edge weights in {O(m+n\log{n})} time if an appropriate priority queue is used [ FT87 ] . Dijkstra‘s algorithm, in its classical form, finds an exact solution by operating on the input weights via additions and comparisons only. It is also strongly polynomial , i.e., its running time on real data is polynomial in n,m exclusively 1 1 1 And does not abuse the arithmetic model, e.g., runs in polynomial space for rational inputs on a Turing machine. . In particular, it does not depend on the input weights‘ magnitude, which is the case for weakly polynomial algorithms. Devising improved strongly polynomial shortest paths algorithms has historically proved very challenging. Only very recently, the decades-old state-of-the-art strongly polynomial SSSP bounds [ Bel58 , FT87 ] have witnessed first breakthroughs: for non-negative weights [ DMM+25 ] (in the sparse case), and for possibly-negative weights [ Fin24 ] . This is despite numerous previous improvements in the weakly polynomial regime (for integer data), e.g., [ BNW22 , vEBKZ77 , CKL+22 , CMSV17 , GT89 , Gol95 , Hag00 , Tho00 , Tho04 ] or in the undirected case [ DMSY23 ] . Parallel SSSP. In this paper, our focus is on strongly polynomial parallel SSSP algorithms for non-negatively weighted directed graphs (digraphs). The current de facto standard for studying the efficiency of parallel shared-memory (PRAM) algorithms is the work-depth model (e.g., [ JáJ92 , Ble96 ] ). The work of a parallel algorithm is its sequential running time, whereas the depth is the longest chain of sequential dependencies between the performed operations. In this paper, when quantifying work and depth, we always stick to the \widetilde{O}(\cdot) notation 2 2 2 \widetilde{O} suppresses \operatorname{polylog}(n) factors. That is, whenever we write \widetilde{O}(f(n)) , we mean O(f(n)\operatorname{polylog}{n}) . In particular, \widetilde{O}(1) captures O(\log^{2}{n}) and \widetilde{O}(n/t) captures O((n/t)\operatorname{polylog}{n}) for all parameters t\in[1,n] . as we are concerned about polynomial improvements anyway. 3 3 3 Moreover, this way, we do not need to specify the precise shared memory access model (e.g., EREW, CRCW) as polylogarithmic-overhead reductions between the variants are known [ JáJ92 ] . A parallel algorithm is called nearly work-efficient if its work matches, up to polylogarithmic factors, the best-known sequential bound for the studied problem. Dijkstra‘s algorithm can be parallelized to run in \widetilde{O}(m) work and \widetilde{O}(n) depth if one uses parallel priority queues [ PK85 , BTZ98 ] . It is also well-known that all-pairs shortest paths (APSP) – and thus also SSSP – can be computed within \widetilde{O}(n^{3}) work and \widetilde{O}(1) depth via repeated squaring-based exponentiation of the weighted adjacency matrix using the (\min,+) product. Identifying feasible work-depth pairs or tradeoffs for exact SSSP beyond these classical ones has been the subject of a large body of prior work [ BGST16 , BHK17 , CF23 , Coh97 , FN18 , GM88 , KS93 , KS97 , RHM+23 , SS99 , Spe97 , UY91 ] ; however, their majority studied weakly polynomial bounds, and mostly in integer-weighted graphs. Notably, [ RHM+23 ] showed a general \widetilde{O}(1) -overhead reduction to (1+\epsilon) -approximate SSSP for digraphs with polynomially-bounded non-negative integer weights, which enabled lifting known approximate SSSP bounds (e.g. [ CFR20a , CFR20b , Zwi02 ] ) to the exact setting. In particular, this implied a nearly work-efficient algorithm with n^{1/2+o(1)} depth, a result shown independently by [ CF23 ] . Spencer [ Spe97 ] showed an \widetilde{O}(m+nt^{2}) work and \widetilde{O}(n/t) depth trade-off (for any t\in[1,n] ) that does not require integrality, but merely \operatorname{poly}(n) -bounded weights. Table 1 lists the state-of-the-art bounds (wrt. \widetilde{O} ) for exact parallel SSSP under various restrictions. Strongly polynomial parallel SSSP. Parallel SSSP in the strongly polynomial regime appears much less understood. A simplified version of Spencer‘s SSSP tradeoff [ Spe97 ] (not described explicitly in the literature, to the best of our knowledge; see Section 3 ) yields \widetilde{O}(n^{2}t) work and \widetilde{O}(n/t) depth for any parameter t\in[1,n] . Note that this constitutes a natural interpolation between parallel Dijkstra and repeated-squaring for dense graphs. For sparse graphs, [ BHK17 ] show a better tradeoff with \widetilde{O}(mn+t^{3}) work and \widetilde{O}(n/t) depth that even works for negative weights. Strikingly, for directed SSSP with non-negative weights, none of the known strongly polynomial parallel algorithms for directed graphs with non-trivial, truly sublinear depth achieve subquadratic work. In particular, none attain sub-Bellman–Ford O(mn^{1-\epsilon}) work for all densities m\in[n,n^{2}] , and none are nearly-work efficient for any density, such as m\approx n^{2} . It is thus natural to ask: Is there a strongly polynomial SSSP algorithm for non-negatively weighted directed graphs with \widetilde{O}(m+n^{2-\epsilon}) work and \widetilde{O}(n^{1-\epsilon}) depth, for some \epsilon>0 ? Note that in the weakly polynomial regime, algorithms with such work/depth characteristics have been known for subexponential real weights [ Spe91 , Spe97 ] for more than 30 years. Interestingly, the posed question has also been known to have an affirmative answer for the special case of undirected graphs [ SS99 ] . Both Spencer [ Spe97 ] and Shi and Spencer [ SS99 ] noted that their methods fail to produce non-trivial bounds for directed graphs in the strongly polynomial regime. They explicitly asked for strongly polynomial parallel SSSP algorithms for digraphs with comparable bounds. It is worth noting that, in the strongly polynomial regime, directed SSSP computation (with non-negative weights) is the bottleneck of many state-of-the-art optimization algorithms, e.g., [ EK72 , HJQ25 , OV20 , Orl93 ] . Therefore, improving the parallel SSSP bounds can immediately lead to improved parallel algorithms for those. 1.1 Our results As our main result, we give an affirmative answer to the posed question and show the following deterministic strongly polynomial work-depth tradeoff for directed SSSP. Theorem 1.1 . Let G=(V,E) be a weighted digraph with weights in \mathbb{R}_{\geq 0} . Single-source shortest paths in G can be computed within \widetilde{O}(m+n^{9/5}t^{17/5}) work and \widetilde{O}(n/t) depth for any t\in[1,n^{1/17}] . For dense enough graphs with m=\Omega(n^{1+{4/5}+\epsilon}) , the algorithm behind Theorem 1.1 can run in near-optimal \widetilde{O}(m) work and truly sublinear in n depth. This is the first strongly polynomial result to improve

Read the complete text