# Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs

Feodor F Dragan, Guillaume Ducoffe, Heather M Guarnera

<figure><img src="image_1.png" /></figure>

## To cite this version:

Feodor F Dragan, Guillaume Ducoffe, Heather M Guarnera. Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs. Journal of Computer and System Sciences, 2025, 149, pp.103606. 10.1016/j.jcss.2024.103606. hal-04812612

HAL Id: hal-04812612

https://hal.science/hal-04812612v1

Submitted on 30 Nov 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs*

Feodor F. Dragan¹**, Guillaume Ducoffe²***, and Heather M. Guarnera³

¹ Computer Science Department, Kent State University, Kent, USA
[dragan@cs.kent.edu](mailto:dragan@cs.kent.edu)

² National Institute for Research and Development in Informatics and University of Bucharest, Bucureşti, România
[guillaume.ducoffe@ici.ro](mailto:guillaume.ducoffe@ici.ro)

³ Department of Mathematical and Computational Sciences, The College of Wooster,
Wooster, USA
[hguarnera@wooster.edu](mailto:hguarnera@wooster.edu)

**Abstract.** A graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. The class of Helly graphs is the discrete analogue of the class of hyperconvex metric spaces. We study diameter, radius and all eccentricity computations within the Helly graphs. Under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time on general graphs. In contrast to these negative results, it was recently shown that the radius and the diameter of an *n*-vertex *m*-edge Helly graph can be computed with high probability in $\mathcal{O}(m\sqrt{n})$ time (i.e., subquadratic in $n+m$). In this paper, we improve that result by presenting a deterministic $\mathcal{O}(m\sqrt{n})$-time algorithm which computes not only the radius and the diameter but also all vertex eccentricities in a Helly graph. Furthermore, we give a parameterized linear-time algorithm for this problem on Helly graphs, with the parameter being the Gromov hyperbolicity.

**Keywords:** Subquadratic Graph Algorithms, Eccentricities, Radius, Diameter, Hyperbolicity, Helly Graphs, Structural Properties

## 1 Introduction

Given an undirected unweighted graph $G = (V, E)$, the distance $d_G(u, v)$ between two vertices $u$ and $v$ is the minimum number of edges on any path connecting $u$ and $v$ in $G$. The eccentricity $e_G(u)$ of a vertex $u$ is the maximum distance from $u$ to any other vertex. The radius and the diameter of $G$, denoted by $rad(G)$

<footnote>* Results of this paper were partially presented at WADS 2021 [35].</footnote>

<footnote>** Corresponding author: Feodor F. Dragan, [dragan@cs.kent.edu](mailto:dragan@cs.kent.edu)</footnote>

<footnote>*** This work was supported by project PN 19 37 04 01 "New solutions for complex problems in current ICT research fields based on modelling and optimization", funded by the Romanian Core Program of the Ministry of Research and Innovation (MCI), 2019-2022</footnote>
and *diam*(G), are the smallest and the largest eccentricities of vertices in G, respectively. A vertex with eccentricity equal to *rad*(G) is called a central vertex of G. We are interested in the fundamental problems of finding a central vertex and of computing the diameter and the radius of a graph. The problem of finding a central vertex of a graph is one of the most famous facility location problems in Operation Research and in Location Science. The diameter and radius of a graph play an important role in the design and analysis of networks in a variety of networking environments like social networks, communication networks, electric power grids, and transportation networks. A naive algorithm which runs breadth-first-search from each vertex to compute its eccentricity and then (in order to compute the radius, the diameter and a central vertex) picks the smallest and the largest eccentricities and a vertex with smallest eccentricity has running time *O*(nm) on an *n*-vertex *m*-edge graph. Interestingly, this naive algorithm is conditionally optimal for general graphs as well as for some restricted families of graphs [1, 10, 24, 70] since, under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time (i.e., in *O*(n-am), for some positive a, b such that a+b < 2) on those graphs. Already for split graphs (a subclass of chordal graphs), computing the diameter is roughly equivalent to DISJOINT SETS, a.k.a., the monochromatic ORTHOGONAL VECTOR (OV) problem [20]. Under the Strong Exponential-Time Hypothesis (SETH), we cannot solve DISJOINT SETS in truly subquadratic time [73], and so neither we can compute the diameter of split graphs in truly subquadratic time [10].

In a quest to break this quadratic barrier (in the size *n*+*m* of the input), there has been a long line of work presenting more efficient algorithms for computing the diameter and/or the radius on some special graph classes, by exploiting their geometric and tree-like representations and/or some forbidden pattern (e.g., excluding a minor, or a family of induced subgraphs). For example, although the diameter of a split graph can unlikely be computed in subquadratic time, there is an elegant linear-time algorithm for computing the radius and a central vertex of a chordal graph [21]. Efficient algorithms for computing the diameter and/or the radius or finding a central vertex are also known for interval graphs [43, 67], AT-free graphs [50], directed path graphs [25], distance-hereditary graphs [27, 33, 37, 42], strongly chordal graphs [29], dually chordal graphs [11, 32], chordal bipartite graphs [48], outerplanar graphs [56], planar graphs [15, 58], graphs with bounded clique-width [27, 51], graphs with bounded tree-width [1, 13, 54] and, more generally, *H*-minor free graphs and graphs of bounded (distance) VC-dimension [54]. See also [23, 24, 46, 49, 53, 55] for other examples.

We here study the *Helly graphs* as a broad generalization of dually chordal graphs which in turn contain all interval graphs, directed path graphs and strongly chordal graphs. Recall that a graph is Helly if every family of pairwise intersecting balls has a non-empty common intersection. This latter property on the balls will be simply referred to as the Helly property in what follows. Helly graphs have unbounded tree-width and unbounded clique-width, they do not exclude any fixed minor and they cannot be characterized via some forbidden structures. They are sometimes called absolute retracts or disk-Helly graphs by
opposition to other Helly-type properties on graphs [28]. The Helly graphs are
well studied in Metric Graph Theory. E.g., see the survey [5] and the papers
cited therein. This is partly because every graph is an isometric subgraph of
some Helly graph, thereby making of the latter the discrete equivalent of hy-
perconvex metric spaces [45, 61]. A minimal by inclusion Helly graph H which
contains a given graph G as an isometric subgraph is unique and called the in-
jective hull [61] or the tight span [45] of G. It is known that the injective hull
H of a graph G preserves vertex eccentricities (that is, e_G(v) = e_H(v) for each
v ∈ V(G)) [39]. So, efficient algorithms for computing eccentricities in Helly
graphs can be used to compute eccentricities in other graph classes, provided
that injective hulls of those graphs can efficiently be computed. For instance, it
was shown in [60] that the injective hull of a distance-hereditary graph can be
computed in linear time. Combined with our results in this paper, one obtains
a new linear-time algorithm for computing all eccentricities in this graph class.

Polynomial-time recognition algorithms for the Helly graphs were presented in [6, 29, 65]. Several structural properties of these graphs were also identified in [6–8, 19, 29–31, 34, 36, 68, 69]. Although the best recognition algorithm has complexity $O(m^2)$ for an $m$-edge Helly graph, many interesting subclasses of Helly graphs, like king graphs, dually chordal graphs, interval graphs and others, can be recognized in linear time. The dually chordal graphs are exactly the Helly graphs in which the intersection graph of balls is chordal, and they were studied independently from the general Helly graphs [11, 12, 44, 32, 34, 72]. In particular, unlike for the general Helly graphs, the domination problem is polynomial-time solvable on dually chordal graphs [44]. The diameter, the radius and a central vertex of a dually chordal graph can be found in linear time (see [11, 44, 32]), that is optimal. However, it was open until recently whether there are truly subquadratic-time algorithms for these problems on general Helly graphs. First such algorithms were recently presented in [52] for computing both the radius and the diameter and in [47] for finding a central vertex. Those algorithms are randomized and run, with high probability, in $\tilde{O}(m\sqrt{n})$ time on a given $n$-vertex $m$-edge Helly graph (i.e., subquadratic in $n+m$). They make use of the Helly property and of the unimodality of the eccentricity function in Helly graphs [30]: every vertex of locally minimum eccentricity is a central vertex. In [52], a linear-time algorithm for computing all eccentricities in $C_4$-free Helly graphs was also presented. The $C_4$-free Helly graphs are exactly the Helly graphs whose balls are convex. They properly include strongly chordal graphs as well as bridged Helly graphs and hereditary Helly graphs [52].

**Our Contribution.** We improve those results from [52] and [47] by presenting a deterministic $O(m\sqrt{n})$ time algorithm which computes not only the radius and the diameter but also all vertex eccentricities in an $n$-vertex $m$-edge Helly graph. No efficient algorithm (deterministic or probabilistic) existed for computing all eccentricities in Helly graphs until this paper. Our probabilistic $\tilde{O}(m\sqrt{n})$ time algorithms from [52, 47] can compute only the diameter, the radius and one central vertex. As in the previous papers [52, 47], here we use unimodality of the eccentricity function in Helly graphs in order to design local-search algorithms.
Our previous (probabilistic) strategy of choosing the starting point of a local search and upper bounding the number of steps by $\tilde{O}(\sqrt{n})$ was using some general properties of random sets/$\epsilon$-nets on general graphs (not just on Helly graphs). By contrast, we present in this paper a deterministic way to achieve the same performance (even better, at most $\sqrt{n}$ steps of local search) by exploiting new structural and metric properties of Helly graphs. In particular, unlike prior works we are also able to explain when one can do even better than $\sqrt{n}$ steps, using hyperbolicity.

This is our first main result in the paper. Being able to efficiently compute all vertex eccentricities is of great importance. For example, in the analysis of social networks (e.g., citation networks or recommendation networks), biological systems (e.g., protein interaction networks), computer networks (e.g., the Internet or peer-to-peer networks), transportation networks (e.g., public transportation or road networks), etc., the eccentricity $e_G(v)$ of a vertex $v$ is used to measure its importance in the network: the *eccentricity centrality index of* $v$ [64] is defined as
$$ = \frac{1}{e_G(v)} $$

Our second main result is a parameterized *linear-time* algorithm for computing all vertex eccentricities in Helly graphs, with the parameter being the Gromov hyperbolicity $\delta$, as defined by the following four point condition. The hyperbolicity of a graph $G$ [59] is the smallest half-integer $\delta \ge 0$ such that, for any four vertices $u, v, w, x$, the two largest of the three distance sums $d(u, v) + d(w, x)$, $d(u, w) + d(v, x)$, $d(u, x) + d(v, w)$ differ by at most $2\delta$. In this case we say that $G$ is $\delta$-hyperbolic. As the tree-width of a graph measures its combinatorial tree-likeness, so does the hyperbolicity of a graph measure its metric tree-likeness. In other words, the smaller the hyperbolicity $\delta$ of $G$ is, the closer $G$ is to a tree metrically. The hyperbolicity of an $n$-vertex graph can be computed in polynomial-time (e.g., in $O(n^{3.69})$ time [57]), however it is unlikely that it can be done in subquadratic time [10, 26, 57]. A 2-approximation of hyperbolicity can be computed in $O(n^{2.69})$ time [57] and an 8-approximation can be computed in $O(n^2)$ time [16] (assuming that the input is the distance matrix of the graph). Graph hyperbolicity has attracted attention recently due to the empirical evidence that it takes small values in many real-world networks, such as biological networks, social networks, Internet application networks, and collaboration networks, to name a few (see, e.g., [2, 3, 9, 62, 66, 71]). Furthermore, many special graph classes (e.g., interval graphs, chordal graphs, dually chordal graphs, AT-free graphs, weakly chordal graphs and many others) have constant hyperbolicity [2, 4, 14, 22, 36, 41, 63, 74]. In fact, the dually chordal graphs and the $C_4$-free Helly graphs are known to be proper subclasses of the 1-hyperbolic Helly graphs (this follows from results in [12, 36]). Notice also that any graph is $\delta$-hyperbolic for some $\delta \le diam(G)/2$.

We show that the radius and a central vertex of an $m$-edge Helly graph $G$ with hyperbolicity $\delta$ can be computed in $O(\delta m)$ time and that all vertex eccentricities in $G$ can be computed in $O(\delta^2 m \log \delta)$ time, even if $\delta$ is not known to us. If either $\delta$ or a constant approximation of it is known, then the running time of our algorithm can be lowered to $O(\delta^2 m)$. Thus, for Helly graphs with
constant hyperbolicity, all vertex eccentricities can be computed in linear time. As a byproduct, we get a linear time algorithm for computing all eccentricities in $C_4$-free Helly graphs as well as in dually chordal graphs, generalizing known results from [11, 32, 52]. Previously, for dually chordal graphs, it was only known that a central vertex can be found in linear time [11, 32]. Notice that the diameter problem can unlikely be solved in truly subquadratic time in general 1-hyperbolic graphs and that the radius problem can unlikely be solved in truly subquadratic time in general 2-hyperbolic graphs [24]. For general $\delta$-hyperbolic graphs, there are only additive $O(\delta)$-approximations of the diameter and the radius, that can be computed in linear time [22, 38, 40].

To show our more general results, additionally to the unimodality of the eccentricity function in Helly graphs, we rely on new structural properties obtained for this class. It turns out that the hyperbolicity of a Helly graph $G$ is governed by the size of a largest isometric rectilinear grid in $G$. As a consequence, the hyperbolicity of an $n$-vertex Helly graph is at most $\sqrt{n}+1$ and the diameter of the center $C(G)$ of $G$ is at most $2\sqrt{n}+3$, where $C(G) := \{v \in V : e_G(v) = \text{rad}(G)\}$. These properties, along with others, play a crucial role in efficient computations of all eccentricities in Helly graphs. We also give new characterizations of the class of Helly graphs. Among others, we show that the Helly property for balls of equal radii implies the Helly property for balls with variable radii. It would be interesting to know whether a similar result holds for all (discrete) metric spaces. We are not aware of such a general result.

**Notations.** Recall that $d_G(u, v)$ denotes the distance between vertices $u$ and $v$ in $G = (V, E)$. Let $n = |V|$ be the number of vertices and $m = |E|$ be the number of edges in $G$. The ball of radius $r$ and center $v$ is defined as $\{u \in V : d_G(u, v) \le r\}$, and denoted by $N_G^r[v]$. Sometimes, $N_G^r[S]$ is called the $r$-neighborhood of $v$. In particular, $N_G[v] := N_G^1[v]$ and $N_G(v) := N_G[v] \setminus \{v\}$ denote the closed and open neighbourhoods of a vertex $v$, respectively. More generally, for any vertex-subset $S$ and a vertex $u$, we define $d_G(u, S) := \min_{v \in S} d_G(u, v)$, $N_G^r[S] := \bigcup_{v \in S} N_G^r[v]$, $N_G[S] := N_G^1[S]$ and $N_G(S) := N_G[S] \setminus S$. The metric projection of a vertex $u$ on $S$, denoted by $\text{Pr}_G(u, S)$, is defined as $\{v \in S : d_G(u, v) = d_G(u, S)\}$. The metric interval $I_G(u, v)$ between $u$ and $v$ is $\{w \in V : d_G(u, w) + d_G(w, v) = d_G(u, v)\}$. For any $k \le d_G(u, v)$, we can also define the slice $L(u, k, v) := \{w \in I_G(u, v) : d_G(u, w) = k\}$. Recall that the eccentricity of a vertex $u$ is defined as $\max_{v \in V} d_G(u, v)$ and denoted by $e_G(u)$. Note that we will omit the subscript if the graph $G$ is clear from the context. The radius and the diameter of a graph $G$ are denoted by $\text{rad}(G)$ and $\text{diam}(G)$, respectively. A vertex $c$ is called central in $G$ if $e_G(c) = \text{rad}(G)$. The set of all central vertices of $G$ is denoted by $C(G) := \{v \in V : e_G(v) = \text{rad}(G)\}$ and called the center of $G$. The eccentricity function $e_G(v)$ of a graph $G$ is said to be *unimodal*, if for every non-central vertex $v$ of $G$ there is a neighbor $u \in N_G(v)$ such that $e_G(u) < e_G(v)$ (that is, every local minimum of the eccentricity function is a global minimum). Recall also that a vertex set $S \subseteq V$ is called convex in $G$ if, for every pair of vertices $x, y \in S$, all shortest paths connecting them are contained in $S$ (i.e., $I_G(x, y) \subseteq S$). For $\beta \ge 0$, we say that $S$ is a $\beta$-pseudoconvex [38] if, for every pair of
vertices $x, y \in S$, any vertex $z \in I_G(x, y) \setminus S$ satisfies $\min\{d_G(z, x), d_G(z, y)\} \le \beta$. A subgraph $H$ of $G$ is called isometric (or distance-preserving) if, for every pair of vertices $x, y$ of $H$, $d_G(x, y) = d_H(x, y)$.

## 2 Characterizations of Helly graphs and hyperbolicity in Helly graphs

Here we demonstrate that for Helly graphs, having a constant hyperbolicity is equivalent to the following properties: having $\beta$-pseudoconvexity of balls with a constant $\beta$, or having the diameter of the center bounded by a constant for all subsets of vertices, or not having a large $(\gamma \times \gamma)$ rectilinear grid as an isometric subgraph. These results generalize some known results from [17, 18, 22, 36, 38].

First we give new characterizations of Helly graphs through a formula for the eccentricity function and relations between diameter and radius for all subsets of vertices. For this we need to generalize our basic notations. Define for any set $M \subseteq V$ and any vertex $v \in V$ the eccentricity of $v$ in $G$ with respect to $M$ as follows:

$$e_M(v) = \max_{u \in M} d_G(u, v).$$

Let $diam_M(G) = \max_{v \in M} e_M(v)$, $rad_M(G) = \min_{v \in V} e_M(v)$, $C_M(G) = \{v \in V : e_M(v) = rad_M(G)\}$. When $M = V$, these agree with earlier definitions.

**Theorem 1.** For a graph $G$ the following statements are equivalent:

(1) $G$ is Helly;

(2) the eccentricity function $e_M(\cdot)$ is unimodal for every set $M \subseteq V$;

(3) $e_M(v) = d_G(v, C_M(G)) + rad_M(G)$ holds for every set $M \subseteq V$ and every vertex $v \in V$;

(4) $2rad_M(G) - 1 \le diam_M(G) \le 2rad_M(G)$ holds for every set $M \subseteq V$;

(5) $rad_M(G) = \lfloor diam_M(G) + 1 \rfloor$ holds for every set $M \subseteq V$.

*Proof.* The equivalence (1) $\Leftrightarrow$ (2) was proven in [29, 30]. It was also shown in [29] that (2) and (3) are equivalent for $M = V$. Here, we complete the proof of all equivalencies. We will show (2) $\Leftrightarrow$ (3), when one considers any set $M \subseteq V$, and (1) $\Rightarrow$ (4) $\Rightarrow$ (5) $\Rightarrow$ (1).

(2) $\Rightarrow$ (3): Let $M$ be any subset of $V$. We will prove the formula in (3) by induction on $k = e_M(v) - rad_M(G)$. If $k = 0$ then $e_M(v) = rad_M(G)$, i.e., $v \in C_M(G)$, and the formula is trivially correct. Consider now a vertex $v$ with $e_M(v) > rad_M(G)$. By the triangle inequality, $e_M(v) \le d_G(v, C_M(G)) + rad_M(G)$ always holds. As the eccentricity function $e_M(\cdot)$ is unimodal, there is a neighbor $u$ of $v$ with $e_M(v) > e_M(u)$. By induction hypothesis, $e_M(u) = d_G(u, C_M(G)) + rad_M(G)$. Hence, by the triangle inequality, $e_M(v) \ge e_M(u) + 1 = d_G(u, C_M(G)) + rad_M(G) + 1 \ge d_G(v, C_M(G)) + rad_M(G)$. Combining both inequalities, we get $e_M(v) = d_G(v, C_M(G)) + rad_M(G)$.

(3) $\Rightarrow$ (2): Let $M$ be any subset of $V$ and $v$ be an arbitrary vertex of $G$ with $e_M(v) > rad_M(G)$. Let also $c_v$ be a vertex of $C_M(G)$ closest to $v$ and $u$ be
a neighbor of $v$ on a shortest path from $v$ to $c_v$. We have $e_M(v) = d_G(v, c_v) + rad_M(G) = 1+d_G(u, c_v)+rad_M(G) \ge 1+d_G(u, C_M(G))+rad_M(G) = 1+e_M(u)$. In particular, $e_M(v) > e_M(u)$.

(1)⇒(4): It is clear that $diam_M(G) \le 2rad_M(G)$ holds for every graph $G$ and every set $M \subseteq V$ (by the triangle inequality). Assume now that for a subset $M$ of $V$, $diam_M(G) \le 2rad_M(G) - 2$ holds. For every vertex $v$ in $M$, consider a ball centered at $v$ and with radius $rad_M(G) - 1$. All these balls pairwise intersect as $diam_M(G) \le 2rad_M(G) - 2$. By the Helly property, there must exist a vertex $c$ in $G$ such that $d_G(c, v) \le rad_M(G) - 1$ for every $v \in M$. The latter implies that $e_M(c) \le rad_M(G) - 1$, giving a contradiction.

(4)⇒(5): It is straightforward.

(5)⇒(1): We know that a graph $G$ is Helly if and only if the family of unit balls of $G$ has the Helly property and for any three vertices $x, y, v$ with $d_G(x, y) \le 2$ and $d_G(x, v) = d_G(y, v) = k \ge 2$ there exists a common neighbor $u$ of $x$ and $y$ such that $d_G(v, u) = k - 1$ (see [6, 29, 30]).

Consider in $G$ a family $\mathcal{F}$ of pairwise intersecting unit balls with centers at vertices $v_1, \dots, v_q$. Define $M = \{v_1, \dots, v_q\}$. As the balls pairwise intersect, $d_G(v_i, v_j) \le 2$ for each $i, j \in \{1, \dots, q\}$. Hence, $diam_M(G) \le 2$ and therefore $rad_M(G) = \lfloor \frac{diam_M(G)+1}{2} \rfloor \le 1$. The latter implies the existence of a vertex $c$ in $G$ with $d_G(c, v_i) \le 1$ for all $i \in \{1, \dots, q\}$. Necessarily, $c$ belongs to all unit balls from $\mathcal{F}$. In other words, the family of unit balls of $G$ has the Helly property.

<figure><img src="image_3.png" /><figcaption>Fig. 1: An illustration to the proof of (5)⇒(1) from Theorem 1, in the case of different values of $k = d_G(x, v) = d_G(y, v)$.</figcaption></figure>

Let $x, y, v$ be any three vertices of $G$ with $d_G(x, y) \le 2$ and $d_G(x, v) = d_G(y, v) = k \ge 2$. We will show by induction on $k$ that there exists a common neighbor $u$ of $x$ and $y$ such that $d_G(v, u) = k - 1$. If $k = 2$ then the existence of $u$ follows from the Helly property for the family of unit balls of $G$.
Assume now that $k > 2$ and first consider the case when $k$ is even, say $k = 2\ell$ (see Fig. 1(a)). Let $M = \{x, y, v\}$. As $k > 2$, $diam_M(G) = k = 2\ell$ and therefore $\mathrm{rad}_M(G) = \lfloor \frac{\mathrm{diam}_M(G)+1}{2} \rfloor = \ell$. Hence, there is a vertex $c$ in $G$ such that $d_G(c, v) = d_G(c, x) = d_G(c, y) = \ell$. Notice that $\ell \ge 2$. By induction, there must exist a common neighbor $u$ of $x$ and $y$ such that $d_G(c, u) = \ell - 1$. Necessarily, $d_G(u, v) = 2\ell - 1 = k - 1$. Assume now that $k$ is odd, say $k = 2\ell + 1$. If $k \ge 5$ then consider a neighbor $x'$ of $x$ on a shortest path from $x$ to $v$ and a neighbor $y'$ of $y$ on a shortest path from $y$ to $v$ (see Fig. 1(b)). Let $M = \{x', y', v\}$. As $d_G(x', v) = d_G(y', v) = k - 1 \ge 4$ and $d_G(x', y') \le 4$, $\mathrm{diam}_M(G) = k - 1 = 2\ell$ and therefore $\mathrm{rad}_M(G) = \lfloor \frac{\mathrm{diam}_M(G)+1}{2} \rfloor = \ell$. Hence, there is a vertex $c$ in $G$ such that $d_G(c, v) = d_G(c, x') = d_G(c, y') = \ell$. Since $d_G(c, x) = d_G(c, y) = \ell + 1$, by induction, there must exist a common neighbor $u$ of $x$ and $y$ such that $d_G(c, u) = \ell$. Necessarily, $d_G(u, v) = 2\ell = k - 1$.

It remains to consider the case when $k = 3$ (see Fig. 1(c)). Let $M = I_G(x, v) \cup I_G(y, v)$. We have $3 \le diam_M(G) \le 4$ and therefore $\mathrm{rad}_M(G) = 2$. The latter implies the existence of a vertex $c$ in $G$ such that $d_G(c, w) \le 2$ for all $w \in M$. Consider a neighbor $v_x$ of $v$ on a shortest path from $v$ to $x$ and a neighbor $v_y$ of $v$ on a shortest path from $v$ to $y$. Since $d_G(c, v_x) \le 2$, $d_G(c, x) \le 2$ and $d_G(x, v_x) = 2$, the three unit balls centered at vertices $x, c, v_x$ pairwise intersect. By the Helly property for unit balls, there must exist a vertex $x'$ in $G$ which is adjacent to $x$ and $v_x$ and at distance at most 1 from $c$. By symmetry, there exists also a vertex $y'$ in $G$ which is adjacent to $y$ and $v_y$ and at distance at most 1 from $c$. Since $d_G(v, x') = d_G(v, y') = 2$ and $d_G(x', y') \le d_G(c, x') + d_G(c, y') \le 2$, by induction, there is a vertex $v'$ in $G$ adjacent to all $x', y', v$. Applying again the induction hypothesis to $v', x, y$, we get a vertex $u$ in $G$ which is adjacent to all $v', x, y$ and hence at distance 2 from $v$. This concludes the proof. $\square$

The equivalence between (1) and (5) can be rephrased as follows.

**Corollary 1.** For every graph $G = (V, E)$, the family of all balls $\{N_G^r[v] : v \in V, r \in \mathbb{N}\}$ of $G$ has the Helly property if and only if the family of $k$-neighborhoods $\{N_G^k[v] : v \in V\}$ of $G$ has the Helly property for every natural number $k$.

That is, the Helly property for balls of equal radii implies the Helly property for balls with variable radii. It would be interesting to know whether a similar result holds for all (discrete) metric spaces. We are not aware of such a general result and did not find its analog in the literature.

*Proof.* It is sufficient to prove that if the family of $k$-neighborhoods $\{N_G^k[v] : v \in V\}$ of $G$ has the Helly property for every natural number $k$, then $G$ satisfies the condition (5) of Theorem 1.

Consider an arbitrary set $M \subseteq V$. Denote $k := \lfloor \frac{\mathrm{diam}_M(G)+1}{2} \rfloor$. Since $d_G(x, y) \le diam_M(G)$ for every pair $x, y$ of vertices from $M$, the family of $k$-neighborhoods $\{N_G^k[v] : v \in M\}$ of $G$ consists of pairwise intersecting sets. By the Helly property, there is a vertex $c \in V$ which belongs to all those $k$-neighborhoods. Necessarily, $d_G(c, v) \le k$ holds for every $v \in M$.
Hence, $rad_M(G) \le k = \lfloor \frac{\mathrm{diam}_M(G)+1}{2} \rfloor$. As $\mathrm{diam}_M(G) \le 2rad_M(G)$, we get $rad_M(G) = \lfloor \frac{\mathrm{diam}_M(G)+1}{2} \rfloor$. $\square$

We will also need the following lemma from [29].

**Lemma 1.** [29] For every Helly graph $G = (V, E)$ and every set $M \subseteq V$, the graph induced by the center $C_M(G)$ is Helly and it is an isometric (and hence connected) subgraph of $G$.

Given this lemma, it will be convenient to denote by $C_M(G)$ not only the set of central vertices but also the subgraph of $G$ induced by this set. Then, $\mathrm{diam}(C_M(G))$ denotes the diameter of this graph ($\mathrm{diam}(C_M(G)) = \mathrm{diam}_{C_M(G)}(G)$ by this isometricity).

Let $\delta(G)$ be the smallest half-integer $\delta \ge 0$ such that $G$ is $\delta$-hyperbolic. Let $\gamma(G)$ be the largest integer $\gamma \ge 0$ such that $G$ has a $(\gamma \times \gamma)$ rectilinear grid as an isometric subgraph. Let $\beta(G)$ be the smallest integer $\beta \ge 0$ such that all balls in $G$ are $\beta$-pseudoconvex. Finally, let $\kappa(G)$ be the smallest integer $\kappa \ge 0$ such that $\mathrm{diam}(C_M(G)) \le \kappa$ for every set $M \subseteq V$.

**Theorem 2.** For every Helly graph $G$, a constant bound on one parameter from $\{\delta(G), \gamma(G), \beta(G), \kappa(G)\}$ implies a constant bound on all others.

*Proof.* Let $\delta := \delta(G)$, $\gamma := \gamma(G)$, $\beta := \beta(G)$, $\kappa := \kappa(G)$. We will show that the following inequalities are true using a few claims:

$$ \kappa \le \min\{2\delta + 1, 2\gamma + 3, \max\{3, 2\beta + 1\}\}, $$

$$ \beta \le \min\{\max\{0, 2\delta - 1\}, 2\gamma + 1, \kappa + 1\}, $$

$$ \gamma \le \min\{\delta, \beta, \kappa/2\}, $$

$$ \delta \le \min\{\gamma, \beta, \kappa/2\} + 1. $$

**Claim 1** If $G$ is $\delta$-hyperbolic Helly, then $\mathrm{diam}(C_M(G)) \le 2\delta + 1$ and $\mathrm{rad}(C_M(G)) \le \delta + 1$ for every set $M \subseteq V$. In particular, $\kappa \le 2\delta + 1$.

Let $M$ be an arbitrary subset of $V$. Let also $d_G(x, y) = \mathrm{diam}_M(G)$ for $x, y \in M$ and let $d_G(u, v) = \mathrm{diam}(C_M(G))$ for $u, v \in C_M(G)$. As $G$ is Helly, $d_G(x, y) \ge 2\mathrm{rad}_M(G) - 1$. We consider the following distance sums: $d_G(x, y) + d_G(u, v) \ge 2\mathrm{rad}_M(G) - 1 + \mathrm{diam}(C_M(G))$, $d_G(x, u) + d_G(v, y) \le 2\mathrm{rad}_M(G)$, and $d_G(x, v) + d_G(y, u) \le 2\mathrm{rad}_M(G)$. If $d_G(x, y) + d_G(u, v)$ is not the largest of the three sums, then $\mathrm{diam}(C_M(G)) \le 1$. Otherwise, by the four point condition, $\mathrm{diam}(C_M(G)) \le 2\delta + 1$. Consider the pairwise intersecting balls $N_G^{\mathrm{rad}_M(G)}[v]$ for all $v \in M$ and $N_G^{\delta+1}[u]$ for all $u \in C_M(G)$. By the Helly property, there is a vertex $c \in C_M(G)$ such that $N_G^{\delta+1}[c] \supseteq C_M(G)$. As $C_M(G)$ is isometric for any Helly graph (see Lemma 1), the diameter and radius of $C_M(G)$ are realized by paths fully contained in $C_M(G)$.
**Claim 2** If $G$ is $\delta$-hyperbolic, then any ball of $G$ is $(2\delta - 1)$-pseudoconvex, when $\delta > 0$, and is convex, when $0 \le \delta \le 1/2$. In particular, $\beta \le \max\{0, 2\delta - 1\}$.

Consider a ball $N_G^r[v]$ centered at a vertex $v \in V$ and with radius $r$. Let $x, y \in N_G^r[v]$ and let $u \in I_G(x, y)$ be a vertex which is not contained in $N_G^r[v]$. By contradiction, assume that $d_G(u, x) \ge 2\delta$ and $d_G(u, y) \ge 2\delta$. Since $u \notin N_G^r[v]$, $d_G(u, v) > r$. Consider the following distance sums: $d_G(x, y) + d_G(u, v) = d_G(x, u) + d_G(u, y) + d_G(u, v) > d_G(x, u) + d_G(u, y) + r$, $d_G(x, u) + d_G(u, y) \le d_G(x, u) + r$, and $d_G(x, v) + d_G(y, u) \le r + d_G(y, u)$. Clearly, $d_G(x, y) + d_G(u, v)$ is the largest sum. Without loss of generality, assume that $d_G(x, u) + d_G(v, y)$ is the second largest sum. By the four point condition, $2\delta \ge d_G(x, y) + d_G(u, v) - d_G(x, u) - d_G(v, y) = d_G(u, y) + d_G(u, v) - d_G(v, y) > 2\delta + r - r = 2\delta$, which is not possible.

**Claim 3** If $G$ is a Helly graph whose all balls are $\beta$-pseudoconvex, then for every set $M \subseteq V$, $\text{diam}(C_M(G)) \le 3$, when $\beta = 0$, and $\text{diam}(C_M(G)) \le 2\beta + 1$, when $\beta > 0$. In particular, $\kappa \le \max\{3, 2\beta + 1\}$.

Let $M$ be an arbitrary subset of $V$. Let also $d_G(x, y) = \text{diam}_M(G)$ for $x, y \in M$ and let $d_G(u, v) = \text{diam}(C_M(G))$ for $u, v \in C_M(G)$. It is known from [29] that if balls in a Helly graph $G$ are convex (i.e., $\beta = 0$) then $\text{diam}(C_M(G)) \le 3$. Let now $\beta \ge 1$ and assume, by way of contradiction, that $d_G(u, v) \ge 2\beta + 2$. As $G$ is Helly, $d_G(x, y) \ge 2\text{rad}_M(G) - 1$. Set $r := \text{rad}_M(G)$. Note that, since we always have $\text{diam}(C_M(G)) \le 2r$ and we further assume $\text{diam}(C_M(G)) \ge 2\beta + 2$, $r \ge 2$. In particular, $2r - 1 \ge r + 1$. Consider the following four balls: $N_G^{r+1}[y]$, $N_G^{d_G(x,y)-r-1}[x]$, $N_G^{\beta+1}[u]$ and $N_G^{d_G(u,v)-\beta-1}[v]$. We show that they pairwise intersect. Clearly, $N_G^{r+1}[y] \cap N_G^{d_G(x,y)-r-1}[x] \ne \emptyset$ and $N_G^{\beta+1}[u] \cap N_G^{d_G(u,v)-\beta-1}[v] \ne \emptyset$. Furthermore, since $d_G(u, x)$, $d_G(u, y)$, $d_G(v, x)$ and $d_G(v, y)$ are at most $r$, the ball $N_G^{r+1}[y]$ intersects both $N_G^{\beta+1}[u]$ and $N_G^{d_G(u,v)-\beta-1}[v]$. As $(d_G(x, y) - r - 1) + (\beta + 1) \ge 2r - 1 - r - 1 + \beta + 1 = r + \beta - 1 \ge r \ge d_G(u, x)$, the balls $N_G^{d_G(x,y)-r-1}[x]$ and $N_G^{\beta+1}[u]$ also intersect. Similarly, the balls $N_G^{d_G(x,y)-r-1}[x]$ and $N_G^{d_G(u,v)-\beta-1}[v]$ must intersect as $d_G(u, v) - \beta - 1 \ge \beta + 1$. As all four balls pairwise intersect, by the Helly property, there must exist a vertex $c$ in $G$ such that $d_G(u, v) = d_G(u, c) + d_G(c, v)$ (i.e., $c \in I_G(u, v)$) and $d_G(y, c) = r + 1$, $d_G(x, c) = d_G(x, y) - r - 1$. The latter contradicts with the $\beta$-pseudoconvexity of the ball $N_G^r[y]$ as $u, v$ belong to that ball and $c \in I_G(u, v)$ with $\min\{d_G(c, u), d_G(c, v)\} \ge \beta + 1$ is not in $N_G^r[y]$.

**Claim 4** For every graph, $\gamma \le \min\{\delta, \beta, \kappa/2\}$.

Consider an isometric $(\gamma \times \gamma)$ rectilinear grid in $G$ and let $a, b, c, d$ be the corner vertices of that grid listed in counterclockwise order. The hyperbolicity of $G$ is at least the hyperbolicity of the quadruple $a, b, c, d$ which is exactly $(d_G(a, c) + d_G(b, d)) - (d_G(a, b) + d_G(c, d)) = \frac{1}{2}((2\gamma + 2\delta) - (\gamma + \delta)) = \gamma$. Hence, $\gamma \le \delta$. For the ball $N_G^\gamma[a]$, we get: $b, d \in N_G^\gamma[a]$, $c \notin N_G^\gamma[a]$, and $c$ is on a shortest path between $b$ and $d$ with $d_G(c, b) = d_G(c, d) = \gamma$. Hence, $\gamma \le \beta$. Let now $M = \{a, c\}$.
Then, $diam_M(G) = 2\gamma$ and $rad_M(G) = \gamma$ and both b and d are in $C_M(G)$. As $d_G(b, d) = 2\gamma$, $diam(C_M(G)) \ge 2\gamma$, giving $\kappa \ge diam(C_M(G)) \ge 2\gamma$.

**Claim 5** For every Helly graph, $\delta \le \gamma + 1$.

This claim follows from a result in [36]. Let the hyperbolicity of $G$ be $\delta$. According to [36, Lemma 8], if $\delta$ is an integer, then $G$ has an isometric subgraph (named $H_1^\delta$ in [36]), which contains an isometric $(\delta \times \delta)$ rectilinear grid, or an isometric subgraph (named $H_3^{\delta-1}$ in [36]), which contains an isometric $((\delta - 1) \times (\delta - 1))$ rectilinear grid. Furthermore, if $\delta$ is a half-integer, then $G$ has an isometric subgraph (named $H_2^{\delta-1/2}$ in [36]), which contains an isometric $((\delta - 1/2) \times (\delta - 1/2))$ rectilinear grid. Thus, in both cases (whether $\delta$ is a half-integer or an integer), $\gamma \ge \delta - 1$ holds.

**Claim 6** For every Helly graph, $\delta \le \min\{\beta, \kappa/2\} + 1$, $\beta \le \min\{\kappa, 2\gamma\} + 1$, $\kappa \le 2\gamma + 3$.

These remaining inequalities follow from the previous claims. We have

$$\delta \le \gamma + 1 \le \beta + 1,$$

$$\delta \le \gamma + 1 \le \kappa/2 + 1,$$

$$\beta \le \max\{0, 2\delta - 1\} \le \max\{0, \kappa + 1\} = \kappa + 1,$$

$$\beta \le \max\{0, 2\delta - 1\} \le 2\gamma + 1,$$

$$\kappa \le 2\delta + 1 \le 2\gamma + 3.$$

This concludes the proof of the theorem. $\square$

The following corollaries of Theorem 2 will play an important role in efficient computations of all eccentricities of a Helly graph. Corollary 2 gives a sublinear bound on the hyperbolicity of a Helly graph. Corollary 3 gives a sublinear bound on the diameter of the center of a Helly graph.

**Corollary 2.** The hyperbolicity of an $n$-vertex Helly graph $G$ is at most $\sqrt{n}+1$.

*Proof.* If $G$ is $\delta$-hyperbolic then, by Claim 5, $G$ contains an isometric rectilinear grid of side-length $\ge \delta - 1$. In particular, $(\delta - 1)^2 \le n$. $\square$

**Corollary 3.** For any $n$-vertex Helly graph $G$, we have $diam(C(G)) \le 2\sqrt{n}+3$.

*Proof.* We apply Corollary 2 and Claim 1 (with $M = V$). Thus, for a $\delta$-hyperbolic Helly graph $G$, $diam(C(G)) \le 2\delta + 1 \le 2\sqrt{n} + 3$. $\square$
### 3 All eccentricities in Helly graphs

It is known that the radius (see [52]) and a central vertex (see [47]) of an $n$-vertex $m$-edge Helly graph can be computed in $\mathcal{O}(m\sqrt{n})$-time with high probability. In this section, we improve those results by presenting a deterministic $\mathcal{O}(m\sqrt{n})$ time algorithm which computes not only the radius and a central vertex but also all vertex eccentricities in a Helly graph.

To show this more general result, we heavily make use of our new structural results from Section 2. In particular, the fact that both the hyperbolicity of a Helly graph $G$ and the diameter of its center $C(G)$ are upper bounded by $\mathcal{O}(\sqrt{n})$ will be very handy. The following results from [52], [47] and [22, 38, 40] will be also very useful.

**Lemma 2.** [52] Let $G$ be an $m$-edge Helly graph and $k$ be a natural number. One can compute the set of all vertices of $G$ of eccentricity at most $k$, and their respective eccentricities, in $\mathcal{O}(km)$ time.

**Lemma 3.** [47] Let $G$ be an $m$-edge Helly graph and $v$ be an arbitrary vertex. There is an $\mathcal{O}(m)$-time algorithm which either certifies that $v$ is a central vertex of $G$ or finds a neighbor $u$ of $v$ such that $e(u) < e(v)$.

**Lemma 4.** [22, 38, 40] Let $G$ be an arbitrary $m$-edge graph and $\delta$ be its hyperbolicity. There is an $\mathcal{O}(\delta m)$-time algorithm which finds in $G$ a vertex $c$ with eccentricity at most $\text{rad}(G) + 2\delta$. The algorithm does not need to know the value of $\delta$ in order to work correctly.

First, by combining Lemmas 3 and 4, we show that a central vertex of a Helly graph $G$ can be computed in $\mathcal{O}(\delta m)$ time, where $\delta$ is the hyperbolicity of $G$.

**Lemma 5.** If $G$ is an $m$-edge Helly graph, then one can compute a central vertex and the radius of $G$ in $\mathcal{O}(\delta m)$ time, where $\delta$ is the hyperbolicity of $G$.

*Proof.* We use Lemma 4 in order to find, in $\mathcal{O}(\delta m)$ time, a vertex $c$ of $G$ with eccentricity $e(c) \le \text{rad}(G) + 2\delta$. Then we apply Lemma 3 at most $2\delta$ times in order to descend from $c$ to a central vertex $c^*$. It takes $\mathcal{O}(\delta m)$ time. $\square$

Combining this with Corollary 2, we get.

**Corollary 4.** For any $n$-vertex $m$-edge Helly graph $G$, a central vertex and the radius of $G$ can be computed in $\mathcal{O}(m\sqrt{n})$ time.

We are now ready to prove our main result of this section, guided by the following general ideas. To compute all vertex eccentricities, we focus on efficiently computing the center $C(G)$ (recall that each vertex $v \in V$ satisfies $e(v) = d(v, C(G)) + \text{rad}(G)$). In Corollary 3, we showed that $C(G)$ is a subset of a disk $S$ of radius $2\sqrt{n} + 3$ centered at any vertex $c \in C(G)$. We next describe how to eliminate any vertex $s \in S$ that is non-central (i.e., there exists some vertex $s'$ far from $s$ such that $e(s) \ge d(s, s') > \text{rad}(G)$). The remaining (central) vertices of $S$ form $C(G)$.
**Theorem 3.** All vertex eccentricities in an n-vertex m-edge Helly graph G can be computed in total $O(m\sqrt{n})$ time.

*Proof.* Our goal is to compute $e(v)$ for every $v \in V$. For that, we first find a central vertex c and compute the radius $rad(G)$ of G, which takes $O(m\sqrt{n})$ time by Corollary 4. If $rad(G) \le 5\sqrt{n} + 6$ (the choice of this number will be clear later), then $diam(G) \le 2rad(G) \le 10\sqrt{n} + 12$ and we are done by Lemma 2 (applied for $k = 10\sqrt{n} + 12$); in this case it takes total time $O(m\sqrt{n})$ to compute all eccentricities in G. Thus, from now on, we assume $rad(G) > 5\sqrt{n} + 6$. By Theorem 1(3), for every $v \in V$, $e(v) = d(v, C(G)) + rad(G)$ holds. Thus, in order to compute all the eccentricities, it is sufficient to compute $C(G)$. For a central vertex $c \in C(G)$ found earlier, let $S = N_G^{2\sqrt{n}+3}[c]$. Note that, by Corollary 3, $C(G) \subseteq S$.

In what follows, let $r = rad(G)$. Consider the BFS layers $L_i(S) = \{v \in V : d(v, S) = i\}$. Note that if $i \le r - 4\sqrt{n} - 6 \le r - diam_S(G)$, then all the vertices of $L_i(S)$ are at distance at most $r$ from all the vertices in $S$. As a result, in order to compute $C(G) \cap S (= C(G))$, it is sufficient to consider the layers $L_i(S)$, for $i > r - 4\sqrt{n} - 6$.

Set $A = \bigcup_{i>r-4\sqrt{n}-6} L_i(S)$. Since for every $v \notin S$, $d(v, c) = d(v, S) + 2\sqrt{n} + 3 \le r$, we deduce that there are at most $(r - 2\sqrt{n} - 3) - (r - 4\sqrt{n} - 6) = 2\sqrt{n} + 3$ nonempty layers in $A$.

We need to consider the “critical band” of all the layers $L_i(S)$, for $1 \le i \le r - 4\sqrt{n} - 6$ (all the layers between $S$ and $A$). We claim that there are at least $\sqrt{n}$ layers in this band. Indeed, under the above assumption, $r > 5\sqrt{n} + 6$. Then, the number of layers is exactly $e(c) - 2\sqrt{n} - 3 > 3\sqrt{n} + 3$, minus at most $2\sqrt{n} + 3$ layers most distant from $c$ (layers in $A$). Overall, there are at least $\sqrt{n}$ layers in the critical band, as claimed.

Then, one layer in the critical band, call it $L$, contains at most $n/\sqrt{n} = \sqrt{n}$ vertices (see Fig. 2).

**Claim 7** For every $a \in A$, there exists a “distant gate” vertex $a^* \in Pr(a, L)$ with the following property: $N^r[a] \cap S = N^{r-d(a,L)}[a^*] \cap S$.

In order to prove the claim, set $p = d(a, L)$ and $q = d(a, c) \le r$. Let us consider a family of balls $\mathcal{F} = \{N^p[a], N^{q-p}[c]\} \cup \{N^{r-p}[s] : s \in N^r[a] \cap (S \setminus c)\}$. We stress that $N^p[a] \cap N^{q-p}[c] = Pr(a, L)$. Then, in order to prove the existence of a distant gate, it suffices to prove that the balls in $\mathcal{F}$ intersect; indeed, if it is the case then we may choose for $a^*$ any vertex in the common intersection of the balls in $\mathcal{F}$. Clearly, $N^p[a] \cap N^{q-p}[c] \ne \emptyset$ and, in the same way, $N^p[a] \cap N^{r-p}[s] \ne \emptyset$ for each $s \in N^r[a] \cap (S \setminus c)$. Furthermore, since $L$ is in the critical band, $d(c, L) > 2\sqrt{n} + 3$, and therefore we have for each $s, s' \in S$:

$$2(r - p) \ge 2(q - p) = 2d(c, L) > diam_S(G) \ge d(s, s').$$

In the same way $(q - p) + (r - p) \ge 2(q - p) > diam_S(G) \ge d(s, c)$. The latter proves that the balls in $\mathcal{F}$ intersect. This concludes the proof of Claim 7.
<figure><img src="image_4.png" /><figcaption>Fig. 2: An illustration to the proof of Theorem 3, where the layers of A are represented in red, the critical band of layers are represented in blue, with distinguished darker blue layer L from the critical band which has at most $\sqrt{n}$ vertices.</figcaption></figure>

We finally explain how to compute these distant gates, and how to use this information in order to compute $S \cap C(G)$. Specifically:

- We make a BFS from every $u \in L$. It takes $O(m|L|) = O(m\sqrt{n})$ time. Doing so, we can compute $\forall a \in A$, $Pr(a, L)$, in total $O(|A||L|) = O(n\sqrt{n})$ time.

- Since $A$ contains at most $O(\sqrt{n})$ nonempty layers, then the number of pairwise distinct distances $d(a, L)$, for $a \in A$, is also in $O(\sqrt{n})$. Call the set of all these distances $I_A$. Then, $\forall u \in L$, and $\forall i \in I_A$, we also compute $p(u, i) = |N_G^{r-i}[u] \cap S|$. For that, we consider the vertices $u \in L$ sequentially. Recall that we compute a BFS tree rooted at $u$. In particular, we can order the vertices of $S$ by increasing distance to $u$. It takes $O(n)$ time. Similarly, we can order $I_A$ in $O(\sqrt{n} \log n) = o(n)$ time. In order to compute all the values $p(u, i)$, it suffices to scan in parallel these two ordered lists. The running time is $O(n)$ for every fixed $u \in L$, and so the total running time is $O(n|L|) = O(n\sqrt{n})$.

- Now, in order to compute a distant gate $a^*$, for $a \in A$, we proceed as follows. Let $i = d(a, L)$. We scan $Pr(a, L)$ and we store a vertex $a^*$ maximizing $p(a^*, i)$. It takes $O(|A||L|) = O(n\sqrt{n})$ time. On the way, $\forall u \in L$, let $q(u)$ be the maximum $i$ such that $a^* = u$ is the distant gate of some vertex $a \in A$, such that $d(a, L) = i$ (possibly, $q(u) = 0$ if $u$ was not chosen as the distant gate of any vertex).

- Let $s \in S$ be arbitrary. For having $s \in S \cap C(G)$, it is necessary and sufficient to have $s \in N^r[a] \cap S, \forall a \in A$. Equivalently, $\forall u \in L$, one must have $d(s, u) \le r - q(u)$. This can be checked in time $O(|L|)$ per vertex in $S$, and so, in total $O(n\sqrt{n})$ time.
☐

# 4 Eccentricities in Helly graphs with small hyperbolicity

In the previous section we showed that a central vertex of a Helly graph $G$ can be computed in $O(\delta m)$ time, where $\delta$ is the hyperbolicity of $G$. This nice result, combined with the property that all Helly graphs have hyperbolicity $O(\sqrt{n})$ (Corollary 2), was key to the design of our $O(m\sqrt{n})$-time algorithm for computing all vertex eccentricities. Next, we deepen the connection between hyperbolicity and fast eccentricity computation within Helly graphs.

As we have mentioned earlier, many graph classes (e.g., interval graphs, chordal graphs, dually chordal graphs, AT-free graphs, weakly chordal graphs and many others) have constant hyperbolicity. In particular, the dually chordal graphs and the $C_4$-free Helly graphs (superclasses of the interval graphs and of the strongly chordal graphs) are proper subclasses of the 1-hyperbolic Helly graphs. This raises the question whether all vertex eccentricities can be computed in linear time in a Helly graph $G$ if its hyperbolicity $\delta$ is a constant.

We prove in what follows that it is indeed the case, which is the main result of this section. The following result could also be considered as a parameterized algorithm on Helly graphs with $\delta$ as the parameter.

**Theorem 4.** If $G$ is an $m$-edge Helly graph of hyperbolicity $\delta$, then the eccentricity of all vertices of $G$ can be computed in $O(\delta^2 m \log \delta)$ time. The algorithm does not need to know the value of $\delta$ in order to work correctly. If $\delta$ (or a constant approximation of it) is known, then the running time is $O(\delta^2 m)$.

A proof of Theorem 4 is given below after Lemma 6.

As a byproduct, we get a linear time algorithm for computing all vertex eccentricities in $C_4$-free Helly graphs as well as in dually chordal graphs, generalizing known results from [11, 32, 52]. We recall that for dually chordal graphs, until this paper it was only known that a central vertex of such a graph can be found in linear time [11, 32].

**Corollary 5.** There is a linear time algorithm for computing all eccentricities in a dually chordal graph as well as in a $C_4$-free Helly graph (and hence, in a strongly chordal graph as well as in an interval graph).

Recall that a graph is called distance-hereditary if every its induced path is a shortest path. The class of distance-hereditary graphs is not a subclass of the class of Helly graphs. Nevertheless, as a byproduct of our results, we can get for distance-hereditary graphs a new linear-time algorithm for computing all eccentricities. It is known [60] that the injective hull $H$ of a distance-hereditary graph $G$ is a distance-hereditary Helly graph and can be computed in linear time. Furthermore, the injective hull $H$ of any graph $G$ preserves vertex eccentricities (that is, $e_G(v) = e_H(v)$ for each $v \in V(G)$) [39]. Thus, we can use Theorem 4 and the fact that the hyperbolicity of a distance-hereditary graph is at most 1
[74] to compute $e_H(v) = e_G(v)$ for all vertices $v$ of $G$ in total linear time. This provides an alternative proof for some results in [27, 33, 37, 42].

**Corollary 6.** [27, 37] There is a linear time algorithm for computing all eccentricities in a distance-hereditary graph.

The remainder of this section is devoted to proving Theorem 4. For that, we need the following result, which is proved in Subsection 4.1:

**Lemma 6.** Let $G$ be an $m$-edge Helly graph, $c$ be a central vertex of $G$ and $k$ be a natural number. There is an $O(k^2m)$-time algorithm which computes $C(G) \cap N^k[c]$.

*Proof (Proof of Theorem 4 assuming Lemma 6.)*. Since, by Theorem 1(3), $e(v) = d(v, C(G)) + rad(G)$ holds for every $v \in V$, as before, in order to compute all the eccentricities, it is sufficient to compute $C(G)$. We first find a central vertex $c$ and compute the radius $rad(G)$ of $G$. This takes $O(\delta m)$ time by Lemma 5.

By Claim 1, we know that $diam(C(G)) \le 2\delta+1$. Therefore, $C(G) \subseteq N^{2\delta+1}[c]$.

- If $\delta$ is known to us, we will fix $k := 2\delta+1$ (if only a constant approximation $\delta' \ge \delta$ of $\delta$ is known, we set $k = 2\delta' + 1$). Then, we are done applying Lemma 6.

- Otherwise, we work sequentially with $k = 2, 3, 4, 5, 8, 9, \dots, 2^p, 2^p + 1, 2^{p+1}, 2^{p+1} + 1, \dots$, and we stop after finding the smallest integer (power of 2) $k$ such that $C(G) \cap N^k[c] = C(G) \cap N^{k+1}[c]$. Indeed, by the isometricity (and hence connectedness) of $C(G)$ in $G$ (see Lemma 1), the set $C(G) \cap N^k[c]$ will contain all central vertices of $G$, i.e., $C(G) \cap N^k[c] = C(G)$. The latter will happen for some $k < 2(2\delta + 1)$ after at most $O(\log \delta)$ probes.

Overall, since we need to apply Lemma 6 at most $O(\log \delta)$ times, for some values $k < 2(2\delta + 1)$, the total running time is $O(\delta^2 m \log \delta)$. If $\delta$ (or a constant approximation of it is known), then we call Lemma 6 only once, and therefore the running time goes down to $O(\delta^2 m)$. $\square$

**4.1 Proof of Lemma 6**

In what follows, $G$ is a Helly graph, $k$ is an integer and $r = rad(G)$. Let $S_k = N^k[c]$. If $r \le 2k$, we can compute all central vertices in $O(km)$ time (see Lemma 2). Thus from now on, $r > 2k$. As $diam_{S_k}(G) \le 2k$, to find all central vertices in $S_k$ (i.e., the set $C(G) \cap S_k$), we need to consider only the vertices at distance $> r - 2k$ from $S_k$.

Let $i < 2k$ be fixed (we need to consider all possible $i$ between $k$ and $2k-1$ sequentially). Let $A_{k,i} = L_{r-i}(S_k)$ (where we recall that $L_{r-i}(S_k) = \{v \in V : d(v, S_k) = r - i\}$). We want to compute

$$S_{k,i} := \{s \in S_k : A_{k,i} \subseteq N^r[s]\}.$$
Indeed, $C(G) \cap S_k = \bigcap_{i=k}^{2k-1} S_{k,i}$.

The computation of $S_{k,i}$ (for $k, i$ fixed) works by two main phases. We give first a high-level description, followed by the details of the two main phases. The first phase sequentially processes layers $L_{r-i}(S_k)$, ..., $L_1(S_k)$ in $r-i$ steps. In each step, a family of nonempty pairwise disjoint sets is formed within the current layer by using the family of pairwise disjoint sets formed in the previous step for the layer above. The second phase proceeds in $i+2$ steps, forming again in each step a family of nonempty pairwise disjoint sets, accomplished by carefully expanding outward from the family of nonempty pairwise disjoint sets obtained in the previous step. By the final step, the resulting family is reduced to a single group $Y$ such that $S_{k,i} = S_k \cap Y$. We detail below these two main phases of the process.

**First phase of the algorithm.** To give the intuition of our approach, we need the following simple claim. For a vertex $v \in V$ and an integer $j$, let $L(v, j, S_k) := \{u \in V : d(v, S_k) = d(v, u) + d(u, S_k) \text{ and } d(v, u) = j\}$.

**Claim 8** Let $B \subseteq A_{k,i}$ be such that $\bigcap\{L(b, j, S_k) : b \in B\} \neq \emptyset$, for some $0 \le j < r-i$. Then, for every $s \in S_k$, $\max_{b \in B} d(s, b) \le r$ if and only if $d(s, \bigcap\{L(b, j, S_k) : b \in B\}) \le r-j$.

*Proof.* If $d(s, \bigcap\{L(b, j, S_k) : b \in B\}) \le r-j$, then clearly $\max_{b \in B} d(s, b) \le r$. Conversely, let us assume $\max_{b \in B} d(s, b) \le r$. Set $\mathcal{F} = \{N_G^{r-j}[s], N_G^{r+k-(i+j)}[c]\} \cup \{N_G^j[b] : b \in B\}$. We prove that the balls in $\mathcal{F}$ intersect.

- For each $b, b' \in B$, $N_G^j[b] \cap N_G^{j'}[b'] \supset \{L(b, j, S_k) : b \in B\} \neq \emptyset$.

- Since we assume $\max_{b \in B} d(s, b) \le r$, $N_G^j[b] \cap N_G^{r-j}[s] \neq \emptyset$.

- Furthermore, as for each $b \in B$ we have $d(b, c) = d(b, S_k) + k = r - i + k$, we obtain $N_G^{r-i+k-j}[c] \cap N_G^j[b] = L(b, j, S_k) \neq \emptyset$.

- Finally, since we have $j < r-i$, $(r-i+k-j) + (r-j) > k+i \ge k \ge d(s, c)$. Therefore, $N_G^{r+k-(i+j)}[c] \cap N_G^{r-j}[s] \neq \emptyset$.

It follows from the above that the balls in $\mathcal{F}$ pairwise intersect. By the Helly property, there exists a vertex $y$ in the common intersection of all the balls in $\mathcal{F}$. As for each $b \in B$, $y \in N_G^{r-i+k-j}[c] \cap N_G^j[b] = L(b, j, S_k)$, we deduce that $y \in \bigcap\{L(b, j, S_k) : b \in B\}$. Finally, we have $d(s, \bigcap\{L(b, j, S_k) : b \in B\}) \le d(s, y) \le r-j$. $\square$

We are now ready to present the first phase of our algorithm (for $k, i$ fixed). It is divided into $r-i$ steps: from $j=0$ to $j=r-i-1$. At step $j$, for $0 \le j < r-i$, the intermediate output is a collection of disjoint subsets $V_j^1, V_j^2, \dots, V_j^{p_j}$ of the layer $L_{r-i-j}(S_k)$. These disjoint subsets are in one-to-one correspondence with some partition $B_1, B_2, \dots, B_{p_j}$ of $A_{k,i}$. Specifically, the algorithm ensures that:

$$ \forall 1 \le t \le p_j, \quad V_j^t = \bigcap \{L(b, j, S_k) : b \in B_t\} \neq \emptyset. $$
Doing so, by the above Claim 8, for any $s \in S_k$ we have

$$ \max_{z \in A_{k,i}} d(s, z) \le r \iff \max_{1 \le t \le p_j} d(s, V_j^t) \le r - j. $$

Initially, for $j = 0$, every set $B_t$ is a singleton. Furthermore, $B_t = V_0^t$. Then, we show how to partition $L_{r-i-(j+1)}(S_k)$ from $V_j^1, V_j^2, \dots, V_j^{p_j}$ in total $O(\sum_{x \in L_{r-i-(j+1)}(S_k)} |N_G(x)|)$ time. Note that in doing so we get a total running time in $O(m)$ for that phase.

For that, let us define $W_j^t = N(V_j^t) \cap L_{r-i-(j+1)}(S_k)$. Since the subsets $V_j^t$ are pairwise disjoint, the construction of the $W_j^t$'s takes total $O(\sum_{x \in L_{r-i-(j+1)}(S_k)} |N_G(x)|)$ time. Furthermore:

**Claim 9** $W_j^t = \bigcap \{L(b, j+1, S_k) : b \in B_t\}$.

*Proof.* We only need to prove that we have $\bigcap \{L(b, j+1, S_k) : b \in B_t\} \subseteq W_j^t$ (the other inclusion being trivial by construction). For that, let $x \in \bigcap \{L(b, j+1, S_k) : b \in B_t\}$ be arbitrary. Recall that we have, for each $b \in B_t$, $d(b, c) = k+d(b, S_k) = r - i + k$. In particular, $x \in L(b, j+1, S_k) = L(b, j+1, c)$. It implies that the balls in $\{N_G[x], N_G^{r-i+k-j}[c]\} \cup \{N_G^j[b] : b \in B_t\}$ pairwise intersect. By the Helly property, $x$ has a neighbour in $N_G^{r-i+k-j}[c] \cap (\bigcap \{N^j[b] : b \in B_t\}) = \bigcap \{L(b, j, S_k) : b \in B_t\} = W_j^t$. Since $x \in L_{r-i-(j+1)}(S_k)$, we obtain as desired $x \in W_j^t$. $\square$

Finally, in order to compute the new sets $V_{j+1}^t$, we proceed as follows. Let $W = \{W_j^t : 1 \le t \le p_j\}$. While $W \ne \emptyset$, we select some vertex $x \in L_{r-i-(j+1)}(S_k)$ maximizing $\#\{t : x \in W_j^t\}$. Then, we create a new set $\bigcap_{t:x \in W_j^t} W_j^t$, and we remove $\{W_j^t : x \in W_j^t\}$ from $W$. Note that, by the above Claim 9, $\bigcap_{t:x \in W_j^t} W_j^t = \bigcap_{t:x \in W_j^t} \bigcap \{L(b, j+1, S_k) : b \in B_t\} = \bigcap \{L(b, j+1, S_k) : b \in \bigcup_{t:x \in W_j^t} B_t\}$. Furthermore, by maximality of vertex $x$, $\bigcap_{t:x \in W_j^t} W_j^t$ is disjoint from the subsets in $\{W_j^t : x \notin W_j^t\}$. The latter ensures that all the new sets we create are pairwise disjoint. See Fig. 3 for an illustration of this first phase.

In order to implement this above process efficiently, we store each $x \in L_{r-i-(j+1)}(S_k)$ in a list indexed by $\#\{t : x \in W_j^t\}$. Then, we traverse these lists by decreasing index. We keep, for each $x \in L_{r-i-(j+1)}(S_k)$, a pointer to its current position in order to dynamically change its list throughout the process. See also the proof of Lemma 2 in [52]. The running time is proportional to $\sum \{|W_j^t| : 1 \le t \le p_j\} = O(\sum_{x \in L_{r-i-(j+1)}(S_k)} |N_G(x)|)$.

Second phase of the algorithm. Let $C_1, C_2, \dots, C_p$ denote the sets $V_{r-i-1}^1, \dots, V_{r-i-1}^{p_{r-i-1}}$ (i.e., those obtained at the end of the first phase of our algorithm). Note that $C_1, C_2, \dots, C_p$ are subsets of $L_1(S_k) (= N_G(S_k))$. At this point, it is not possible anymore to follow the shortest-paths between $A_{k,i}$ and $S_k$.

Then, let $X = A_{k,i} \cup \{c\}$. Set $\alpha(c) = k+i+2$ and $\alpha(a) = r$ for each $a \in A_{k,i}$. We define the set $Y = \{y : \forall x \in X, d(y, x) \le \alpha(x)\}$. Observe that $S_{k,i} = Y \cap S_k$
<figure><img src="image_5.png" /><figcaption>Fig. 3: An illustration of step *j* of the first phase of the algorithm from Lemma 6, using each $V_j^t$ to compute $W_j^t$ for all $1 \le t \le p_j$, and using the vertices of $L_{r-i-(j+1)}(S_k)$ belonging to maximum $W_j^t$ to form $V_{j+1}^{t'}$.</figcaption></figure>

(recall that $S_{k,i}$ was defined as $\{s \in S_k : A_{k,i} \subseteq N^r[s]\}$). Therefore, in order to compute $S_{k,i}$, it suffices to compute $Y$.

For that, we proceed in $i+2$ steps. At step $\ell$, for $0 \le \ell \le i+1$, we maintain a family of nonempty pairwise disjoint sets $Z_{\ell}^1, Z_{\ell}^2, \dots, Z_{\ell}^{q_{\ell}}$ and a covering $X_\ell^1, X_\ell^2, \dots, X_\ell^{q_{\ell}}$ of $X$ such that the following is true for every $1 \le t \le q_\ell$:

$$Z_{\ell}^{t} = \bigcap_{x \in X_{\ell}^{t}} N_{G}^{\alpha(x)-(i+1)+\ell}[x].$$

Doing so, after $i+2$ steps, the set $Y$ is nonempty if and only if $q_{i+1} = 1$ (the above partition is reduced to one group). Furthermore, if it is the case, $Y = Z_{i+1}^1$.

Initially, for $\ell = 0$, we start from $Z_0^1 = C_1, \dots, Z_0^p = C_p$, and then the corresponding covering is $\forall 1 \le t \le p, X_0^t = B_t \cup \{c\}$ (with $B_1, B_2, \dots, B_p$ being the partition of $A_{k,i}$ after the first phase of our algorithm). – Note that this is only a covering, and not a partition, because the vertex $c$ is contained in all the groups. – For going from $\ell$ to $\ell+1$, we proceed as we did during the first phase. Specifically, for every $t$, let $U_\ell^t = N_G[Z_\ell^t]$. Since the sets $Z_\ell^t$ are pairwise disjoint, the computation of all the intermediate sets $U_\ell^t$ takes total $\mathcal{O}(m)$ time.

$$\textbf{Claim 10} \quad U_{\ell}^{t} = \bigcap_{x \in X_{\ell}^{t}} N_{G}^{\alpha(x)-(i+1)+(\ell+1)}[x].$$

The proof is similar to that of Claim 9.

Finally, in order to compute the new sets $Z_{\ell+1}^{t'}$, let $\mathcal{U} = \{U_{\ell}^{t} : 1 \le t \le q_{\ell}\}$. While $\mathcal{U} \ne \emptyset$, we select some vertex $u \in V$ maximizing $\#\{t : u \in U_{\ell}^{t}\}$ in $\mathcal{U}$.
Then, we create a new set $\bigcap_{t:u \in U_\ell^t} U_\ell^t$, and we remove $\{U_\ell^t : u \in U_\ell^t\}$ from $\mathcal{U}$.
The running time is proportional to $\sum \{|U_\ell^t| : 1 \le t \le q_\ell\} = \mathcal{O}(m)$.

Complexity analysis. Overall, the first phase runs in $O(m)$ time, and the second phase runs in $O(im) = O(km)$ time. Since it applies for $k, i$ fixed, the total running time of the algorithm of Lemma 6 (for $k$ fixed) is in $O(k^2m)$.

This completes the proof of Lemma 6.

# 5 Conclusion

We presented the first truly subquadratic deterministic algorithm for computing all eccentricities in a Helly graph. For Helly graphs with constant hyperbolicity, we gave a linear time algorithm. To obtain these results, we heavily used our new structural properties of Helly graphs. A few questions remain open.

1. We showed that the hyperbolicity of an $n$-vertex Helly graph $G$ is at most $\sqrt{n} + 1$. This enabled a refined algorithm for computing all eccentricities in Helly graphs. What other algorithmic graph problems can efficiently be solved on Helly graphs by utilizing a bound on the hyperbolicity? More generally, in Metric Graph Theory, it is interesting and important to understand how metric properties can help in designing efficient graph algorithms.

2. We showed that in graphs the Helly property for balls of equal radii implies the Helly property for balls with variable radii. It would be interesting to know whether a similar result holds for all (discrete) metric spaces.

3. In [39], Helly graphs were generalized to graphs with bounded Helly-gap. Can our results be extended to all graphs with bounded Helly-gap? Note that the Helly graphs are the graphs with Helly-gap equal 0.

4. It is interesting to know also whether our algorithm for general Helly graphs can be improved. Are there algorithms for computing all eccentricities in Helly graphs that run in $o(m\sqrt{n})$ time?

We were not able to get any non-trivial lower bounds on the complexity. It seems challenging to adapt SETH-hardness reductions from the literature to Helly graphs. The reason is that all these reductions are based on the so-called Orthogonal Vectors (OV) problem, which is linear-time solvable for set systems with the Helly property. We can show that using the following algorithm to solve a problem equivalent to OV under simple reductions.

Input: Families $A, B$ of $n$ sets over a universe $U$ of cardinality $d = c \log n$.

Problem: Determine whether there exist $a \in A, b \in B$ disjoint.

- Choose an element $u_0$ that belongs to a maximum number of sets in $B$. Let $B_0$ denote all sets in $B$ that contain $u_0$.

- Let $U_0$ be the common intersection of all sets in $B_0$. This subuniverse is nonempty because it contains $u_0$. Furthermore, we may assume, by the Helly property, that every set $a$ in $A$ must contain at least one element of $U_0$ (if $a \cap U_0 = \emptyset$, then $a$ is disjoint from at least one set of $B_0$ and we are done).
- If $B_0 = B$, then we conclude that every set in $A$ intersects every set in $B$. Otherwise (if $B_0 \neq B$), we continue from the beginning with $B = B \setminus B_0$.

Doing so, we consider disjoint lists $B_0, B_1, \dots$, and their respective common intersections $U_0, U_1, \dots$. All subuniverses $U_i$ are disjoint, which follows from the maximality of $u_i$ at every step of the algorithm.

This result provides a further motivation for studying Helly graphs: since all known hardness reductions are based on SETH/OV, this paper continues the systematic exploration of graph classes for which OV becomes easy.

## References

1. A. Abboud, V. Vassilevska Williams, and J. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In *SODA*, pages 377–391. SIAM, 2016.

2. M. Abu-Ata and F. F. Dragan. Metric tree-like structures in real-world networks: an empirical study. *Networks*, 67(1):49–68, 2016.

3. A. B. Adcock, B. D. Sullivan, and M. W. Mahoney. Tree-like structure in large social and information networks. In *2013 IEEE 13th International Conference on Data Mining*, pages 1–10. IEEE, 2013.

4. H.-J. Bandelt and V. Chepoi. 1-hyperbolic graphs. *SIAM J. Discret. Math.*, 16(2):323–334, 2003.

5. H.-J. Bandelt and V. Chepoi. Metric graph theory and geometry: a survey. *Contemporary Mathematics*, 453:49–86, 2008.

6. H.-J. Bandelt and E. Pesch. Dismantling absolute retracts of reflexive graphs. *European Journal of Combinatorics*, 10(3):211–220, 1989.

7. H.-J. Bandelt and E. Pesch. A Radon theorem for Helly graphs. *Archiv der Mathematik*, 52(1):95–98, 1989.

8. H.-J. Bandelt and E. Prisner. Clique graphs and Helly graphs. *Journal of Combinatorial Theory, Series B*, 51(1):34–45, 1991.

9. M. Borassi, D. Coudert, P. Crescenzi, and A. Marino. On computing the hyperbolicity of real-world graphs. In *Algorithms-ESA 2015*, pages 215–226. Springer, 2015.

10. M. Borassi, P. Crescenzi, and M. Habib. Into the square: On the complexity of some quadratic-time solvable problems. *Electronic Notes in Theoretical Computer Science*, 322:51–67, 2016.

11. A. Brandstädt, V. Chepoi, and F. F. Dragan. The algorithmic use of hypertree structure and maximum neighbourhood orderings. *Discret. Appl. Math.*, 82(1-3):43–77, 1998.

12. A. Brandstädt, F. F. Dragan, V. Chepoi, and V. Voloshin. Dually chordal graphs. *SIAM Journal on Discrete Mathematics*, 11(3):437–455, 1998.

13. K. Bringmann, T. Husfeldt, and M. Magnusson. Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth. In *IPEC*, 2018.

14. G. Brinkmann, J. Koolen, and V. Moulton. On the hyperbolicity of chordal graphs. *Annals of Combinatorics*, 5(1):61–69, 2001.

15. S. Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. *ACM Transactions on Algorithms*, 15(2):21, 2018.
16. 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. In *34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary*, pages 22:1–22:15, 2018.

17. J. Chalopin, V. Chepoi, A. Genevois, H. Hirai, and D. Osajda. Helly groups, 2020.

18. J. Chalopin, V. Chepoi, H. Hirai, and D. Osajda. Weakly modular graphs and nonpositive curvature. *Mem. Amer. Math. Soc.*, 2020, 159 pp.

19. M. Chastand, F. Laviolette, and N. Polat. On constructible graphs, infinite bridged graphs and weakly cop-win graphs. *Discrete Mathematics*, 224(1-3):61–78, 2000.

20. V. Chepoi and F. F. Dragan. Disjoint sets problem. 1992.

21. V. Chepoi and F. F. Dragan. A linear-time algorithm for finding a central vertex of a chordal graph. In J. van Leeuwen, editor, *Algorithms - ESA '94, Second Annual European Symposium, Utrecht, The Netherlands, September 26-28, 1994, Proceedings*, volume 855 of *Lecture Notes in Computer Science*, pages 159–170. Springer, 1994.

22. V. Chepoi, F. F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and approximating trees of $\delta$-hyperbolic geodesic spaces and graphs. In M. Teil-laud, editor, *Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 9-11, 2008*, pages 59–68. ACM, 2008.

23. V. Chepoi, F. F. Dragan, and Y. Vaxès. Center and diameter problems in plane triangulations and quadrangulations. In *SODA*, pages 346–355, 2002.

24. V. Chepoi, F. F. F. Dragan, M. Habib, Y. Vaxès, and H. Alrasheed. Fast approximation of eccentricities and distances in hyperbolic graphs. *Journal of Graph Algorithms and Applications*, 23(2):393–433, 2019.

25. D. Corneil, F. F. Dragan, M. Habib, and C. Paul. Diameter determination on restricted graph families. *Discrete Applied Mathematics*, 113(2-3):143–166, 2001.

26. D. Coudert and G. Ducoffe. Recognition of $c_4$-free and $1/2$-hyperbolic graphs. *SIAM J. Discret. Math.*, 28(3):1601–1617, 2014.

27. D. Coudert, G. Ducoffe, and A. Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. *ACM Transactions on Algorithms*, 15(3), 2019.

28. M. Dourado, F. Protti, and J. Szwarcfiter. Complexity aspects of the Helly property: Graphs and hypergraphs. *The Electronic Journal of Combinatorics*, 1000:17–12, 2009.

29. F. F. Dragan. *Centers of Graphs and the Helly Property (in Russian)*. PhD thesis, Moldava State University, Chișinău, 1989.

30. F. F. Dragan. Conditions for coincidence of local and global minima for eccentricity function on graphs and the Helly property (in Russian). *Studies in Applied Mathematics and Information Science*, pages 49–56, 1990.

31. F. F. Dragan. Domination in quadrangle-free Helly graphs. *Cybernetics and Systems Analysis*, 29(6):822–829, 1993.

32. F. F. Dragan. HT-graphs: centers, connected $r$-domination and Steiner trees. *Comput. Sci. J. of Moldova (Kishinev)*, 1(2):64–83, 1993.

33. F. F. Dragan. Dominating cliques in distance-hereditary graphs. In E. M. Schmidt and S. Skyum, editors, *Algorithm Theory - SWAT '94, 4th Scandinavian Workshop on Algorithm Theory, Aarhus, Denmark, July 6-8, 1994, Proceedings*, volume 824 of *Lecture Notes in Computer Science*, pages 370–381. Springer, 1994.

34. F. F. Dragan and A. Brandstädt. $r$-dominating cliques in graphs with hypertree structure. *Discrete Mathematics*, 162(1-3):93–108, 1996.
35. F. F. Dragan, G. Ducoffe, and H. M. Guarnera. Fast deterministic algorithms for computing all eccentricities in (hyperbolic) helly graphs. In A. Lubiw and M. R. Salavatipour, editors, *Algorithms and Data Structures - 17th International Symposium, WADS 2021, Virtual Event, August 9-11, 2021, Proceedings*, volume 12808 of *Lecture Notes in Computer Science*, pages 300-314. Springer, 2021.

36. F. F. Dragan and H. M. Guarnera. Obstructions to a small hyperbolicity in Helly graphs. *Discrete Mathematics*, 342(2):326–338, 2019.

37. F. F. Dragan and H. M. Guarnera. Eccentricity function in distance-hereditary graphs. *Theor. Comput. Sci.*, 833:26–40, 2020.

38. F. F. Dragan and H. M. Guarnera. Eccentricity terrain of $\delta$-hyperbolic graphs. *J. Comput. Syst. Sci.*, 112:50–65, 2020.

39. F. F. Dragan and H. M. Guarnera. Helly-gap of a graph and vertex eccentricities. *Theor. Comput. Sci.*, 867:68–84, 2021.

40. F. F. Dragan, M. Habib, and L. Viennot. Revisiting radius, diameter, and all eccentricity computation in graphs through certificates. *CoRR*, abs/1803.04660, 2018.

41. F. F. Dragan and A. Mohammed. Slimness of graphs. *Discret. Math. Theor. Comput. Sci.*, 21(3), 2019.

42. F. F. Dragan and F. Nicolai. LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem. *Discret. Appl. Math.*, 98(3):191–207, 2000.

43. F. F. Dragan, F. Nicolai, and A. Brandstädt. LexBFS-orderings and power of graphs. In F. d'Amore, P. G. Franciosa, and A. Marchetti-Spaccamela, editors, *Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG '96, Cadenabbia (Como), Italy, June 12-14, 1996, Proceedings*, volume 1197 of *Lecture Notes in Computer Science*, pages 166–180. Springer, 1996.

44. F. F. Dragan, K. Prisakaru, and V. Chepoi. The location problem on graphs and the Helly problem. *Diskretnaya Matematika*, 4(4):67–73, 1992.

45. A. Dress. Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces. *Advances in Mathematics*, 53(3):321–402, 1984.

46. G. Ducoffe. A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters. In *SOSA*, 2019.

47. G. Ducoffe. Distance problems within Helly graphs and k-Helly graphs. *CoRR*, abs/2011.00001, 2020.

48. G. Ducoffe. Beyond helly graphs: The diameter problem on absolute retracts. In L. Kowalik, M. Pilipczuk, and P. Rzazewski, editors, *Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers*, volume 12911 of *Lecture Notes in Computer Science*, pages 321–335. Springer, 2021.

49. G. Ducoffe. Isometric embeddings in trees and their use in distance problems. In F. Bonchi and S. J. Puglisi, editors, *46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia*, volume 202 of *LIPIcs*, pages 43:1–43:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

50. G. Ducoffe. The diameter of AT-free graphs. *Journal of Graph Theory*, 99(4):594–614, 2022.

51. G. Ducoffe. Optimal centrality computations within bounded clique-width graphs. *Algorithmica*, 84(11):3192–3222, 2022.

52. G. Ducoffe and F. F. Dragan. A story of diameter, radius, and (almost) Helly property. *Networks*, 77(3):435–453, 2021.
53. G. Ducoffe, M. Habib, and L. Viennot. Fast diameter computation within split graphs. In *COCOA*, pages 155–167. Springer, 2019.

54. G. Ducoffe, M. Habib, and L. Viennot. Diameter computation on *H*-minor free graphs and graphs of bounded (distance) VC-dimension. In *SODA*, pages 1905–1922. SIAM, 2020.

55. D. Eppstein. Diameter and treewidth in minor-closed graph families. *Algorithmica*, 27(3-4):275–291, 2000.

56. A. Farley and A. Proskurowski. Computation of the center and diameter of outerplanar graphs. *Discrete Applied Mathematics*, 2(3):185–191, 1980.

57. H. Fournier, A. Ismail, and A. Vigneron. Computing the Gromov hyperbolicity of a discrete metric space. *Inf. Process. Lett.*, 115(6-8):576–579, 2015.

58. P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann. Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\tilde{O}(n^{5/3})$ time. In *SODA*, pages 495–514. SIAM, 2018.

59. M. Gromov. *Hyperbolic Groups*, pages 75–263. Springer, New York, NY, 1987.

60. H. M. Guarnera, F. F. Dragan, and A. Leitert. Injective hulls of various graph classes. *Graphs Comb.*, 38(4):112, 2022.

61. J. Isbell. Six theorems about injective metric spaces. *Commentarii Mathematici Helvetici*, 39(1):65–76, 1964.

62. W. S. Kennedy, I. Saniee, and O. Narayan. On the hyperbolicity of large-scale networks and its estimation. In *2016 IEEE International Conference on Big Data (Big Data)*, pages 3344–3351. IEEE, 2016.

63. J. H. Koolen and V. Moulton. Hyperbolic bridged graphs. *Eur. J. Comb.*, 23(6):683–699, 2002.

64. D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. Tenfelde-Podehl, and O. Zlotowski. Centrality indices. In *Network Analysis*, pages 16–61. Springer, 2005.

65. M. Lin and J. Szwarcfiter. Faster recognition of clique-Helly and hereditary clique-Helly graphs. *Information Processing Letters*, 103(1):40–43, 2007.

66. O. Narayan and I. Saniee. Large-scale curvature of networks. *Physical Review E*, 84(6):066108, 2011.

67. S. Olariu. A simple linear-time algorithm for computing the center of an interval graph. *International Journal of Computer Mathematics*, 34(3-4):121–128, 1990.

68. N. Polat. Convexity and fixed-point properties in Helly graphs. *Discrete Mathematics*, 229(1-3):197–211, 2001.

69. N. Polat. On constructible graphs, locally Helly graphs, and convexity. *Journal of Graph Theory*, 43(4):280–298, 2003.

70. L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In *STOC*, pages 515–524. ACM, 2013.

71. Y. Shavitt and T. Tankel. Hyperbolic embedding of internet graph for distance estimation and overlay construction. *IEEE/ACM Transactions on Networking*, 16(1):25–36, 2008.

72. J. L. Szwarcfiter and C. F. Bornstein. Clique graphs of chordal and path graphs. *SIAM J. Discret. Math.*, 7(2):331–336, 1994.

73. R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. *Theoretical Computer Science*, 348(2-3):357–365, 2005.

74. Y. Wu and C. Zhang. Hyperbolicity and chordality of a graph. *Electr. J. Comb.*, 18(1):Paper #P43, 2011.