Additive approximation algorithm for geodesic centers in $\delta$-hyperbolic graphs
<|reference_start|>Additive approximation algorithm for geodesic centers in $\delta$-hyperbolic graphs: 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{$\delta$-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(\delta)$-approximation algorithm for \textsc{$k$-Geodesic Center} on $\delta$-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 $\delta$-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.<|reference_end|>
@article{chakraborty2024additive,
    title={Additive approximation algorithm for geodesic centers in
  $\delta$-hyperbolic graphs},
    author={Dibyayan Chakraborty, Yann Vax`es},
    journal={arXiv preprint arXiv:2404.03812},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.03812},
    primaryClass={cs.DS cs.CC}
}