@online{Bringmann_2502.05687,
TITLE = {Near-Optimal Directed Low-Diameter Decompositions},
AUTHOR = {Bringmann, Karl and Fischer, Nick and Haeupler, Bernhard and Latypov, Rustam},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2502.05687},
EPRINT = {2502.05687},
EPRINTTYPE = {arXiv},
YEAR = {2025},
MARGINALMARK = {$\bullet$},
ABSTRACT = {Low Diameter Decompositions (LDDs) are invaluable tools in the design of<br>combinatorial graph algorithms. While historically they have been applied<br>mainly to undirected graphs, in the recent breakthrough for the negative-length<br>Single Source Shortest Path problem, Bernstein, Nanongkai, and Wulff-Nilsen<br>[FOCS '22] extended the use of LDDs to directed graphs for the first time.<br>Specifically, their LDD deletes each edge with probability at most<br>$O(\frac{1}{D} \cdot \log^2 n)$, while ensuring that each strongly connected<br>component in the remaining graph has a (weak) diameter of at most $D$.<br> In this work, we make further advancements in the study of directed LDDs. We<br>reveal a natural and intuitive (in hindsight) connection to Expander<br>Decompositions, and leveraging this connection along with additional<br>techniques, we establish the existence of an LDD with an edge-cutting<br>probability of $O(\frac{1}{D} \cdot \log n \log\log n)$. This improves the<br>previous bound by nearly a logarithmic factor and closely approaches the lower<br>bound of $\Omega(\frac{1}{D} \cdot \log n)$. With significantly more technical<br>effort, we also develop two efficient algorithms for computing our LDDs: a<br>deterministic algorithm that runs in time $\tilde O(m \cdot poly(D))$ and a<br>randomized algorithm that runs in near-linear time $\tilde O(m)$.<br> We believe that our work provides a solid conceptual and technical foundation<br>for future research relying on directed LDDs, which will undoubtedly follow<br>soon.<br>},
}