Additive approximation algorithm for geodesic centers in δ-hyperbolic graphs

For an integer k≥ 1, the objective of {k-Geodesic Center} is to find a set C of k isometric paths such that the maximum distance between any vertex v and C is minimised. Introduced by Gromov, δ-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 {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 {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≥ 1, k-{Geodesic Center} is NP-hard even on partial grids.