Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP

2025/10/22 by Adam Karczmarz, Wojciech Nadara, Karczmarz, Adam +3
Computer Science · #Complexity and Algorithms in Graphs #Graph Theory and Algorithms #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2510.19780

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-ε) work and O(n^1-ε) depth for some positive ε>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.

Citations

• Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
• Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
• Faster single-source shortest paths with negative real weights via proper hop distance
• Deterministic Fully Dynamic SSSP and More
• A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
• Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
• Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
• Negative-Weight Single-Source Shortest Paths in Near-linear Time
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
• Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
• Faster Parallel Algorithm for Approximate Shortest Path
• Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
• A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
• Hopsets with Constant Hopbound, and Applications to Approximate Shortest\n Paths
• Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in O(m^10/7 log W) Time
• Parallel Shortest-Paths Using Radius Stepping
• Faster all-pairs shortest paths via circuit complexity
• Polynomial Value Iteration Algorithms for Detrerminstic MDPs
• All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
• A Note on Two Problems in Connexion with Graphs

Related

• Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths
• A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
• Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
• More Parallelism in Dijkstra's Single-Source Shortest Path Algorithm
• A Faster Directed Single-Source Shortest Path Algorithm