2026-07-23T00:17:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20147 2024-07-02T07:52:48Z ddc:004 open_access

Graphs Shortcuts: New Bounds and Algorithms (Invited Talk) Parter, Merav Shortcuts Spanners Distance Preservers For an n-vertex digraph G = (V,E), a shortcut set is a (small) subset of edges H taken from the transitive closure of G that, when added to G guarantees that the diameter of G ∪ H is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every n-vertex digraph admits a shortcut set of linear size (i.e., of O(n) edges) that reduces the diameter to Õ(√n). Despite extensive research over the years, the question of whether one can reduce the diameter to o(√n) with Õ(n) shortcut edges has been left open. In this talk, I will present the first improved diameter-sparsity tradeoff for this problem, breaking the √n diameter barrier. Specifically, we show an O(n^ω)-time randomized algorithm for computing a linear shortcut set that reduces the diameter of the digraph to Õ(n^{1/3}). I also present time efficient algorithms for computing these shortcuts and explain the limitations of the current approaches. Finally, I will draw some connections between shortcuts and several forms of graph sparsification (e.g., reachability preservers, spanners). Based on a joint work with Shimon Kogan (SODA 2022, ICALP 2022, FOCS 2022, SODA 2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Merav Parter 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.4 urn:nbn:de:0030-drops-201476 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.4 eng https://creativecommons.org/licenses/by/4.0/legalcode