Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
For researchers in graph algorithms, this work transfers key properties of undirected low-diameter decompositions to directed graphs, enabling new applications in distributed computing and approximation algorithms.
This paper strengthens directed low-diameter decompositions by providing the first results for separated decompositions, tightening probabilistic guarantees, and achieving meaningful guarantees for sub-logarithmic diameters D = Ω(log log n), whereas prior work required D = ω(log n). All results are algorithmic with near-linear time Õ(m).
This paper significantly strengthens directed low-diameter decompositions in several ways. We define and give the first results for separated low-diameter decompositions in directed graphs, tighten and generalize probabilistic guarantees, and prove new independence results between (far away) edges. Our results are the first to give meaningful guarantees for decompositions with small diameters $D = Ω(\log\log n)$ in contrast to the state of the art that only applies to super-logarithmic diameters $D = ω(\log n)$. These results transfer several important and widely used aspects of undirected low-diameter decompositions to the directed setting. All our results are algorithmic -- small modifications to two existing directed low-diameter decompositions [BFHL25; Li25] can be used to sample decompositions with our new guarantees in near-linear time $\tilde{O}(m)$.