Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910483240452096 |
|---|---|
| author | Chakraborty, Dibyayan Vaxès, Yann |
| author_facet | Chakraborty, Dibyayan Vaxès, Yann |
| contents | For an integer $k\geq 1$, the objective of \textsc{$k$-Geodesic Center} is to find a set $\mathcal{C}$ of $k$ isometric paths such that the maximum distance between any vertex $v$ and $\mathcal{C}$ is minimised. Introduced by Gromov, \emph{$δ$-hyperbolicity} measures how treelike a graph is from a metric point of view. Our main contribution in this paper is to provide an additive $O(δ)$-approximation algorithm for \textsc{$k$-Geodesic Center} on $δ$-hyperbolic graphs. On the way, we define a coarse version of the pairing property introduced by Gerstel \& Zaks (Networks, 1994) and show it holds for $δ$-hyperbolic graphs. This result allows to reduce the \textsc{$k$-Geodesic Center} problem to its rooted counterpart, a main idea behind our algorithm. We also adapt a technique of Dragan \& Leitert, (TCS, 2017) to show that for every $k\geq 1$, $k$-\textsc{Geodesic Center} is NP-hard even on partial grids. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03812 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs Chakraborty, Dibyayan Vaxès, Yann Data Structures and Algorithms Computational Complexity For an integer $k\geq 1$, the objective of \textsc{$k$-Geodesic Center} is to find a set $\mathcal{C}$ of $k$ isometric paths such that the maximum distance between any vertex $v$ and $\mathcal{C}$ is minimised. Introduced by Gromov, \emph{$δ$-hyperbolicity} measures how treelike a graph is from a metric point of view. Our main contribution in this paper is to provide an additive $O(δ)$-approximation algorithm for \textsc{$k$-Geodesic Center} on $δ$-hyperbolic graphs. On the way, we define a coarse version of the pairing property introduced by Gerstel \& Zaks (Networks, 1994) and show it holds for $δ$-hyperbolic graphs. This result allows to reduce the \textsc{$k$-Geodesic Center} problem to its rooted counterpart, a main idea behind our algorithm. We also adapt a technique of Dragan \& Leitert, (TCS, 2017) to show that for every $k\geq 1$, $k$-\textsc{Geodesic Center} is NP-hard even on partial grids. |
| title | Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2404.03812 |