Greedy Algorithms for Shortcut Sets and Hopsets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908994699788288 |
|---|---|
| author | Bals, Ben Blikstad, Joakim Bodwin, Greg Dadush, Daniel Forster, Sebastian Nazari, Yasamin |
| author_facet | Bals, Ben Blikstad, Joakim Bodwin, Greg Dadush, Daniel Forster, Sebastian Nazari, Yasamin |
| contents | For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentially optimal tradeoffs between size and quality. The goal of this paper is to develop and analyze comparable greedy algorithms for nearby objects in graph metric augmentation. We show the following:
- A simple greedy algorithm for shortcut sets achieves the state-of-the-art size/hopbound tradeoff recently proved by Kogan and Parter (2022), up to $O(\log n)$ factors in the size. Moreover, with an additional preprocessing step, the greedy algorithm subpolynomially improves on the previous size bounds in some range of parameters.
- The same greedy algorithm was already known to be existentially optimal for the size/hopbound tradeoff for hopsets, by an analysis of Berman, Raskhodnikova, and Ruan (2010) introduced for transitive-closure spanners. We provide a completely different analysis showing that the algorithm is also existentially optimal (up to $O(\log n)$ factors) for the matching hopset problem, in which one has a budget of roughly $O(m)$ additional edges (for an $m$-edge input graph). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_20111 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Greedy Algorithms for Shortcut Sets and Hopsets Bals, Ben Blikstad, Joakim Bodwin, Greg Dadush, Daniel Forster, Sebastian Nazari, Yasamin Data Structures and Algorithms Discrete Mathematics For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentially optimal tradeoffs between size and quality. The goal of this paper is to develop and analyze comparable greedy algorithms for nearby objects in graph metric augmentation. We show the following: - A simple greedy algorithm for shortcut sets achieves the state-of-the-art size/hopbound tradeoff recently proved by Kogan and Parter (2022), up to $O(\log n)$ factors in the size. Moreover, with an additional preprocessing step, the greedy algorithm subpolynomially improves on the previous size bounds in some range of parameters. - The same greedy algorithm was already known to be existentially optimal for the size/hopbound tradeoff for hopsets, by an analysis of Berman, Raskhodnikova, and Ruan (2010) introduced for transitive-closure spanners. We provide a completely different analysis showing that the algorithm is also existentially optimal (up to $O(\log n)$ factors) for the matching hopset problem, in which one has a budget of roughly $O(m)$ additional edges (for an $m$-edge input graph). |
| title | Greedy Algorithms for Shortcut Sets and Hopsets |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2511.20111 |