A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909010531188736 |
|---|---|
| author | Ducoffe, Guillaume |
| author_facet | Ducoffe, Guillaume |
| contents | A vertex in a graph is called central if it minimizes its maximum distance to the other vertices. The radius of a graph $G$ is the largest distance between a central vertex and the other vertices, and it is denoted by $rad(G)$. In the center problem, we are asked to find a central vertex. We study the fine-grained complexity of the center problem on graphs with small Gromov hyperbolicity. Roughly, the Gromov hyperbolicity of a graph represents how close, locally, it is to a tree, from a metric point of view. It has applications in the design of approximation algorithms. In particular, there is a linear-time algorithm that for every $δ$-hyperbolic graph $G$ outputs some vertex at distance at most $rad(G) + 5δ$ to the other vertices [Chepoi et al, SoCG'08]. However, a linear-time algorithm for computing a central vertex is known only for $0$-hyperbolic graphs, whereas its existence was ruled out for $2$-hyperbolic graphs under the Hitting Set Conjecture of [Abboud et al, SODA'16]. Our main contribution in the paper is a linear-time algorithm for computing a central vertex in the class of $\frac 1 2$-hyperbolic graphs. Furthermore, we rule out the existence of such an algorithm for $1$-hyperbolic graphs, under the Hitting Set Conjecture, thus completely settling all the cases left open. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_01578 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs Ducoffe, Guillaume Data Structures and Algorithms Computational Complexity A vertex in a graph is called central if it minimizes its maximum distance to the other vertices. The radius of a graph $G$ is the largest distance between a central vertex and the other vertices, and it is denoted by $rad(G)$. In the center problem, we are asked to find a central vertex. We study the fine-grained complexity of the center problem on graphs with small Gromov hyperbolicity. Roughly, the Gromov hyperbolicity of a graph represents how close, locally, it is to a tree, from a metric point of view. It has applications in the design of approximation algorithms. In particular, there is a linear-time algorithm that for every $δ$-hyperbolic graph $G$ outputs some vertex at distance at most $rad(G) + 5δ$ to the other vertices [Chepoi et al, SoCG'08]. However, a linear-time algorithm for computing a central vertex is known only for $0$-hyperbolic graphs, whereas its existence was ruled out for $2$-hyperbolic graphs under the Hitting Set Conjecture of [Abboud et al, SODA'16]. Our main contribution in the paper is a linear-time algorithm for computing a central vertex in the class of $\frac 1 2$-hyperbolic graphs. Furthermore, we rule out the existence of such an algorithm for $1$-hyperbolic graphs, under the Hitting Set Conjecture, thus completely settling all the cases left open. |
| title | A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2605.01578 |