Deterministic Padded Decompositions and Negative-Weight Shortest Paths
arXiv:2511.07859
Abstract
We obtain the first near-linear time deterministic algorithm for negative-weight single-source shortest paths on integer-weighted graphs. Our main ingredient is a deterministic construction of a padded decomposition on directed graphs, which may be of independent interest.
STOC 2026, 12 pages