A Cut-Matching Game for Constant-Hop Expanders
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909366943219712 |
|---|---|
| author | Haeupler, Bernhard Huebotter, Jonas Ghaffari, Mohsen |
| author_facet | Haeupler, Bernhard Huebotter, Jonas Ghaffari, Mohsen |
| contents | This paper extends and generalizes the well-known cut-matching game framework and provides a novel cut-strategy that produces constant-hop expanders.
Constant-hop expanders are a significant strengthening of regular expanders with the additional guarantee that any demand can be (obliviously) routed along constant-hop flow-paths - in contrast to the $Ω(\log n)$-hop paths in expanders.
Cut-matching games for expanders are key tools for obtaining linear-time approximation algorithms for many hard problems, including finding (balanced or approximately-largest) sparse cuts, certifying the expansion of a graph by embedding an (explicit) expander, as well as computing expander decompositions, hierarchical cut decompositions, oblivious routings, multi-cuts, and multi-commodity flows.
The cut-matching game of this paper is crucial in extending this versatile and powerful machinery to constant-hop and length-constrained expanders and has been already been extensively used. For example, as a key ingredient in several recent breakthroughs, including, computing constant-approximate $k$-commodity (min-cost) flows in $(m+k)^{1+ε}$ time as well as the optimal constant-approximate deterministic worst-case fully-dynamic APSP-distance oracle - in all applications the constant-approximation factor directly traces to and crucially relies on the expanders from a cut-matching game guaranteeing constant-hop routing paths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_11726 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Cut-Matching Game for Constant-Hop Expanders Haeupler, Bernhard Huebotter, Jonas Ghaffari, Mohsen Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Combinatorics This paper extends and generalizes the well-known cut-matching game framework and provides a novel cut-strategy that produces constant-hop expanders. Constant-hop expanders are a significant strengthening of regular expanders with the additional guarantee that any demand can be (obliviously) routed along constant-hop flow-paths - in contrast to the $Ω(\log n)$-hop paths in expanders. Cut-matching games for expanders are key tools for obtaining linear-time approximation algorithms for many hard problems, including finding (balanced or approximately-largest) sparse cuts, certifying the expansion of a graph by embedding an (explicit) expander, as well as computing expander decompositions, hierarchical cut decompositions, oblivious routings, multi-cuts, and multi-commodity flows. The cut-matching game of this paper is crucial in extending this versatile and powerful machinery to constant-hop and length-constrained expanders and has been already been extensively used. For example, as a key ingredient in several recent breakthroughs, including, computing constant-approximate $k$-commodity (min-cost) flows in $(m+k)^{1+ε}$ time as well as the optimal constant-approximate deterministic worst-case fully-dynamic APSP-distance oracle - in all applications the constant-approximation factor directly traces to and crucially relies on the expanders from a cut-matching game guaranteeing constant-hop routing paths. |
| title | A Cut-Matching Game for Constant-Hop Expanders |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Combinatorics |
| url | https://arxiv.org/abs/2211.11726 |