Theory Seminar, Wednesday Dec 4: Merav Parter (Weizmann) - Graphs Shortcuts: New Bounds and Algorithms
4 views
Skip to first unread message
Arnold Filtser
Nov 27, 2024, 12:55:39 PM11/27/24
to BIU Theory Seminar, Merav Parter
Hi all,
Speaker: Merav Parter (Weizmann)
Title: Graphs Shortcuts: New Bounds and Algorithms
Abstract: 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⅓). 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).
Next week (Wed Dec 4, at 12) we will meet for our theory seminar.
Location: Building 503 room 226.
See you all there,
Title: Graphs Shortcuts: New Bounds and Algorithms
Abstract: 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⅓). 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).
Reply all
Reply to author
Forward
0 new messages