Approximation Algorithms for Optimal 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_ | 1866909602866528256 |
|---|---|
| author | Dinitz, Michael Koranteng, Ama Nazari, Yasamin |
| author_facet | Dinitz, Michael Koranteng, Ama Nazari, Yasamin |
| contents | For a given graph $G$, a "hopset" $H$ with hopbound $β$ and stretch $α$ is a set of edges such that between every pair of vertices $u$ and $v$, there is a path with at most $β$ hops in $G \cup H$ that approximates the distance between $u$ and $v$ up to a multiplicative stretch of $α$. Hopsets have found a wide range of applications for distance-based problems in various computational models since the 90s. More recently, there has been significant interest in understanding these fundamental objects from an existential and structural perspective. But all of this work takes a worst-case (or existential) point of view: How many edges do we need to add to satisfy a given hopbound and stretch requirement for any input graph?
We initiate the study of the natural optimization variant of this problem: given a specific graph instance, what is the minimum number of edges that satisfy the hopbound and stretch requirements? We give approximation algorithms for a generalized hopset problem which, when combined with known existential bounds, lead to different approximation guarantees for various regimes depending on hopbound, stretch, and directed vs. undirected inputs. We complement our upper bounds with a lower bound that implies Label Cover hardness for directed hopsets and shortcut sets with hopbound at least $3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06522 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithms for Optimal Hopsets Dinitz, Michael Koranteng, Ama Nazari, Yasamin Data Structures and Algorithms Discrete Mathematics For a given graph $G$, a "hopset" $H$ with hopbound $β$ and stretch $α$ is a set of edges such that between every pair of vertices $u$ and $v$, there is a path with at most $β$ hops in $G \cup H$ that approximates the distance between $u$ and $v$ up to a multiplicative stretch of $α$. Hopsets have found a wide range of applications for distance-based problems in various computational models since the 90s. More recently, there has been significant interest in understanding these fundamental objects from an existential and structural perspective. But all of this work takes a worst-case (or existential) point of view: How many edges do we need to add to satisfy a given hopbound and stretch requirement for any input graph? We initiate the study of the natural optimization variant of this problem: given a specific graph instance, what is the minimum number of edges that satisfy the hopbound and stretch requirements? We give approximation algorithms for a generalized hopset problem which, when combined with known existential bounds, lead to different approximation guarantees for various regimes depending on hopbound, stretch, and directed vs. undirected inputs. We complement our upper bounds with a lower bound that implies Label Cover hardness for directed hopsets and shortcut sets with hopbound at least $3$. |
| title | Approximation Algorithms for Optimal Hopsets |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2502.06522 |