School of Computing, University of Leeds, United Kingdom. Laboratoire
d’Informatique et Systèmes, Aix-Marseille Université and CNRS, Faculté des
Sciences de Luminy, F-13288 Marseille, Cedex 9, France. [500]Theory of
computation Graph algorithms analysis Theory of computation Approximation
algorithms

#  Additive approximation algorithm for geodesic centers in
$\delta$-hyperbolic graphs

Dibyayan Chakraborty  Yann Vaxès

###### Abstract

For an integer $k\geq 1$, the objective of $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,
_$\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 $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
$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$-Geodesic Center is NP-hard even on partial
grids.

###### keywords:

Hyperbolicity, approximation algorithms, Isometric paths, Minimum eccentricity
shortest paths.

##  1 Introduction

Given a graph $G,$ the $k$-Geodesic Center problem asks to find a collection
$\cal C$ of $k$ isometric paths such that the maximum distance between any
vertex and $\cal C$ is minimised. This problem may arise in determining a set
of $k$ "most accessible" speedy line routes in a network and can find
applications in communication networks, transportation planning, water
resource management and fluid transportation [23]. The decision version of
this problem asks, given a graph $G$ and two integers $k$ and $R,$ whether
there exist a collection $\cal C$ of $k$ isometric paths such that any vertex
of $G$ is at distance at most $R$ from $\cal C.$

$k$-Geodesic Center is related to several algorithmic problems studied in the
literature. $k$-Geodesic Center is a generalisation of Minimum Eccentricity
Shortest Path (MESP) where given an integer $R$, the objective is to decide if
there exists an isometric path $P$ such that the maximum distance between any
vertex and $P$ is at most $R$ [23]. Clearly, $1$-Geodesic Center is equivalent
to MESP. If, instead of isometric paths, we asks whether there exists a subset
of $k$ vertices of eccentricity at most $R,$ we obtain the decision version of
$k$-center which is one of the most studied facility location problem in the
literature [29, 30, 34, 40, 41]. The solution of a $k$-Geodesic Center can be
thought of as a relaxation of $k$-Center. $k$-Geodesic Center is also related
to Isometric Path Cover, where the objective is to find the minimum number of
isometric paths that contains all vertices of the input graph. Study of the
algorithmic aspects of Isometric Path Cover has garnered much attention
recently [11, 24, 26].

All the three problems (i.e. IPC, MESP, and $k$-Center) are NP-hard for
general graphs but are known to admit exact polynomial time algorithms when
the given graph $G$ is a tree [11, 23, 42]. This raises the question about the
complexity of these problems when the input graph is _close to a tree_? In
this paper, we consider the graph parameter _$\delta$ -hyperbolicity_ [28],
which measures how treelike a graph is from a metric point of view. See
Section 2 for a formal definition. Graphs with constant $\delta$-hyperbolicity
are called _hyperbolic_ graphs. From a practical perspective, the study of
$\delta$-hyperbolicity of graphs is motivated by the fact that many real-world
graphs are tree-like [1, 2, 31] or have small $\delta$-hyperbolicity [7, 25,
39]. From a theoretical perspective, many popular graph classes like interval
graphs, chordal graphs, $\alpha_{i}$-metric graphs [21], graphs with bounded
tree-length [20], link graphs of simple polygons [15] have constant
$\delta$-hyperbolicity.

Polynomial time approximation algorithms with an error (additive or
multiplicative) depending only on the $\delta$-hyperbolicity of $G$ exist for
MESP [38], $k$-Center [17, 25], and Isometric Path Cover [12]. Motivated by
the above results, in this paper, we provide an additive
$O(\delta)$-approximation algorithm111A feasible solution for a minimization
problem is said to be _additive $\alpha$-approximate_ if its objective value
is at most the optimum value plus $\alpha$. An _additive
$\alpha$-approximation algorithm_ for a minimization problem is a polynomial
time algorithm that produces an additive $\alpha$-approximate solution for
every instance of the input. for $k$-Geodesic Center on $\delta$-hyperbolic
graphs for arbitrary $k$. The same algorithmic approach leads to an exact
polynomial time algorithm in case of trees.

######  Theorem 1.1.

Let $G$ be a $\delta$-hyperbolic graph and $k$ be an integer. Then, there is a
polynomial time $O(\delta)$-additive approximation algorithm for $k$-Geodesic
Center on $G.$

Our algorithm has mainly two stages. In the first stage, we solve the “rooted”
version of $(2k-1)$-Geodesic Center, where we require that all isometric paths
in the solution has a common end-vertex. Then to reduce the number of
isometric paths, we use the _shallow pairing_ property of $\delta$-hyperbolic
graphs. See Definition 3.2. Intuitively, this property ensures that the
$2k$-many end-vertices of the $2k-1$ isometric paths obtained in the first
stage can be “paired” to obtain $k$ many isometric paths which together
provide an additive $O(\delta)$-approximation algorithm for $k$-Geodesic
Center. To the best of our knowledge, the shallow pairing property of
$\delta$-hyperbolic graphs was previously unknown and could be of independent
interest.

We also adapt a technique of Dragan & Leitert, (TCS ’17) to show that for
every $k\geq 1$, $k$-Geodesic Center is NP-hard even on _partial grids_. A
graph is a _partial grid_ if it is a subgraph of $(k\times k)$-grid for some
positive integer $k$.

######  Theorem 1.2.

For every integer $k\geq 1$, $k$-Geodesic Centre is NP-hard even on partial
grids.

Related Works To the best of our knowledge, the computational complexity of
$k$-Geodesic Center for arbitrary $k$ has not been studied before. Therefore,
we begin by surveying the relevant results on $1$-Geodesic Center i.e. the
MESP problem. Dragan & Leitart [23] gave several constant factor approximation
algorithms for MESP with varying running times on general graphs. In an
another paper [22], the authors proposed polynomial time algorithms for MESP
on graph classes like _chordal_ graphs and _distance hereditary_ graphs. In
fact the authors proved that, MESP admits an $O(n^{\gamma+3})$-time algorithm
on graphs with _projection gap_ at most $\gamma$, and $n$ vertices. The
parameter _projection gap_ generalises the notion of $\delta$-hyperbolicity.
Their result implies that MESP admits an $O(n^{4\delta+4})$-time algorithm on
graphs with $\delta$-hyperbolicity at most $\delta$, and $n$ vertices. We do
not know if MESP admits a fixed parameter algorithm with respect to
$\delta$-hyperbolicity. The same authors also proposed additive approximation
algorithms for graphs with bounded _tree-length_. Fixed parameter tractability
of MESP with respect to various graph parameters like modular width, distance
to cluster graph, maximum leaf number, feedback edge set, etc. have been also
studied recently [4, 33]. As noted by Kučera and Suchỳ [33], the fixed
parameter tractablility of MESP with respect to _tree-width_ is an interesting
open problem. (Tree-width measures how far a graph is from a tree from a
structural point of view.) Relation of MESP with other problems like the
_minimum distortion embedding on a line_ [23] and _$k$ -laminar_ problem [5]
have been established.

Dragan & Leitart [22] observed that MESP admits an additive $O(\delta\log
n)$-approximation algorithm on graphs with $\delta$-hyperbolicity at most
$\delta$ and $n$ vertices. Their proof uses the fact that the tree-length of
$\delta$-hyperbolic graphs are at most $O(\delta\log n)$. As the best known
bound for tree-length of $\delta$-hyperbolic graphs is $O(\delta\log n)$, this
method seems not directly provide constant error in case of hyperbolic graph.
Then, in the PhD Thesis of A.O. Mohammed [38], an $O(\delta)$-approximation
algorithm for MESP on $\delta$-hyperbolic graphs have been proposed. Other
examples include fast additive $O(\delta)$-approximation algorithms for
finding the diameter, radius, and all eccentricities [15, 16, 17] as well as
packing and covering for families of quasiconvex sets [14]. Theorem 1.1 adds
$k$-Geodesic Center in the list of problems admitting an additive
approximation algorithm depending only on the $\delta$-hyperbolicity of the
input graph. Recently, the computational complexity of maximum independent set
of planar $\delta$-hyperbolic graphs have been studied [32].

Organisation: In Section 2 we introduce some terminologies. In Section 3, we
introduce the notion of shallow pairing and prove its existence in
$\delta$-hyperbolic graphs. In Sections 4 and 5, we prove Theorems 1.1 and
1.2, respectively.

##  2 Preliminaries

Basic notations: For two vertices $u,v\in V(G)$, $\sigma(u,v)$ shall denote an
$(u,v)$-isometric path in $G$ and the length (i.e. the number of edges) in
$\sigma(u,v)$ is denoted as $d(u,v)$, the _distance_ between $u$ and $v$. If
an isometric path $P$ of $G$ has a vertex $r$ as end vertex, then $P$ is
called an _$r$ -path_.

For two sets $S_{1},S_{2}\subseteq V(G)$ of vertices,
$d(S_{1},S_{2})=\min\\{d(u,v)\colon u\in S_{1},v\in S_{2}\\}$ is the distance
between $S_{1}$ and $S_{2}$. For convenience, if one subset of vertices is a
singleton, we abbreviate $d(\\{v\\},S)$ by $d(v,S).$ For an integer $k$ and a
set of vertices $S$, the _$k$ -neighborhood (or $k$-ball) around $S$_, denoted
as $B_{k}\left({S}\right)$, is the set of all vertices $v$ such that
$d(v,S)\leq k$. For an integer $R$, a collection $\mathcal{C}$ of isometric
paths of $G$ is an _$R$ -cover_ of $G$ if

$\displaystyle\bigcup\limits_{P\in\mathcal{C}}B_{R}\left({V(P)}\right)=V(G)$

For an integer $k$, the symbol $R^{*}_{k}$ shall denote the minimum integer
for which there is a $R^{*}_{k}$-cover $\mathcal{C}$ of $G$ with
$|\mathcal{C}|=k$. If every path in $\mathcal{C}$ is an $r$-path, then
$\mathcal{C}$ is an _$(r,R)$ -cover_ of $G$. For an integer $R$, a vertex $r$
and a subset $S\subseteq V(G)$ is a _$(r,R)$ -packing_ if the $R$-neighborhood
of any $r$-path $P$ contains at most one vertex of $S,$ i.e.
$|B_{R}\left({V(P)}\right)\cap S|\leq 1$. Note that if $S$ is an
$(r,R)$-packing of $G$ then any $(r,R)$-cover of $G$ has size at least $|S|.$
Indeed, the $R$-neighborhood of any $r$-path covers at most one vertex in $S.$
Hence, it is not possible to cover $S$ with less than $|S|$ $r$-paths.

Definitions related to $\delta$-hyperbolicity: Let $(X,d)$ be a metric space.
A geodesic segment joining two points $x$ and $y$ from $X$ is a map $\rho$
from the segments $\sigma(a,b)$ of length $|a-b|=d(x,y)$ to $X$ such that
$\rho(a)=x,$ $\rho(b)=y$, and $d(\rho(s),\rho(t))=|s-t|$ for all
$s,t\in\sigma(a,b).$ A metric space $(X,d)$ is geodesic if every pair of
points in $X$ can be joined by a geodesic. We will denote by $\sigma(x,y)$ any
geodesic segment connecting the points $x$ and $y.$

Introduced by Gromov [28], $\delta$-hyperbolicity measures how treelike a
graph is from a metric point of view. Recall that a metric space $(X,d)$
embeds into a tree network (with positive real edge lengths), if and only if
for any four points $u,v,w,x$ the two larger of the distance sums
$d(u,v)+d(w,x),$ $d(u,w)+d(v,x),$ and $d(u,x)+d(v,w)$ are equal. A metric
space $(X,d)$ is called $\delta$-hyperbolic if the two larger distance sums
differ by at most $2\delta.$ For a metric space $(X,d),$ the _Gromov product_
of two points $x,y$ with respect to a third point $z$ is defined as

$\left(x|y\right)_{z}=\frac{1}{2}\left(d(x,z)+d(z,y)-d(x,y)\right)$

Equivalently, a metric space $(X,d)$ is $\delta$-hyperbolic if for any four
points $u,v,w,x,$

$\left(u|w\right)_{x}\geq\min\left\\{\left(u|v\right)_{x},\left(v|w\right)_{x}\right\\}-\delta.$

A connected graph $G=(V,E)$ equipped with standard graph metric $d_{G}$ is
$\delta$-hyperbolic if $(V,d_{G})$ is a $\delta$-hyperbolic metric space. The
$\delta$-hyperbolicity $\delta(G)$ of a graph $G$ is the smallest $\delta$
such that $G$ is $\delta$-hyperbolic.

There exists several equivalent definitions of $\delta$-hyperbolic metric
spaces involving different but comparable values of $\delta.$ In the proof of
Theorem 1.1, we will use the definition employing $\delta$-thin geodesic
triangles. A geodesic triangle $\Delta\left(x,y,z\right)$ is a union
$\sigma(x,y)\cup\sigma(x,z)\cup\sigma(y,z)$ of three geodesic segments
connecting these vertices. Let $m_{x}$ be the point of the geodesic
$\sigma(y,z)$ located at distance $\alpha_{y}:=\left(x|z\right)_{y}$ from $y.$
Then $m_{x}$ is located at distance $\alpha_{z}:=\left(x|y\right)_{z}$ from
$z$ because $\alpha_{y}+\alpha_{z}=d(y,z).$ Analogously, define the points
$m_{y}\in\sigma(x,z)$ and $m_{z}\in\sigma(x,y)$ both located at distance
$\alpha_{x}:=\left(y|z\right)_{x}$ from $x$; see Figure 1.

$\alpha_{y}$$\leq\delta$$\leq\delta$$m^{\prime}$$\varphi$$m_{x}$$m_{z}$$m_{y}$$x$$z$$x^{\prime}$$z^{\prime}$$y$$y^{\prime}$$\leq\delta$$\alpha_{x}$$\alpha_{z}$

Figure 1: A $\delta$-thin geodesic triangle

There exists a unique isometry $\varphi$ which maps the geodesic triangle
$\Delta\left(x,y,z\right)$ to a star $T(x,y,z)$ consisting of three solid
segments $\sigma(x^{\prime},m^{\prime}),$ $\sigma(y^{\prime},m^{\prime}),$ and
$\sigma(z^{\prime},m^{\prime})$ of length $\alpha_{x},$ $\alpha_{y},$ and
$\alpha_{z},$ respectively. This isometry maps the vertices $x,y,z$ of
$\Delta\left(x,y,z\right)$ to the respective leaves
$x^{\prime},y^{\prime},z^{\prime}$ of $T(x^{\prime},y^{\prime},z^{\prime})$
and the points $m_{x},$ $m_{y},$ and $m_{z}$ to the center $m$ of this tripod.
Any other point of $T(x^{\prime},y^{\prime},z^{\prime})$ is the image of
exactly two points of $\Delta\left(x,y,z\right).$ A geodesic triangle
$\Delta\left(x,y,z\right)$ is called $\delta$-thin [3] if for all points
$u,v\in\Delta\left(x,y,z\right),$ $\varphi(u)=\varphi(v)$ implies
$d(u,v)\leq\delta.$

The following result shows that the $\delta$-hyperbolicity of geodesic space
can be approximated by the maximum thinness of its geodesic triangles.

######  Proposition 2.1 ([3, 8, 28]).

Geodesic triangles of geodesic $\delta$-hyperbolic space are $4\delta$-thin.
Conversely, geodesic space with $\delta$-thin triangles are
$\delta$-hyperbolic.

Every graph $G=(V,E)$ equipped with its standard distance $d_{G}$ can be
transformed into a geodesic space $(X,d)$ by replacing every edge $e=(u,v)$ by
a solid segment $[u,v]$ of length $1.$ These segments may intersect only at
their common ends. Then $(V,d_{G})$ isometrically embeds naturally in $(X,d).$
The _thinness_ $\tau(G)$ of a graph $G$ is the smallest integer $\delta$, such
that all geodesic triangles of the geodesic space arising from $G$ are
$\delta$-thin. When thinness of a graph is $\delta$, then it is also called a
_$\delta$ -thin_ graph.

Subdivisions and partial grids: For a graph $G$, its _$\ell$ -subdivision_,
denoted as $G_{\ell}$, is obtained by replacement of all its edges by paths of
a fixed length $\ell\geq 1$. An _equal subdivision_ of $G$ is an
$\ell$-subdivision for some $\ell\geq 1$. The vertices of $G$ in $G_{\ell}$
are the _original vertices_. We shall use the following result.

######  Lemma 2.2 ([12]).

Let $G$ be a planar graph with maximum degree $4$. Then there exists a partial
grid graph $H$, which is an equal subdivision of $G$ and contains at most
$O(|V(G)|^{3})$ vertices.

##  3 Pairings and shallow pairings

In this section we first recall the definition of the pairing property
following the terminology of [9]. Then, we introduce a coarse version of this
property, called shallow pairing property, and show that this relaxed property
holds for $\delta$-hyperbolic graphs.

Given a connected graph $G$, a profile is any finite sequence
$\pi=(x_{1},\ldots,x_{n})$ of vertices of $G$. The _total distance_ of a
vertex $v$ of $G$ is defined by $F_{\pi}(v)=\sum_{i=1}^{n}d(v,x_{i}).$ A
_pairing_ $P$ is a partition of an even profile $\pi$ of length $k=2n,$ into
$n$ disjoint pairs. For a pairing $P$, define $D_{\pi}(P)=\sum_{\\{a,b\\}\in
P}d(a,b)$. The notion of pairing was defined by Gerstel and Zaks [27]; they
also proved the following weak duality between the functions $F_{\pi}$ and
$D_{\pi}$:

######  Lemma 3.1 ([27]).

For any even profile $\pi$ of length $k=2n$ of a connected graph $G$, for any
pairing $P$ of $\pi$ and any vertex $v$ of $G$, $D_{\pi}(P)\leq F_{\pi}(v)$
and the equality holds if and only if $v\in\bigcap_{\\{a,b\\}\in P}I(a,b)$.

We say that a graph $G$ satisfies the _pairing property_ if for any even
profile $\pi$ there exists a pairing $P$ of $\pi$ and a vertex $v$ of $G$ such
that $D_{\pi}(P)=F_{\pi}(v)$, i.e., the functions $F_{\pi}$ and $D_{\pi}$
satisfy the strong duality. Such a pairing is called a _perfect pairing_. By
Lemma 3.1, the pairing property of [27] coincides with the _intersecting-
intervals property_ of [35]. It was shown in [27] that trees satisfy the
pairing property. More generally, it was shown in [36] and independently in
[18] that cube-free median graphs also satisfy the pairing property. It was
proven in [35] that the complete bipartite graph $K_{2,n}$ satisfies the
pairing property. As observed in [35], the $3$-cube is a simple example of a
graph not satisfying the pairing property.

In general, $\delta$-hyperbolic graphs do not satisfy the pairing property
but, as shown below, they satisfy some coarse variant of the pairing property.
Before defining this variant, let first define the notion of $\gamma$-shallow
pairing

######  Definition 3.2 ($\gamma$-shallow pairing).

Let $G$ be a graph and $\pi$ an even profile of length $2k$. A _$\gamma$
-shallow pairing_ of $\pi$ is a pairing $P$ such that, there exists a vertex
$v$ with $\left(x|y\right)_{v}\leq\gamma$ for every $\\{x,y\\}\in P.$

In the definition of a perfect pairing $P$, the vertex $v$ belongs to every
interval between a pair of vertices in $P.$ As the following lemma shows, in
the definition of a $\gamma$-shallow pairing $P_{\gamma}$, the vertex $v$ is
at distance at most $\gamma+\tau(G)$ from every isometric path between a pair
of vertices in $P_{\gamma}.$

######  Lemma 3.3.

Let $G$ be a graph, $\pi$ be an even profile of length $2k$ and $P$ be a
$\gamma$-shallow pairing of $\pi$. Then there exists a vertex $v$ such that
$d(v,\sigma(x,y))\leq\gamma+\tau(G)$ for every geodesic $\sigma(x,y)$ with
$\\{x,y\\}\in P.$

######  Proof 3.4.

By definition of a $\gamma$-shallow pairing, there exists a vertex $v$ such
that $\left(x|y\right)_{v}\leq\gamma$ for every $\\{x,y\\}\in P.$ For any pair
of vertices $\\{x,y\\}\in P,$ consider the geodesic triangle $\Delta(x,y,v)$
and let $\sigma(v,x),\sigma(v,y),$ and $Q$ be the sides of this triangle. Let
$x^{\prime},y^{\prime}$ be the points of $\sigma(v,x)$ and $\sigma(v,y)$,
respectively, located at distance $\left(x|y\right)_{v}$ from $v$. Since the
thinness of $G$ is $\tau(G),$ $d(x^{\prime},y^{\prime})\leq\tau(G)$, moreover
$d(x^{\prime},z^{\prime})\leq\tau(G)$ and
$d(y^{\prime},z^{\prime})\leq\tau(G)$, where $z^{\prime}$ is the point of $Q$
at distance $\left(y|v\right)_{x}$ from $v$ and at distance
$\left(x|v\right)_{y}$ from $y$. Since, $\left(x|y\right)_{v}\leq\gamma$, we
conclude that $d(v,Q)\leq d(v,z^{\prime})\leq
d(v,x^{\prime})+d(x^{\prime},z^{\prime})\leq\gamma+\tau(G)$.

We say that a graph $G$ satisfies the _$\gamma$ -shallow pairing property_ if
for any even profile $\pi$ there exists a $\gamma$-shallow pairing $P$ of
$\pi$.

The existence and the computation in polynomial time of a
$(2\delta+\frac{1}{2})$-shallow pairing in a $\delta$-thin graph $G$ can be
obtained using the concept of fiber that was introduced in [14]. For a vertex
$u\in V(G)$ and a profile $\pi$, the fiber of $x$ with respect to a vertex $u$
is the set of vertices

$F_{u}(x)=\\{y\in\pi:(x|y)_{u}\geq 2\tau(G)+1\\}.$

From Claim 1 and 2 of [14], the following lemma holds.

######  Lemma 3.5.

For any graph $G$ and any even profile $\pi$ of length $2k,$ there is a vertex
$v\in V(G)$ such that $|F_{v}(x)|\leq k$ for any vertex $x\in\pi.$

Lemma 3.5 is useful to prove the following result:

######  Proposition 3.6.

Any graph $G$ satisfies the _$(2\tau(G)+\frac{1}{2})$ -shallow pairing
property_. Moreover, for any graph $G$ with $n$ vertices and $m$ edges, and
any even profile $\pi$ of length $2k,$ a $(2\tau(G)+\frac{1}{2})$-shallow
pairing of $\pi$ can be computed in $O(mn^{2})$ time.

######  Proof 3.7.

First, we will prove that the vertex $v$ whose existence is guaranteed by
Lemma 3.5 can be calculated efficiently. Indeed, an $O(mn^{2})$ time algorithm
was given in [13] to compute the thinness $\tau(G)$ of a graph $G$ with $n$
vertices and $m$ edges. The matrix of distances between every pair of vertices
can be computed in $O(mn)$ time. Then, for every vertex $u\in V(G)$, it is
possible to compute in $O(k^{2})$ time the Gromov products
$\left(x|y\right)_{u}$ for every pair of vertices $x,y\in\pi$. Within the same
running time, it is possible to also compute the fibers $F_{u}(x)$ for every
$x\in\pi.$ Indeed, it suffices to add $y$ to $F_{u}(x)$ and $x$ to $F_{u}(y)$
when we compute a value $\left(x|y\right)_{u}$ exceeding
$2\tau(G)+\frac{1}{2}.$ If the size of a fiber $F_{u}(x)$ becomes larger than
$k$ then we can abort and try the next vertex $u.$ The procedure stops once we
have find a vertex $v$ such that $F_{v}(x)\leq k$ for every vertex $x\in\pi.$
By Lemma 3.5, this happens for at least one vertex $v\in V(G).$ Hence, it is
possible to find in $O(mn+nk^{2})$ time a vertex $v$ such that $|F_{v}(x)|\leq
k$ for every $x\in\pi.$ Let $H$ be the graph defined on the vertices of $\pi$
by adding an edge between two vertices $x$ and $y$ whenever
$\left(x|y\right)_{v}\leq 2\tau(G)+\frac{1}{2}.$ By the choice of $v,$ every
vertex of $H$ has degree at least $k.$ By Dirac’s theorem, $H$ is Hamiltonian
and thus has a perfect matching $M.$ Such a perfect matching can be computed
in $O(\sqrt{n}m)$ time [6, 37]. The pairing defined by the end-vertices of
edges in $M$ is a $(2\delta+\frac{1}{2})$-shallow pairing of $\pi$ that can be
computed in $O(mn^{2})$ time. Indeed, the running time is dominated by the
algorithm that computes the thinness of $G$.

In the next section, for any pairing $P,$ we will denote by ${\cal S}(P)$ a
collection of isometric paths between every pair of vertices in $P,$ i.e.
${\cal S}(P):=\left\\{\sigma(x,y):\\{x,y\\}\in P\right\\}$

##  4 Additive approximation algorithm

In this section, we prove Theorem 4.1 which implies Theorem 1.1 by Proposition
2.1.

######  Theorem 4.1.

Let $G$ be a graph with $m$ edges, $n$ vertices and $k$ be an integer. Then,
Algorithm 3 is a $O(mn^{2}\log n)$-time $(6\tau(G)+1)$-additive approximation
algorithm for $k$-Geodesic Center on $G$.

We provide a brief outline of the proof for the above theorem and organisation
of this section. A collection $\mathcal{C}$ of isometric paths is “rooted” if
all the paths in $\mathcal{C}$ have a common end-vertex. First we show in
Section 4.1, that the rooted version of the $k$-Geodesic Center problem where
we require that the collection of isometric paths is rooted can be solved in
polynomial time up to an additive $2\delta$ error in $\delta$-thin graphs. For
that, we use a primal dual algorithm and a dichotomy to find an integer $R$
such that there is a collection of $2k-1$ isometric rooted paths of
eccentricity $R+2\delta$ and no such collection has eccentricity smaller than
$R.$ Then in Section 4.2, we show that any collection $\cal C$ of $k$
isometric paths can be transformed into a rooted collection $\cal C^{\prime}$
of size $2k-1$ such that the eccentricity of $\cal C^{\prime}$ is at most the
eccentricity of $\cal C$ plus $\delta$. From this observation and the choice
of $R$, we conclude that no collection of $k$ isometric paths has eccentricity
smaller than $R-\delta.$ To transform the rooted collection returned by the
primal-dual algorithm into a non rooted collection of size $k,$ we also need a
converse result. For that, using the $(2\delta+\frac{1}{2})$-shallow pairing
property of $\delta$-thin graphs, in Section 4.3, we show that any rooted
collection $\cal C^{\prime}$ of $2k-1$ isometric paths can be transformed into
a non rooted collection $\cal C$ of $k$ isometric paths such that the
eccentricity of $\cal C$ is at most the eccentricity of $\cal C^{\prime}$ plus
$3\delta+1.$ We complete the proof in Section 4.4 as follows: the rooted
collection of eccentricity $R+2\delta$ computed by our primal-dual algorithm
can be transformed into a collection of size $k$ and eccentricity
$R+5\delta+1.$ Since there is no such collection with an eccentricity less
than $R-\delta,$ the collection of eccentricity $R+5\delta+1$ is optimal up to
a $6\delta+1$ error.

###  4.1 An algorithm for the Rooted $k$-Geodesic Center problem

In this Section, we present an algorithm that, given a $\delta$-thin graph
$G,$ computes an integer $R$ such that no collection of $2k-1$ rooted
isometric paths has eccentricity smaller than $R$ and there is a collection of
$2k-1$ isometric rooted paths of eccentricity $R+2\delta.$ Our description of
this algorithm proceeds in two steps. First, we describe Algorithm 1. Given a
graph $G,$ a root $r\in V(G)$ and integer $R,$ Algorithm 1 outputs either an
$(r,R+2\delta)$-cover of $G$ of size $2k-1$ or a $(r,R)$-packing of size $2k$.
Then, Algorithm 2 uses Algorithm 1 to perform a dichotomy. For every vertex
$u\in V(G),$ Algorithm 2 computes the smallest value $R_{u}$ for which
Algorithm 1 outputs a cover. We show that $R:=\min\\{R_{u}:u\in V(G)\\}$ is an
integer such that no collection of $2k-1$ rooted isometric paths has
eccentricity smaller than $R$ and there is a collection of $2k-1$ isometric
rooted paths of eccentricity $R+2\delta.$ We start with the following
technical lemma.

######  Lemma 4.2.

Let $\sigma(u,v)\cup\sigma(v,w)\cup\sigma(u,w)$ be a geodesic triangle with
$d(w,\sigma(u,v))\leq R.$ Then, $(u|v)_{w}\leq R.$

######  Proof 4.3.

Let $y$ be a vertex of $\sigma(u,v)$ at distance at most $R$ from $w.$ Let
$y^{\prime}$ be the vertex of $\Delta(u,v,w)$ such that
$\varphi(y)=\varphi(y^{\prime}).$ Without loss of generality, we can assume
that $y^{\prime}\in\sigma(v,w).$ By triangle inequality,
$d(w,v)=d(w,y^{\prime})+d(y^{\prime},v)\leq d(w,y)+d(y,v).$ Since
$d(v,y^{\prime})=d(v,y),$ we get $d(w,y^{\prime})\leq d(w,y).$ Hence,
$(u|v)_{w}\leq d(w,y^{\prime})\leq d(w,y)\leq R.$

Input : A $\delta$-thin graph $G$, $r\in V(G)$, $R\in\mathbb{N}$, an integer
$k\leq|V(G)|$

Output : $(r,R+2\delta)$-cover of $G$ of size $2k-1$ or an $(r,R)$-packing of
size $2k$.

1

2$X=V(G)$; $i=0$;

3while  _ $i\leq 2k-1$ and $X\neq\emptyset$_ do

4 Let $v_{i}\in X$ be a vertex with $d(r,v_{i})\geq d(r,z)$ for all $z\in X$;

5 Let $\sigma_{i}$ be any $(r,v_{i})$-isometric path;

6 $X_{i}=\left\\{u\in X:\ \exists\ \text{an $r$-path}\ P\ \text{such that}\
d(u,P)\leq R\ \text{and}\ d(v_{i},P)\leq R\right\\}$

7 $X=X\setminus X_{i}$;

8 $\mathcal{P}=\mathcal{P}\cup\\{v_{i}\\}$;

9 $\mathcal{C}=\mathcal{C}\cup\\{\sigma_{i}\\}$.

10 $i=i+1$;

11

12if  _$X=\emptyset$_ then

13 return $\mathcal{C}$;

14else

15 return $\mathcal{P}$

16

17

Algorithm 1

######  Lemma 4.4.

Algorithm 1 either returns an $(r,R)$-packing of size $2k$ or an
$(r,R+2\delta)$-cover of $G$ of size at most $2k-1$.

######  Proof 4.5.

First assume that Algorithm 1 returns a subset of vertices $\mathcal{P}$.
Suppose there exists two vertices $\\{v_{i},v_{j}\\}\subseteq\mathcal{P}$ with
$i<j$ such that  (a) $v_{i},v_{j}$were included in $\mathcal{P}$ at the
$i^{th}$ and $j^{th}$ iteration of Algorithm 1, and  (b) there exists an
$r$-path $P$ such that $\\{v_{i},v_{j}\\}\subseteq
B_{R}\left({V(P)}\right)\cap\mathcal{P}$. But then $v_{j}\in X_{i}$ and
therefore was removed from $X$ in the $i^{th}$ iteration, a contradiction.

Now assume that Algorithm 1 returns a collection of $r$-paths $\mathcal{C}$.
For a vertex $u\in V(G)$, let $v_{i}\in\mathcal{P}$ be the vertex such that
$u\in X_{i}$ when $u$ was removed from $X.$ By definition of $X_{i},$ there
exists an $r$-path $P$ such that $d(u,P)\leq R$ and $d(v_{i},P)\leq R.$ Let
$x$ be the end-vertex of $P$ distinct from $r.$ Let $\sigma_{i}$ be the
$r$-path added to $\cal C$ by Algorithm 1 during the $i^{th}$ iteration and
$\sigma(r,u)$ be any isometric path between $r$ and $u$. We distinguish two
cases (see Figure 2).

  * •

Case 1. First suppose that $(u|x)_{r}\leq(v_{i}|x)_{r}.$ Let $m_{i},$
$m^{\prime}_{i},$ $m^{\prime\prime}_{i}$ be the points of $\sigma_{i},$ $P$
and $\sigma(r,u)$ at distance $(u|x)_{r}$ from $r.$ Since
$d(u,\sigma(r,x))\leq R,$ Lemma 4.2 implies
$d(u,m^{\prime\prime}_{i})=(r|x)_{u}\leq R.$ Hence, the $\delta$-thinness of
the geodesic triangles $\sigma(r,u)\cup\sigma(u,x)\cup P$ and
$\sigma_{i}\cup\sigma(v_{i},x)\cup P$ implies $d(u,m_{i})\leq
d(u,m^{\prime\prime}_{i})+d(m^{\prime\prime}_{i},m^{\prime}_{i})+d(m^{\prime}_{i},m_{i})\leq
R+2\delta.$

  * •

Case 2. Now, assume that $(v_{i}|x)_{r}\leq(u|x)_{r}.$ Let $m_{i},$
$m^{\prime}_{i},$ $m^{\prime\prime}_{i}$ be the vertices of $\sigma_{i},$ $P$
and $\sigma(r,u)$ at distance $(v_{i}|x)_{r}$ from $r.$ By the choice of
$v_{i},$ $d(r,m_{i})+d(m_{i},v_{i})=d(r,v_{i})\geq
d(r,u)=d(r,m^{\prime\prime}_{i})+d(m^{\prime\prime}_{i},u).$ Since
$d(r,m_{i})=d(r,m^{\prime\prime}_{i}),$ we deduce that
$d(m^{\prime\prime}_{i},u)\leq d(m_{i},v_{i}).$ Since
$d(v_{i},\sigma(r,x))\leq R,$ Lemma 4.2 implies $d(m^{\prime\prime}_{i},u)\leq
d(m_{i},v_{i})=(r|x)_{v_{i}}\leq R.$ Using the thinness of geodesic triangles
$\sigma(r,u)\cup\sigma(u,x)\cup P$ and $\sigma_{i}\cup\sigma(v_{i},x)\cup P,$
we derive that $d(u,m_{i})\leq
d(u,m^{\prime\prime}_{i})+d(m^{\prime\prime}_{i},m^{\prime}_{i})+d(m^{\prime}_{i},m_{i})\leq
R+2\delta.$

We conclude that any vertex $u\in V(G)$ is at distance at most $R+2\delta$
from some path in $\mathcal{C}$.

|
---|---
Case 1. $(u|x)_{r}\leq(v_{i}|x)_{r}$ |  Case 2. $(u|x)_{r}>(v_{i}|x)_{r}$
Figure 2: Illustrations for the two cases in the proof of Lemma 4.4.

Input : A $\delta$-thin graph $G$, an integer $k\leq|V(G)|$.

Output : An integer $R$ and an $(u,R+2\delta)$-cover of size $2k-1$ such that
there is no $(v,R^{\prime})$-cover with $R^{\prime}<R.$

1

2for  _$v\in V(G)$_ do

3

4 Let $R_{v}$ be the smallest $R$ integer for which Algorithm 1 returns a
$(v,R+2\delta)$-cover $\mathcal{C}_{v}$ of size $2k-1.$

/* The above steps can be implemented by using Algorithm 1 in combination with
a binary search on $R_{v}\in\\{0,1,\ldots,|V(G)|\\}$. */

5

6Let $u\in V(G)$ such that $R_{u}=\min\\{R_{v}\colon v\in V(G)\\}$.

7return $(\mathcal{C}_{u},R_{u})$.

8

Algorithm 2

######  Lemma 4.6.

Algorithm 2 returns an integer $R$ and a $(u,R+2\delta)$-cover
$\mathcal{C}_{u}$ of $G$ of size $2k-1$ such that, there is no
$(v,R^{\prime})$-cover of size $2k-1$ with $R^{\prime}<R.$

######  Proof 4.7.

Let $\left(\mathcal{C}_{u},R_{u}\right)$ be the output of Algorithm 2. Since
$R_{u}=\min\\{R_{v}\colon v\in V(G)\\}$ is the minimum integer $R$ for which
Algorithm 1 returns $(u,R+2\delta)$-cover $\mathcal{C}_{u},$ Algorithm 1
returns a $(v,R^{\prime})$-packing of size $2k$ for any $R^{\prime}<R_{u}$ and
any $v\in V(G).$ Hence, there is no $(v,R^{\prime})$-cover of size $2k-1$ with
$R^{\prime}<R.$

###  4.2 From non rooted to rooted collection of paths

In the following lemma, we show that if there is an $R$-cover of size $k$ of a
$\delta$-thin graph then there is a rooted $(r,R+\delta)$-cover of size $2k-1$
of $G,$ for some $r\in V(G)$.

######  Lemma 4.8.

Let $\mathcal{C}$ be an $R$-cover of a $\delta$-thin graph $G$ with
$|\mathcal{C}|=k,$ $X_{\mathcal{C}}$ the set of end-vertices of paths in
$\mathcal{C}$ and $r\in X_{\mathcal{C}}.$ Then, any collection isometric paths
$\mathcal{C}_{r}=\left\\{\sigma(r,x)\colon x\in
X_{C}\setminus\\{r\\}\right\\}$ is an $(r,R+\delta)$-cover of $G$.

######  Proof 4.9.

For a vertex $u\in V(G)$, let $P=\sigma(v_{1},v_{2})\in\mathcal{C}$ be a path
such that $d(u,P)\leq R$ and $w\in V(P)$ be a vertex with $d(u,w)\leq R$. Let
$P_{1},P_{2}\in\mathcal{C}_{r}$ where $P_{i}=\sigma(r,v_{i})$. Since the
geodesic triangle $P\cup P_{1}\cup P_{2}$ of $G$ is $\delta$-thin, either
$d(w,P_{1})\leq\delta$ or $d(w,P_{2})\leq\delta$. Therefore, either
$d(u,P_{1})\leq R+\delta$ or $d(u,P_{2})\leq R+\delta$. Hence,
$\mathcal{C}_{r}$ is a $(r,R+\delta)$-cover of $G$.

###  4.3 From rooted to non rooted collection of paths

Figure 3: Illustration of the notations used in Proof of Lemma 4.10.

Conversely, the next lemma shows that, from a set of rooted isometric paths of
a $\delta$-thin graph of size $2k-1$ and eccentricity $R$, it is possible to
construct a $(R+3\delta+1)$-cover of $G$ of size $k$.

######  Lemma 4.10.

Let $r$ be a vertex of a $\delta$-thin graph $G$. For integers $R$ and $k$,
let $\mathcal{C}_{r}$ be an $(r,R)$-cover of $G$ with
$|\mathcal{C}_{r}|=2k-1.$ Let $\pi_{r}$ be a profile of length $2k$ containing
all end vertices of the paths in $\mathcal{C}_{r}$ and $P_{r}$ be a
$(2\delta+\frac{1}{2})$-shallow pairing of $\pi_{r}$. Then, ${\cal S}(P_{r})$
is a $(R+3\delta+1)$-cover of $G$ of size $k.$

######  Proof 4.11.

Let $u\in V(G)$ and $P=\sigma(r,x)\in\mathcal{C}_{r}$ be an $r$-path with
$d(u,P)\leq R$. Let $\\{x^{\prime},r^{\prime}\\}\subseteq\pi_{r}$ be the
vertices such that $\\{x,x^{\prime}\\}\in P_{r}$ and $\\{r,r^{\prime}\\}\in
P_{r}$. By definition of a $(2\tau(G)+\frac{1}{2})$-shallow pairing, we have
that $\left(x|x^{\prime}\right)_{m}\leq 2\delta+\frac{1}{2}$ and
$\left(r|r^{\prime}\right)_{m}\leq 2\delta+\frac{1}{2}$ which imply the
following inequalities:

$d(x,m)+d(m,x^{\prime})-d(x,x^{\prime})\leq 4\delta+1\Rightarrow
d(x,x^{\prime})\geq d(x,m)+d(m,x^{\prime})-(4\delta+1)$
$d(r,m)+d(m,r^{\prime})-d(r,r^{\prime})\leq 4\delta+1\Rightarrow
d(r,r^{\prime})\geq d(r,m)+d(m,r^{\prime})-(4\delta+1)$

Combining the above inequalities we derive:

$d(x,x^{\prime})+d(r,r^{\prime})\geq(d(x,m)+d(m,r^{\prime}))+(d(x^{\prime},m)+d(m,r))-(8\delta+2)\geq
d(x,r^{\prime})\\\ +d(x^{\prime},r)-(8\delta+2)$ (1)

Adding $d(r,x)$ to both sides of (1) we get:

$d(r,x)+d(x,x^{\prime})-d(r,x^{\prime})\geq
d(r,x)+d(x,r^{\prime})-d(r,r^{\prime})-(8\delta+2)$

which further implies:

$\left(r|x^{\prime}\right)_{x}\geq\left(r|r^{\prime}\right)_{x}-(4\delta+1)$
(2)

Recall that $P=\sigma(r,x)\in\mathcal{C}_{r}$. Let $m_{x}$ be the point of the
geodesic $P$ such that
$d(x,m_{x})=\lfloor\left(r|x^{\prime}\right)_{x}\rfloor$ and $m_{r}$ be the
point of the geodesic $P$ such that
$d(x,m_{r})=\lceil\left(r|r^{\prime}\right)_{x}\rceil$. Let $z$ be the vertex
of $P$ with $d(u,z)\leq R$. Consider the following cases.

  * •

If $z$ lies in the $(x,m_{x})$-subpath of $P$, consider any isometric path
$\sigma(r,x^{\prime}).$ Since the geodesic triangle
$P\cup\sigma(r,x^{\prime})\cup\sigma(x,x^{\prime})$ is $\delta$-thin, we have
that $d(z,\sigma(x,x^{\prime}))\leq\delta$. Hence,
$d(u,\sigma(x,x^{\prime}))\leq d(u,z)+d(z,\sigma(x,x^{\prime}))\leq R+\delta$.

  * •

If $z$ lies in the $(r,m_{r})$-subpath of $P$, consider any isometric path
$\sigma(r^{\prime},x).$ Since the geodesic triangle
$P\cup\sigma(r,r^{\prime})\cup\sigma(r^{\prime},x)$ is $\delta$-thin, we have
that $d(z,\sigma(r,r^{\prime}))\leq\delta.$ Hence,
$d(u,\sigma(r,r^{\prime}))\leq d(u,z)+d(z,\sigma(r,r^{\prime}))\leq R+\delta$.

  * •

Otherwise, $z$ must lie in the $(m_{r},m_{x})$-subpath of $P$. Due to
inequality (2) we have that $d(m_{r},m_{x})\leq 4\delta+2.$ This implies
either $d(z,m_{x})\leq 2\delta+1$ or $d(z,m_{r})\leq 2\delta+1$. Since the
geodesic triangles $P\cup\sigma(r,x^{\prime})\cup\sigma(x,x^{\prime})$ and
$P\cup\sigma(r,r^{\prime})\cup\sigma(x,r^{\prime})$ are $\delta$-thin, we have
$d(m_{x},\sigma(x,x^{\prime}))\leq\delta$ and
$d(m_{r},\sigma(r,r^{\prime}))\leq\delta.$ If $d(z,m_{x})\leq 2\delta+1$ then
$d(u,\sigma(x,x^{\prime}))\leq
d(u,z)+d(z,m_{x})+d(m_{x},\sigma(x,x^{\prime}))\leq R+3\delta+1$. Otherwise,
$d(z,m_{r})\leq 2\delta+1$ and $d(u,\sigma(r,r^{\prime}))\leq
d(u,z)+d(z,m_{r})+d(m_{r},\sigma(r,r^{\prime}))\leq R+3\delta+1$.

In all three above cases, either $d(u,\sigma(x,x^{\prime}))\leq R+3\delta+1$
or $d(u,\sigma(r,r^{\prime}))\leq R+3\delta+1.$ We conclude that, for any
$u\in V(G)$, the collection ${\cal S}(P_{r})$ contains an isometric path $Q$
such that $d(u,Q)\leq R+3\delta+1,$ i.e. ${\cal S}(P_{r})$ is a
$(R+3\delta+1)$-cover.

###  4.4 Proof of Theorem 4.1

Input : A $\delta$-thin graph $G$, an integer $k\leq|V(G)|$.

Output : A collection of $k$ isometric paths with eccentricity at most
$R^{*}_{k}+(6\tau(G)+1)$

1

2Let $\mathcal{C}_{u}$ be the $(u,R_{u})$-cover of $G$ returned by Algorithm 2
with $G$ and $k$ as input.

3Let $\pi$ be the even profile consisting of $u$ and every other end vertex of
the $u$-paths in $\mathcal{C}_{u}$.

4Computes a $(2\tau(G)+\frac{1}{2})$-shallow pairing $P$ of $\pi.$

5return $\mathcal{S}(P)$.

6

Algorithm 3

Let $G$ be a connected graph and $\delta=\tau(G)$ its thinness. Let
$\mathcal{C}^{*}$ be a $R^{*}_{k}$-cover of $G,$ $\pi_{\mathcal{C}^{*}}$ the
profile containing the end-vertices of paths in $\mathcal{C}^{*}$ and
$r\in\pi_{\mathcal{C}^{*}}$. Consider the set
$\mathcal{C}^{*}_{r}=\left\\{\sigma(r,x)\colon
x\in\pi_{\mathcal{C}^{*}}\setminus\\{r\\}\right\\}$. Due to Lemma 4.8, we have

$\mathcal{C}^{*}_{r}\text{ is a }\left(r,R^{*}_{k}+\delta\right)\text{-cover
of }G.$ (3)

Now let $\left(\mathcal{C}_{u},R_{u}\right)$ be the output of Algorithm 2. By
Lemma 4.6, there is no $(r,R^{\prime})$-cover of size $2k-1$ with
$R^{\prime}<R_{u}.$ Due to (3), there exists a $(r,R^{*}_{k}+\delta)$-cover of
$G$ of size $2k-1.$ Hence, $R_{u}\leq R^{*}_{k}+\delta$ and $\mathcal{C}_{u}$
has eccentricity at most $R_{u}+2\delta\leq R^{*}_{k}+3\delta.$ Let $\pi_{u}$
be the profile consisting of $u$ and every other end vertex of the $u$-paths
in $\mathcal{C}_{u}$. Observe that $\pi_{u}$ is an even profile of length of
$2k.$ By Proposition 3.6, it is possible to compute in $O(mn^{2})$-time a
$(2\tau(G)+\frac{1}{2})$-shallow pairing $P^{\prime}$ of $\pi_{u}$. Due to
Lemma 4.10, ${\cal S}(P^{\prime})$ is an $(R^{*}_{k}+6\delta+1)$-cover of size
$k.$ This completes the proof of Theorem 4.1. Algorithm 3 describes our
complete algorithm for $k$-Geodesic Center on $\delta$-thin graphs.

Clearly, the running times of Algorithm 1 and Algorithm 2 are $O(k(n+m))$ and
$O(nk(n+m)\log n)$, respectively. Due to Proposition 3.6, computing a shallow
pairing takes $O(mn^{2})$-time. Therefore, the total running time of Algorithm
3 is $O(mn^{2}\log n)$.

###  4.5 The special case of trees

In case of trees, the same algorithmic approach leads to an exact polynomial
time algorithm. Indeed, since trees are $0$-hyperbolic, Lemma 4.6 implies that
Algorithm 2 computes a rooted $(r,R)$-cover $\mathcal{C}$ of size $2k-1$ such
that there is no $(r^{\prime},R^{\prime})$-cover with $R^{\prime}<R.$ By Lemma
4.4, an optimal $R^{*}$-cover of size $k$ can be transformed into a rooted
$(r^{\prime},R^{*})$-cover of size $2k-1.$ Hence, $R^{*}\geq R.$ Since trees
satisfy the pairing property, any $(r,R)$-cover of size $2k-1$ can be
transformed into an $R$-cover of size $k.$ This implies $R\geq R^{*}.$ Hence,
in case of trees, $R=R^{*}$ and the solution returned by Algorithm 3 is an
optimal $R^{*}$-cover of size $k$.

##  5 NP-hardness for partial grids

In this section we prove Theorem 1.2. Our proof is an adaptation of the NP-
hardness of $1$-Geodesic Center on planar bipartite graphs proved by Dragan &
Leitert (Corollary 8, [23]). First we prove the following lemmas.

######  Lemma 5.1.

Let $G$ be a graph and $H=G_{\ell}$ for some $\ell\geq 1$. Then for integers
$m,k$, if $G$ has an $m$-cover of size $k$ then $H$ has an
$\left(m\ell+\left\lfloor\ell/2\right\rfloor\right)$-cover of size $k$.

######  Proof 5.2.

Let $\mathcal{C}$ be an $m$-cover of $G$ of size $k$ and
$\mathcal{C}^{\prime}$ be a set of paths in $H$ which are $\ell$-subdivision
of the paths in $\mathcal{C}$. Clearly, all paths in $\mathcal{C}^{\prime}$
consists of isometric paths in $H$. Let $u$ be an original vertex of $H$ and
$P\in\mathcal{C}$ be a path such that $d(u,V(P))\leq m$ in $G$. Let
$P^{\prime}\in\mathcal{C}^{\prime}$ be the $\ell$-subdivision of $P$. Clearly,
$d(u,V(P^{\prime}))\leq m\ell$. Now consider a vertex $u\in V(H)$ which is not
a vertex of $G$. Hence there exists an original vertex $u^{\prime}\in V(H)$
with $d(u,u^{\prime})\leq\left\lfloor\ell/2\right\rfloor$. Let
$P\in\mathcal{C}$ be a path such that $d(u^{\prime},V(P))\leq m$ in $G$ and
$P^{\prime}\in\mathcal{C}^{\prime}$ be the $\ell$-subdivision of $P$. Then
$d(u,V(P^{\prime}))\leq d(u,u^{\prime})+d(u^{\prime},V(P^{\prime}))\leq
m\ell+\left\lfloor\ell/2\right\rfloor$.

Let $G$ be a graph and $H=G_{\ell}$ for some $\ell\geq 1$. For an isometric
path $P$ of $H$ between two original vertices $u,v$, let $G(P)$ denote the
$(u,v)$-isometric path in $G$ such that $P$ is an $\ell$-subdivision of
$G(P)$. Intuitively, $G(P)$ is the original isometric path whose
$\ell$-subdivision created $P$ in $H$.

######  Lemma 5.3.

Let $G$ be a graph and let $H=G_{\ell}$ for some $\ell\geq 1$. Let $P$ be an
isometric path of $H$ between two original vertices $u,v$. Let $w$ be an
original vertex of $G$ such that $d(w,V(P))<(r+1)\ell$ for some positive
integer $r$. Then, for $Q=G(P)$ we have $d(w,V(Q))\leq r$.

######  Proof 5.4.

Let $w^{\prime}\in V(P)$ be a vertex which is closest to $w$ in $H$ and
$P^{\prime}$ be an $(w,w^{\prime})$-isometric path in $H$. Clearly,
$w^{\prime}$ is an original vertex and therefore $G(P^{\prime})$ exists.
Observe that, the number of original vertices in $P^{\prime}$ is at most
$r+1$. (Otherwise length of $P^{\prime}$ is at least $(r+1)\ell$ in $H$ which
is a contradiction.) Hence length of $G(P)$ is at most $r$ in $G$.

Dragan & Leitert [23] reduced the NP-complete Planar Monotone 3-SAT [19] to
show that $1$-Geodesic Center is NP-hard on bipartite planar subcubic graphs.
Given an Planar Monotone 3-SAT instance $I$, the authors constructed a planar
bipartite subcubic graph $B\left(I\right)$ and an integer $m^{\prime}$ with
the following properties.

  * •

$B\left(I\right)$ has an isometric path with eccentricity at most $m^{\prime}$
if and only if $I$ is satisfiable;

  * •

there are two special cut vertices $v_{0},v_{n}$ of $B\left(I\right)$ such
that any isometric path with eccentricity at most $m^{\prime}$ will contain
$v_{0}$ and $v_{n}$.

To prove our result, we modify the graph $B\left(I\right)$ slightly. First
construct a gadget as follows. Take a path $P$ of length $2k$ and let the
vertices of $P$ be $u_{1},u_{2},\ldots,u_{2k+1}$. For each $j\in[2,2k]$, take
a new path $Q_{j}$ of length $m^{\prime}$ and make one of the end-vertex of
$Q_{j}$ adjacent to $u_{j}$. Let $T$ be the union of $P$ and
$Q_{j},j\in[2,2k-1]$. Now make the vertex $v_{0}$ adjacent to $u_{1}$.

We call the modified graph $B^{\prime}_{k}\left(I\right)$. It is easy to
verify that a set $\mathcal{P}$ of isometric paths in
$B^{\prime}_{k}\left(I\right)$ is an $m^{\prime}$-cover if and only if the
following holds:

  * •

There are $k-1$ isometric paths in $B^{\prime}_{k}\left(I\right)$ whose
vertices completely lie in $T$.

  * •

There is a special isometric path $P$ in $B^{\prime}_{k}\left(I\right)$
containing $v_{0},v_{n}$ such that $P$ has eccentricity $m^{\prime}$ in
$B\left(I\right)$.

The above discussion implies that $B^{\prime}_{k}\left(I\right)$ has an
$m^{\prime}$-cover of size $k$ if and only if $B\left(I\right)$ has an
$m^{\prime}$-cover of cardinality one. Moreover,
$B^{\prime}_{k}\left(I\right)$ is planar and has maximum degree at most $3$.
Now we construct a $H=P_{k}\left(I\right)$ by applying Lemma 2.2 on
$G=B^{\prime}_{k}\left(I\right)$ and $\ell$ be the integer such that
$H=G_{\ell}$. We prove that $G$ has an $m^{\prime}$-cover of cardinality $k$
if and only if $H$ has an
$\left(m^{\prime}\ell+\left\lceil\ell/2\right\rceil\right)$-cover of
cardinality $k$.

If $G$ has an $m^{\prime}$-cover of cardinality $k$, then Lemma 5.1 implies
that $H$ has an
$\left(m^{\prime}\ell+\left\lceil\ell/2\right\rceil\right)$-cover of
cardinality $k$. Now assume that $H$ has an
$\left(m^{\prime}\ell+\left\lceil\ell/2\right\rceil\right)$-cover
$\mathcal{C}$ of cardinality $k$. Let $T_{\ell}$ be the induced subgraph of
$P_{k}\left(I\right)$ isomorphic to the $\ell$-subdivision of $T$. The
structure of $T_{\ell}$ implies that there will be $k-1$ isometric paths whose
vertices lies completely in $T_{\ell}$. Let $B_{\ell}$ denote the subgraph of
$P_{k}\left(I\right)$ isomorphic to the $\ell$-subdivision of
$B\left(I\right)$. Since the original vertices $v_{0}$ and $v_{n}$ are still
cut vertices in $P_{k}\left(I\right)$, there is a special path
$P\in\mathcal{C}$ such that all vertices in $B_{\ell}$ is at a distance at
most $m^{\prime}\ell+\left\lceil\ell/2\right\rceil$ from $P$. Now apply Lemma
5.3 to conclude that all vertices of $B\left(I\right)$ which also belongs to
$B^{\prime}_{k}\left(I\right)$ is at distance $m^{\prime}$ from $G(P)$.
Therefore, the set $\mathcal{C}^{\prime}=\\{G(P)\colon P\in\mathcal{C}\\}$ is
an $m^{\prime}$-cover of $G$.

The above discussion implies that $P_{k}\left(I\right)$ has an
$\left(m^{\prime}\ell+\left\lceil\ell/2\right\rceil\right)$-cover of
cardinality $k$ if and only if $I$ is satisfiable. This completes the proof.

##  6 Conclusion

Constant factor approximability of $k$-Geodesic Center in general graphs for
$k\geq 2$ remains open. From both application and theoretical point of views,
approximability of $k$-Geodesic Center on planar graphs is an important open
question. An approximation scheme even for MESP on planar graphs is open.
Studying whether $k$-Geodesic Center (for arbitrary $k$) is fixed-parameter
tractable with respect to tree-width or hyperbolicity are interesting research
questions. Polynomial solvability of $k$-Geodesic Center in superclasses of
trees (e.g. outerplanar graphs), solid grids (i.e. partial grids where
internal faces have unit area), are open as well. For graphs with bounded
isometric path complexity (including hyperbolic graphs), IPC admits a constant
factor approximation algorithm [10]. It would be interesting to explore if
$k$-Geodesic Center admits an additive approximation algorithm on graphs with
bounded isometric path complexity? Finally, investigating the approximability
or fixed-parameter tractability of $k$-Geodesic Center on weighted graphs are
interesting directions.

## References

  * [1] M. Abu-Ata and F.F. Dragan.  Metric tree-like structures in real-world networks: an empirical study.  Networks, 67(1):49–68, 2016.
  * [2] A.B. Adcock, B.D. Sullivan, and M.W. Mahoney.  Tree-like structure in large social and information networks.  In Hui Xiong, George Karypis, Bhavani Thuraisingham, Diane J. Cook, and Xindong Wu, editors, 2013 IEEE 13th International Conference on Data Mining, Dallas, TX, USA, December 7-10, 2013, pages 1–10. IEEE Computer Society, 2013.
  * [3] J.M. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro, and H. Short.  Notes on word hyperbolic groups.  In Group theory from a geometrical viewpoint. 1991.
  * [4] S. Bhyravarapu, S. Jana, L. Kanesh, S. Saurabh, and S. Verma.  Parameterized algorithms for eccentricity shortest path problem.  In International Workshop on Combinatorial Algorithms, pages 74–86. Springer, 2023.
  * [5] E. Birmelé, F. De Montgolfier, and L. Planche.  Minimum eccentricity shortest path problem: An approximation algorithm and relation with the k-laminarity problem.  In Combinatorial Optimization and Applications: 10th International Conference, COCOA 2016, Hong Kong, China, December 16–18, 2016, Proceedings 10, pages 216–229. Springer, 2016.
  * [6] N. Blum.  A new approach to maximum matching in general graphs.  In Automata, Languages and Programming: 17th International Colloquium Warwick University, England, July 16–20, 1990 Proceedings 17, pages 586–597. Springer, 1990.
  * [7] M Borassi, D. Coudert, P. Crescenzi, and A Marino.  On computing the hyperbolicity of real-world graphs.  In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 215–226. Springer, 2015.
  * [8] M.R. Bridson and A. Haefliger.  Metric spaces of non-positive curvature, volume 319.  Springer Science & Business Media, 2013.
  * [9] L. Bénéteau, J. Chalopin, V. Chepoi, and Y. Vaxès.  Abc(t)-graphs: an axiomatic characterization of the median procedure in graphs with connected and g2-connected medians, 2022.
  * [10] D. Chakraborty, J. Chalopin, F. Foucaud, and Y. Vaxès.  Isometric path complexity of graphs.  In Jérôme Leroux, Sylvain Lombardy, and David Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France, volume 272 of LIPIcs, pages 32:1–32:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [11] D. Chakraborty, A. Dailly, S. Das, F. Foucaud, H. Gahlawat, and S. K. Ghosh.  Complexity and algorithms for ISOMETRIC PATH COVER on chordal graphs and beyond.  In 33rd International Symposium on Algorithms and Computation, ISAAC 2022, December 19-21, 2022, Seoul, Korea, volume 248 of LIPIcs, pages 12:1–12:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [12] D. Chakraborty, H. Gahlawat, and B. Roy.  Algorithms and complexity for geodetic sets on partial grids.  Theoretical Computer Science, 979:114217, 2023.
  * [13] J. Chalopin, V. Chepoi, F. F. Dragan, G. Ducoffe, A. Mohammed, and Y. Vaxès.  Fast approximation and exact computation of negative curvature parameters of graphs.  Discret. Comput. Geom., 65(3):856–892, 2021.
  * [14] V. Chepoi, F. F. Dragan, and Y. Vaxès.  Core congestion is inherent in hyperbolic networks.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2264–2279. SIAM, 2017.
  * [15] V. Chepoi, Feodor Dragan, Bertrand Estellon, Michel Habib, and Yann Vaxès.  Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs.  In Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 59–68, 2008.
  * [16] V. Chepoi, F.F. Dragan, Michel Habib, Yann Vaxès, and Hend Alrasheed.  Fast approximation of eccentricities and distances in hyperbolic graphs.  Journal of Graph Algorithms and Applications, 23(2):393–433, 2019\.
  * [17] V. Chepoi and B. Estellon.  Packing and covering $\delta$-hyperbolic spaces by balls.  In Moses Charikar, Klaus Jansen, Omer Reingold, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings, volume 4627 of Lecture Notes in Computer Science, pages 59–73. Springer, 2007.
  * [18] V. Chepoi, T. Fevat, E. Godard, and Y. Vaxès.  A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives.  Algorithmica, 62(1-2):146–168, 2012.
  * [19] M. de Berg and A. Khosravi.  Optimal binary space partitions in the plane.  In Computing and Combinatorics: 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings 16, pages 216–225. Springer, 2010.
  * [20] Y. Dourisboure and C. Gavoille.  Tree-decompositions with bags of small diameter.  Discrete Mathematics, 307(16):2008–2029, 2007.
  * [21] F. F. Dragan and G. Ducoffe.  $\alpha$${}_{\mbox{i}}$-metric graphs: Radius, diameter and all eccentricities.  CoRR, abs/2305.02545, 2023.
  * [22] F. F. Dragan and A. Leitert.  Minimum eccentricity shortest paths in some structured graph classes.  Journal of Graph Algorithms and Applications, 20(2):299–322, 2016\.
  * [23] F. F. Dragan and A. Leitert.  On the minimum eccentricity shortest path problem.  Theoretical Computer Science, 694:66–78, 2017.
  * [24] M. Dumas, F. Foucaud, A. Perez, and I. Todinca.  On graphs coverable by k shortest paths.  In 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248, pages 40–1, 2022.
  * [25] K. Edwards, W.S. Kennedy, and I. Saniee.  Fast approximation algorithms for p-centers in large $\delta$-hyperbolic graphs.  Algorithmica, 80(12):3889–3907, 2018.
  * [26] H. Fernau, F. Foucaud, K. Mann, U. Padariya, and KN R. Rao.  Parameterizing path partitions.  In International Conference on Algorithms and Complexity, pages 187–201. Springer, 2023.
  * [27] O. Gerstel and S. Zaks.  A new characterization of tree medians with applications to distributed sorting.  Networks, 24(1):23–29, 1994.
  * [28] M. Gromov.  Hyperbolic groups.  In Essays in group theory, pages 75–263. Springer, 1987.
  * [29] D.S. Hochbaum and D.B. Shmoys.  A best possible heuristic for the k-center problem.  Mathematics of operations research, 10(2):180–184, 1985.
  * [30] W.-L. Hsu and G.L. Nemhauser.  Easy and hard bottleneck location problems.  Discrete Applied Mathematics, 1(3):209–215, 1979.
  * [31] E.A. Jonckheere, P Lohsoonthorn, and F. Bonahon.  Scaled gromov hyperbolic graphs.  J. Graph Theory, 57(2):157–180, 2008.
  * [32] S. Kisfaludi-Bak, J. Masaříková, E.J. van Leeuwen, B. Walczak, and K. Węgrzycki.  Separator theorem and algorithms for planar hyperbolic graphs.  arXiv preprint arXiv:2310.11283, 2023.
  * [33] M. Kučera and O.j Suchỳ.  Minimum eccentricity shortest path problem with respect to structural parameters.  Algorithmica, 85(3):762–782, 2023.
  * [34] J. Łącki, B. Haeupler, C. Grunau, R. Jayaram, and V. Rozhoň.  Fully dynamic consistent k-center clustering.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3463–3484. SIAM, 2024.
  * [35] F. R. McMorris, H. M. Mulder, B. Novick, and R. C. Powers.  An ABC-problem for location and consensus functions on graphs.  Discrete Appl. Math., 207(1):15–28, 2016.
  * [36] F. R. McMorris, H. M. Mulder, and F. S. Roberts.  The median procedure in median graphs.  Discrete Appl. Math., 84(1-3):165–181, 1998.
  * [37] S. Micali and V.V. Vazirani.  An O ($\sqrt{|V|}$|E|) algoithm for finding maximum matching in general graphs.  In 21st Annual symposium on foundations of computer science (Sfcs 1980), pages 17–27. IEEE, 1980.
  * [38] A. O. Mohammed.  Slimness, Thinness and other Negative Curvature Parameters of Graphs.  PhD thesis, Kent State University, 2019.
  * [39] O. Narayan and I. Saniee.  Large-scale curvature of networks.  Phys. Rev. E, 84:066108, 2011.
  * [40] J. Plesník.  On the computational complexity of centers locating in a graph.  Aplikace matematiky, 25(6):445–452, 1980.
  * [41] B. C. Tansel, R. L. Francis, and T. J. Lowe.  Location on networks: A survey, i, II.  Manag. Sci., 29:482–511, 1983.
  * [42] H. Wang and J. Zhang.  An ${O}(n\log n)$-time algorithm for the $k$-center problem in trees.  SIAM Journal on Computing, 50(2):602–635, 2021.