Simpler and Faster Directed Low-Diameter Decompositions

Abstract

We present a simpler and faster algorithm for low-diameter decompositions on directed graphs, matching the $O(\log n\log \log n)$ loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICALP 2025) and improving the running time to $O((m+n\log \log n){\log }^{2}n)$.

10 pages. Fix error in Algorithm 2: it needs to cut both out-balls and in-balls. (This was the initial algorithm, which was then incorrectly simplified.)