Near-Optimal Directed Low-Diameter Decompositions
Loading...
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 334
Abstract
Low Diameter Decompositions (LDDs) are invaluable tools in the design of combinatorial graph algorithms. While historically they have been applied mainly to undirected graphs, in the recent breakthrough for the negative-length Single Source Shortest Path problem, Bernstein, Nanongkai, and Wulff-Nilsen [FOCS’22] extended the use of LDDs to directed graphs for the first time. Specifically, their LDD deletes each edge with probability at most O(1/D · log2 n), while ensuring that each strongly connected component in the remaining graph has a (weak) diameter of at most D. In this work, we make further advancements in the study of directed LDDs. We reveal a natural and intuitive (in hindsight) connection to Expander Decompositions, and leveraging this connection along with additional techniques, we establish the existence of an LDD with an edge-cutting probability of O(1/D · log n log log n). This improves the previous bound by nearly a logarithmic factor and closely approaches the lower bound of Ω(1/D · log n). With significantly more technical effort, we also develop two efficient algorithms for computing our LDDs: a deterministic algorithm that runs in time Õ(m poly(D)) and a randomized algorithm that runs in near-linear time Õ(m). We believe that our work provides a solid conceptual and technical foundation for future research relying on directed LDDs, which will undoubtedly follow soon.Description
Publisher Copyright: © Karl Bringmann, Nick Fischer, Bernhard Haeupler, and Rustam Latypov.
Other note
Citation
Bringmann, K, Fischer, N, Haeupler, B & Latypov, R 2025, Near-Optimal Directed Low-Diameter Decompositions. in K Censor-Hillel, F Grandoni, J Ouaknine & G Puppis (eds), 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025., 35, Leibniz International Proceedings in Informatics, LIPIcs, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 08/07/2025. https://doi.org/10.4230/LIPIcs.ICALP.2025.35