Feodor F Dragan
email: dragan@cs.kent.edu

Guillaume Ducoffe
email: guillaume.ducoffe@ici.ro

Heather M Guarnera
email: hguarnera@wooster.edu

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

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. It is also known that every graph isometrically embeds into a Helly graph, making the latter an important class of graphs in Metric Graph Theory. 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 G can be computed with high probability in Õ(m √ n) time (i.e., subquadratic in n+m). In this paper, we improve that result by presenting a deterministic O(m √ 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 δ. More specifically, we show that the radius and a central vertex of an m-edge δ-hyperbolic Helly graph G can be computed in O(δm) time and that all vertex eccentricities in G can be computed in O(δ 2 m) time. To show this more general result, we heavily use our new structural properties obtained for Helly graphs.

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) 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 a BFS 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 [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF][START_REF] Borassi | Into the square: On the complexity of some quadratic-time solvable problems[END_REF][START_REF] Chepoi | Fast approximation of eccentricities and distances in hyperbolic graphs[END_REF][START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF] since, under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time (i.e., in O(n a m b ), 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 problem [START_REF] Chepoi | Disjoint sets problem[END_REF]. Under the Strong Exponential-Time Hypothesis (SETH), we cannot solve Disjoint Sets in truly subquadratic time, and so neither we can compute the diameter of split graphs in truly subquadratic time [START_REF] Borassi | Into the square: On the complexity of some quadratic-time solvable problems[END_REF].

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 [START_REF] Chepoi | A linear-time algorithm for finding a central vertex of a chordal graph[END_REF]. Efficient algorithms for computing the diameter and/or the radius or finding a central vertex are also known for interval graphs [START_REF] Dragan | LexBFS-orderings and power of graphs[END_REF][START_REF] Olariu | A simple linear-time algorithm for computing the center of an interval graph[END_REF], AT-free graphs [START_REF] Ducoffe | Around the diameter of AT-free graphs[END_REF], directed path graphs [START_REF] Corneil | Diameter determination on restricted graph families[END_REF], distance-hereditary graphs [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF][START_REF] Dragan | Dominating cliques in distance-hereditary graphs[END_REF][START_REF] Dragan | Eccentricity function in distance-hereditary graphs[END_REF][START_REF] Dragan | LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem[END_REF], strongly chordal graphs [START_REF] Dragan | Centers of Graphs and the Helly Property[END_REF], dually chordal graphs [START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF][START_REF] Dragan | HT-graphs: centers, connected r-domination and Steiner trees[END_REF], chordal bipartite graphs [START_REF] Ducoffe | Beyond Helly graphs: the diameter problem on absolute retracts[END_REF], outerplanar graphs [START_REF] Farley | Computation of the center and diameter of outerplanar graphs[END_REF], planar graphs [START_REF] Cabello | Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs[END_REF][START_REF] Gawrychowski | Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n 5/3 ) time[END_REF], graphs with bounded clique-width [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF][START_REF] Ducoffe | Optimal diameter computation within bounded clique-width graphs[END_REF], graphs with bounded tree-width [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF][START_REF] Bringmann | Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth[END_REF][START_REF] Ducoffe | Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension[END_REF] and, more generally, H-minor free graphs and graphs of bounded (distance) VC-dimension [START_REF] Ducoffe | Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension[END_REF].

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 [START_REF] Dourado | Complexity aspects of the Helly property: Graphs and hypergraphs[END_REF]. The Helly graphs are well studied in Metric Graph Theory. E.g., see the survey [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF] 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 hyperconvex metric spaces [START_REF] Dress | Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces[END_REF][START_REF] Isbell | Six theorems about injective metric spaces[END_REF]. A minimal by inclusion Helly graph H which contains a given graph G as an isometric subgraph is unique and called the injective hull [START_REF] Isbell | Six theorems about injective metric spaces[END_REF] or the tight span [START_REF] Dress | Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces[END_REF] of G. Polynomial-time recognition algorithms for the Helly graphs were presented in [START_REF] Bandelt | Dismantling absolute retracts of reflexive graphs[END_REF][START_REF] Dragan | Centers of Graphs and the Helly Property[END_REF][START_REF] Lin | Faster recognition of clique-Helly and hereditary clique-Helly graphs[END_REF]. Several structural properties of these graphs were also identified (see [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF] and the references cited therein). 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 [START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF][START_REF] Brandstädt | Dually chordal graphs[END_REF][START_REF] Dragan | The location problem on graphs and the Helly problem[END_REF][START_REF] Dragan | HT-graphs: centers, connected r-domination and Steiner trees[END_REF]. As we already mentioned it [START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF][START_REF] Dragan | The location problem on graphs and the Helly problem[END_REF][START_REF] Dragan | HT-graphs: centers, connected r-domination and Steiner trees[END_REF], the diameter, the radius and a central vertex of a dually chordal graph can be found in linear time, 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 [START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF] for computing both the radius and the diameter and in [START_REF] Ducoffe | Distance problems within Helly graphs and k-Helly graphs[END_REF] for finding a central vertex. Those algorithms are randomized and run, with high probability, in Õ(m √ 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 [START_REF] Dragan | Conditions for coincidence of local and global minima for eccentricity function on graphs and the Helly property[END_REF]: every vertex of locally minimum eccentricity is a central vertex. In [START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF], a lineartime 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 [START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF].

Our Contribution. We improve those results from [START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF] and [START_REF] Ducoffe | Distance problems within Helly graphs and k-Helly graphs[END_REF] by presenting a deterministic O(m √ 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. 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 [START_REF] Koschützki | Centrality indices[END_REF] is defined as 1 e G (v) . We complete this above result with a parameterized linear-time algorithm for computing all vertex eccentricities in Helly graphs, with the parameter being the Gromov hyperbolicity δ, as defined by the following four point condition. The hyperbolicity of a graph G [START_REF] Gromov | Hyperbolic Groups[END_REF] is the smallest half-integer δ ≥ 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δ. In this case we say that G is δ-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 δ 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 [START_REF] Fournier | Computing the Gromov hyperbolicity of a discrete metric space[END_REF]), however it is unlikely that it can be done in subquadratic time [START_REF] Borassi | Into the square: On the complexity of some quadratic-time solvable problems[END_REF][START_REF] Coudert | Recognition of c 4 -free and 1/2-hyperbolic graphs[END_REF][START_REF] Fournier | Computing the Gromov hyperbolicity of a discrete metric space[END_REF]. A 2-approximation of hyperbolicity can be computed in O(n 2.69 ) time [START_REF] Fournier | Computing the Gromov hyperbolicity of a discrete metric space[END_REF] and an 8-approximation can be computed in O(n 2 ) time [START_REF] Chalopin | Fast approximation and exact computation of negative curvature parameters of graphs[END_REF] (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., [START_REF] Abu-Ata | Metric tree-like structures in real-world networks: an empirical study[END_REF][START_REF] Borassi | On computing the hyperbolicity of real-world graphs[END_REF][START_REF] Kennedy | On the hyperbolicity of large-scale networks and its estimation[END_REF][START_REF] Narayan | Large-scale curvature of networks[END_REF]). 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 [START_REF] Abu-Ata | Metric tree-like structures in real-world networks: an empirical study[END_REF][START_REF] Brinkmann | On the hyperbolicity of chordal graphs[END_REF][START_REF] Chepoi | Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs[END_REF][START_REF] Dragan | Obstructions to a small hyperbolicity in Helly graphs[END_REF][START_REF] Dragan | Slimness of graphs[END_REF][START_REF] Koolen | Hyperbolic bridged graphs[END_REF][START_REF] Wu | Hyperbolicity and chordality of a graph[END_REF]. 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 [START_REF] Brandstädt | Dually chordal graphs[END_REF][START_REF] Dragan | Obstructions to a small hyperbolicity in Helly graphs[END_REF]). Notice also that any graph is δ-hyperbolic for some δ ≤ diam(G)/2.

We show that the radius and a central vertex of an m-edge Helly graph G with hyperbolicity δ can be computed in O(δm) time and that all vertex eccentricities in G can be computed in O(δ 2 m log δ) time, even if δ is not known to us. If either δ or a constant approximation of it is known, then the running time of our algorithm can be lowered to O(δ 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 [START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF][START_REF] Dragan | HT-graphs: centers, connected r-domination and Steiner trees[END_REF][START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF]. Previously, for dually chordal graphs, it was only known that a central vertex can be found in linear time [START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF][START_REF] Dragan | HT-graphs: centers, connected r-domination and Steiner trees[END_REF]. 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 [START_REF] Chepoi | Fast approximation of eccentricities and distances in hyperbolic graphs[END_REF]. For general δ-hyperbolic graphs, there are only additive O(δ)-approximations of the diameter and the radius, that can be computed in linear time [START_REF] Chepoi | Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs[END_REF][START_REF] Dragan | Eccentricity terrain of δ-hyperbolic graphs[END_REF][START_REF] Dragan | Revisiting radius, diameter, and all eccentricity computation in graphs through certificates[END_REF].

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 √ n + 1 and the diameter of the center of G is at most 2 √ n + 3. 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 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 ∈

V : d G (u, v) ≤ r}, and denoted by N r G [v]. Sometimes, N r G [v] is called the r-neighborhood of v. In particular, N G [v] := N 1 G [v] and N G (v) := N G [v] \ {v} denote the closed and
open neighbourhoods of a vertex v, respectively. More generally, for any vertexsubset S and a vertex u, we define d G (u, S)

:= min v∈S d G (u, v), N r G [S] := v∈S N r G [v], N G [S] := N 1 G [S] and N G (S) := N G [S] \ S.
The metric projection of a vertex u on S, denoted by P r G (u, S), is defined as {v ∈ S :

d G (u, v) = d G (u, S)}. The metric interval I G (u, v) between u and v is {w ∈ V : d G (u, w) + d G (w, v) = d G (u, v)}. For any k ≤ d G (u, v), we can also define the slice L(u, k, v) := {w ∈ I G (u, v) : d G (u, w) = k}.
Recall that the eccentricity of a vertex u is defined as max v∈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 rad(G) and diam(G), respectively.

A vertex c is called central in G if e G (c) = rad(G). The set of all central vertices of G is denoted by C(G) := {v ∈ V : e G (v) = 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 ∈ 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 ⊆ V is called convex in G if, for every vertices x, y ∈ S, all shortest paths connecting them are contained in S (i.e., I G (x, y) ⊆ S). For β ≥ 0, we say that S is β-pseudoconvex [START_REF] Dragan | Eccentricity terrain of δ-hyperbolic graphs[END_REF] if, for every vertices x, y ∈ S, any vertex

z ∈ I G (x, y)\S satisfies min{d G (z, x), d G (z, y)} ≤ β. A subgraph H of G is called isometric (or distance-preserving) if, for every ver- tices x, y of H, d G (x, y) = d H (x, y).

Helly graphs and their hyperbolicity

Here we demonstrate that for Helly graphs, having a constant hyperbolicity is equivalent to the following properties: having β-pseudoconvexity of balls with a constant β, or having the diameter of the center bounded by a constant for all subsets of vertices, or not having a large (γ × γ) rectilinear grid as an isometric subgraph. These results generalize some known results from [START_REF] Chalopin | Helly groups[END_REF][START_REF] Chalopin | Weakly modular graphs and nonpositive curvature[END_REF][START_REF] Chepoi | Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs[END_REF][START_REF] Dragan | Obstructions to a small hyperbolicity in Helly graphs[END_REF][START_REF] Dragan | Eccentricity terrain of δ-hyperbolic graphs[END_REF].

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 ⊆ V and any vertex v ∈ V the eccentricity of v in G with respect to

M as e M (v) = max u∈M d G (u, v). Let diam M (G) = max v∈M e M (v), rad M (G) = min v∈V e M (v), C M (G) = {v ∈ 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 (•) is unimodal for every set

M ⊆ V ; (3) e M (v) = d G (v, C M (G)) + rad M (G) holds for every set M ⊆ V and every vertex v ∈ V ; (4) 2rad M (G) -1 ≤ diam M (G) ≤ 2rad M (G) holds for every set M ⊆ V ; (5) rad M (G) = diam M (G)+1
Proof of this theorem and of all other statements of this section can be found in full version of this paper [START_REF] Dragan | Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs[END_REF]. The equivalence between (1) and ( 5) can be rephrased as follows. 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.

We will also need the following lemma from [START_REF] Dragan | Centers of Graphs and the Helly Property[END_REF].

Lemma 1. [START_REF] Dragan | Centers of Graphs and the Helly Property[END_REF] For every Helly graph G = (V, E) and every set M ⊆ 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, diam(C M (G)) denotes the diameter of this graph (diam

(C M (G)) = diam C M (G) (G) by this isometricity).
Let δ(G) be the smallest half-integer δ ≥ 0 such that G is δ-hyperbolic. Let γ(G) be the largest integer γ ≥ 0 such that G has a (γ × γ) rectilinear grid as an isometric subgraph. Let β(G) be the smallest integer β ≥ 0 such that all balls in G are β-pseudoconvex. Finally, let κ(G) be the smallest integer κ ≥ 0 such that diam(C M (G)) ≤ κ for every set M ⊆ V .

Theorem 2. For every Helly graph G, a constant bound on one parameter from {δ(G), γ(G), β(G), κ(G)} implies a constant bound on all others.

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 an n-vertex Helly graph. Corollary 3 gives a sublinear bound on the diameter of the center of an n-vertex Helly graph.

Corollary 2. The hyperbolicity of an n-vertex Helly graph G is at most

√ n + 1.

Corollary 3. For any Helly graph

G, diam(C(G)) ≤ 2δ(G) + 1 ≤ 2 √ n + 3.
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 O( √ n) will be very handy. The following results from [START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF], [START_REF] Ducoffe | Distance problems within Helly graphs and k-Helly graphs[END_REF] and [START_REF] Chepoi | Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs[END_REF][START_REF] Dragan | Eccentricity terrain of δ-hyperbolic graphs[END_REF][START_REF] Dragan | Revisiting radius, diameter, and all eccentricity computation in graphs through certificates[END_REF] will be also very useful. Lemma 2. [START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF] 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 O(km) time. Lemma 3. [START_REF] Ducoffe | Distance problems within Helly graphs and k-Helly graphs[END_REF] Let G be an m-edge Helly graph and v be an arbitrary vertex.

There is an 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. [START_REF] Chepoi | Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs[END_REF][START_REF] Dragan | Eccentricity terrain of δ-hyperbolic graphs[END_REF][START_REF] Dragan | Revisiting radius, diameter, and all eccentricity computation in graphs through certificates[END_REF] Let G be an arbitrary m-edge graph and δ be its hyperbolicity. There is an O(δm)-time algorithm which finds in G a vertex c with eccentricity at most rad(G) + 2δ. The algorithm does not need to know the value of δ in order to work correctly. We are now ready to prove our main result of this section.

L i (S) = {v ∈ V : d(v, S) = i}. Note that if i ≤ r -4 √ n -6 ≤ 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), it is sufficient to consider the layers L i (S), for i > r -4 √ n-6.

Set A = i>r-4 √ n-6 L i (S). Since for every v / ∈ S, d(v, c) = d(v, S) + 2 √ n + 3 ≤ r,
we deduce that there are at most (r -2

√ n -3) -(r -4 √ n -6) = 2 √ n + 3 nonempty layers in A.
We will need to consider the "critical band" of all the layers L i (S), for 1 ≤ i ≤ r -4 √ n -6 (all the layers between S and A). We claim that there are at least √ n layers in this band. Indeed, under the above assumption, r > 5 √ n + 6. Then, the number of layers is exactly e(c) -2

√ n -3 > 3 √ n + 3, minus at most 2 √
n + 3 layers most distant from c (layers in A). Overall, there are at least √ n layers in the critical band, as claimed. Then, one layer in the critical band, call it L, contains at most n/ √ n = √ n vertices.

Claim 1 For every a ∈ A, there exists a "distant gate" a * ∈ P r(a, L) with the following property:

N r [a] ∩ S = N r-d(a,L) [a * ] ∩ S.
In order to prove the claim, set p = d(a, L) and q = d(a, c) ≤ r. Let us consider a family of balls

F = {N p [a], N q-p [c]}∪{N r-p [s] : s ∈ N r [a]∩(S \c)}.
We stress that N p [a] ∩ N q-p [c] = P r(a, L). Then, in order to prove the existence of a distant gate, it suffices to prove that the balls in F intersect; indeed, if it is the case then we may choose for a * any vertex in the common intersection of the balls in F. Clearly, N p [a] ∩ N q-p [c] = ∅ and, in the same way,

N p [a] ∩ N r-p [s] = ∅ for each s ∈ N r [a] ∩ (S \ c). Furthermore, since L is in the critical band, d(c, L) > 2 √ n + 3
, and therefore we have for each s, s ∈ S: 2(r -p) ≥ 2(q -p) = 2d(c, L) > diam S (G) ≥ d(s, s ). In the same way (q -p) + (r -p) ≥ 2(q -p) > diam S (G) ≥ d(s, c). The latter proves that the balls in F intersect. This concludes the proof of Claim 1.

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

-We make a BFS from every u ∈ L. it takes O(m|L|) = O(m √ n) time. Doing so, we can compute ∀a ∈ A, P r(a, L), in total O(|A||L|) = O(n √ n) time. -Since A contains at most O( √ n) nonempty layers, then the number of pair- wise distinct distances d(a, L), for a ∈ A, is also in O( √ n).
Call the set of all these distances I A . Then, ∀u ∈ L, and ∀i ∈ I A , we also compute

p(u, i) = |N r-i G [u] ∩ S|.
For that, we consider the vertices u ∈ L sequentially. Recall that we computed 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( √ 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 ∈ L, and so the total running time is

O(n|L|) = O(n √ n).
-Now, in order to compute a distant gate a * , for a ∈ A, we proceed as follows.

Let i = d(a, L). We scan P r(a, L) and we store a vertex a * maximizing p(a * , i).

It takes O(|A||L|) = O(n √ n) time.
On the way, ∀u ∈ L, let q(u) be the maximum i such that a * ≡ u is the distant gate of some vertex a ∈ 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 ∈ S be arbitrary. For having s ∈ S ∩C(G), it is necessary and sufficient to have s ∈ N r [a] ∩ S, ∀a ∈ A. Equivalently, ∀u ∈ L, one must have d(s, u) ≤ r -q(u). This can be checked in time O(|L|) per vertex in S, and so, in total

O(n √ 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(δm) time, where δ is the hyperbolicity of G. This nice result, combined with the property that all Helly graphs have hyperbolicity O( √ n) (Corollary 2), was key to the design of our O(m √ 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 δ 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 δ as the parameter. 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 [START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF][START_REF] Dragan | HT-graphs: centers, connected r-domination and Steiner trees[END_REF][START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF]. 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 [START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF][START_REF] Dragan | HT-graphs: centers, connected r-domination and Steiner trees[END_REF].

The remainder of this section is devoted to proving Theorem 4. For that, the following result is proved in Subsection 4.1: . The latter will happen for some k < 2(2δ + 1) after at most O(log δ) probes. Overall, since we need to apply Lemma 6 at most O(log δ) times, for some values k < 2(2δ + 1), the total running time is O(δ 2 m log δ). If δ (or a constant approximation of it is known), then we call Lemma 6 only once, and therefore the running time goes down to O(δ 2 m).

Proof of Lemma 6

In what follows, G is a Helly graph, k is an integer and r = rad(G). Lemma 2). Thus from now on, r > 2k. As diam S k (G) ≤ 2k, to find all central vertices in S k (i.e., the set C(G) ∩ S k ), we will need to consider only the vertices at distance > r -2k from S k .

Let S k = N k [c]. If r ≤ 2k, we can compute all central vertices in O(km) time (see
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 ∈ V : d(v, S k ) = r -i}). We want to compute S k,i := {s ∈ S

k : A k,i ⊆ N r [s]}. Indeed, C(G)∩S k = 2k-1 i=k S k,i .
The computation of S k,i (for k, i fixed) works by phases. We describe below the two main phases of the process.

First phase of the algorithm. To give the intuition of our approach, we will need the following simple claim. For a vertex v ∈ V and an integer j, let L(v, j, S k ) : 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 ≤ j < r -i, the intermediate output is a collection of disjoint subsets V 1 j , V 2 j , ..., V pj 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 , ..., B pj of A k,i . Specifically, the algorithm ensures that:

= {u ∈ V : d(v, S k ) = d(v, u) + d(u, S k ) and d(v, u) = j}. Claim 2 Let B ⊆ A k,i be such that {L(b, j, S k ) : b ∈ B} = ∅, for some 0 ≤ j < r -i. Then, for every s ∈ S k , max b∈B d(s, b) ≤ r if and only if d(s, {L(b, j, S k ) : b ∈ B}) ≤ r -j. Proof. If d(s, {L(b, j, S k ) : b ∈ B}) ≤ r -j, then max b∈B d(s, b) ≤ r. Con- versely, let us assume max b∈B d(s, b) ≤ r. Set F = {N r-j G [s], N r+k-(i+j) G [c]} ∪ {N j G [b] : b ∈ B}. We prove that the balls in F intersect. For each b, b ∈ B, N j G [b]∩N j G [b ] ⊇ {L(b, j, S k ) : b ∈ B} = ∅. Since we assume max b∈B d(s, b) ≤ r, N j G [b] ∩ N r-j G [s] = ∅. Furthermore, as for each b ∈ B we have d(b, c) = d(b, S k ) + k = r -i + k, we obtain N r-i+k-j G [c] ∩ N j G [b] = L(b, j, S k ) = ∅. Finally, since we have j < r -i, (r -i + k -j) + (r -j) > k + i ≥ k ≥ d(s, c). Therefore, N r+k-(i+j) G [c] ∩ N r-j G [s] = ∅.
∀1 ≤ t ≤ p j , V t j = {L(b, j, S k ) : b ∈ B t } = ∅.
Doing so, by the above Claim 2, for any s ∈ S k we have max z∈A k,i d(s, z) ≤ r ⇐⇒ max 1≤t≤pj d(s, V t j ) ≤ r -j. Initially, for j = 0, every set B t is a singleton. Furthermore, B t = V t 0 . Then, we show how to partition L r-i-(j+1) (S k ) from V 1 j , V 2 j , ..., V pj j in total O( x∈Lr-i-j (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 t j = N (V t j ) ∩ L r-i-(j+1) (S k ). Since the subsets V t j are pairwise disjoint, the construction of the W t j 's takes total O( x∈Lr-i-j (S k ) |N G (x)|) time. Furthermore:

Claim 3 W t j = {L(b, j + 1, S k ) : b ∈ B t }.
Proof. We only need to prove that we have {L(b, j +1, S k ) : b ∈ B t } ⊆ W t j (the other inclusion being trivial by construction). For that, let x ∈ {L(b, j +1, S k Finally, in order to compute the new sets V t j+1 , we proceed as follows. Let W = {W t j : 1 ≤ t ≤ p j }. While W = ∅, we select some vertex x ∈ L r-i-(j+1) (S k ) maximizing #{t : x ∈ W t j }. Furthermore, by maximality of vertex x, t:x∈W t j W t j is disjoint from the subsets in {W t j : x / ∈ W t j }. The latter ensures that all the new sets we create are pairwise disjoint. In order to implement this above process efficiently, we store each x ∈ L r-i-(j+1) (S k ) in a list indexed by #{t : x ∈ W t j }. Then, we traverse these lists by decreasing index. We keep, for each x ∈ 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 [START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF]. The running time is proportional to {|W t (i.e., those obtained at the end of the first phase of our algorithm). Note that C 1 , C 2 , ..., C p are subsets of L 1 (S k ) (= N G (S k )).

Corollary 1 .

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

FirstCorollary 4 .

 4 , by combining Lemmas 3 and 4, we show that a central vertex of a Helly graph G can be computed in O(δm) time, where δ 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 O(δm) time, where δ is the hyperbolicity of G. Proof. We use Lemma 4 in order to find, in O(δm) time, a vertex c of G with eccentricity e(c) ≤ rad(G) + 2δ. Then we apply Lemma 3 at most 2δ times in order to descend from c to a central vertex c * . It takes O(δm) time. Combining this with Corollary 2, we get. For any n-vertex m-edge Helly graph G, a central vertex and the radius of G can be computed in O(m √ n) time.

Theorem 3 .

 3 All vertex eccentricities in an n-vertex m-edge Helly graph G can be computed in total O(m √ n) time. Proof. Our goal is to compute e(v) for every v ∈ V . For that, we first find a central vertex c and compute the radius rad(G) of G, which takes O(m √ n) time by Corollary 4. If rad(G) ≤ 5 √ n + 6 (the choice of this number will be clear later), then diam(G) ≤ 2rad(G) ≤ 10 √ n + 12 and we are done by Lemma 2 (applied for k = 10 √ n + 12); it takes in this case total time O(m √ n) to compute all eccentricities in G. Thus, from now on, we assume rad(G) > 5 √ n + 6. By Theorem 1(3), for every v ∈ 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 ∈ C(G) found earlier, let S = N 2 √ n+3 G [c]. By Corollary 3, C(G) ⊆ S. In what follows, let r = rad(G). Consider the BFS layers

Theorem 4 .

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

Lemma 6 .

 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 2 m)-time algorithm which computesC(G) ∩ 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 ∈ 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(δm) time by Lemma 5.By Corollary 3, we know that diam(C(G)) ≤ 2δ + 1. Therefore, C(G) ⊆ N 2δ+1 [c]. If δ is known to us, we fix k := 2δ + 1 (if only a constant approximation δ ≥ δ of δ is known, we set k = 2δ + 1). Then, we are done applying Lemma 6. Otherwise, we work sequentially with k = 2, 3, 4, 5, 8, 9, . . . , 2 p , 2 p + 1, 2 p+1 , 2 p+1 + 1,. . . , and we stop after finding the smallest integer (power of 2)k such that C(G)∩N k [c] = C(G)∩N k+1 [c]. Indeed,by the isometricity (and hence connectedness) of C(G) in G (see Lemma 1), the set C(G) ∩ N k [c] will contain all central vertices of G, i.e., C(G) ∩ N k [c] = C(G)

  It follows from the above that the balls in F pairwise intersect. By the Helly property, there exists a vertex y in the common intersection of all the balls in F. As for each b ∈ B, y ∈ N r-i+k-j G [c]∩N j G [b] = L(b, j, S k ), we deduce that y ∈ {L(b, j, S k ) : b ∈ B}. Finally, we have d(s, {L(b, j, S k ) : b ∈ B}) ≤ d(s, y) ≤ r -j.

  ) : b ∈ B t } be arbitrary. Recall that we have, for each b ∈ B t , d(b, c) = k+d(b, S k ) = r -i + k. In particular, x ∈ L(b, j + 1, S k ) = L(b, j + 1, c). It implies that the balls in {N G [x], N r-i+k-j G [c]} ∪ {N j G [b] : b ∈ B t } pairwise intersect. By the Helly property, x has a neighbour in N r-i+k-j G [c] ∩ {N j [b] : b ∈ B t } = {L(b, j, S k ) : b ∈ B t } = V t j . Since x ∈ L r-i-(j+1) (S k ), we get that x ∈ W t j .

j | : 1 ≤ 1 , C 2 ,

 112 t ≤ p j } = O( x∈Lr-i-j (S k ) |N G (x)|).Second phase of the algorithm.Let C

  Then, we create a new set t:x∈W t Note that, by the above Claim 3, t:x∈W t

	j	W t j , and we
	remove {W t	j	W t j =

j : x ∈ W t j } from W. t:x∈W t j {L(b, j + 1, S k ) : b ∈ B t } = {L(b, j + 1, S k ) : b ∈ t:x∈W t j B t }.

holds for every set M ⊆ V .

All eccentricities in Helly graphsIt is known that the radius (see[START_REF] Ducoffe | A story of diameter, radius, and (almost) Helly property. Networks[END_REF]) and a central vertex (see[START_REF] Ducoffe | Distance problems within Helly graphs and k-Helly graphs[END_REF]) of an n-vertex m-edge Helly graph can be computed in Õ(m √ n)-time with high probability. In this section, we improve those results by presenting a deterministic O(m √ 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,

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 (

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 ∪ {c}. Set α(c) = k + i + 2 and α(a) = r for each a ∈ A k,i . We define the set Y = {y : ∀x ∈ X, d(y, x) ≤ α(x)}. Observe that S k,i = Y ∩ S k (recall that S k,i was defined as {s ∈ S k : A k,i ⊆ 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 , for 0 ≤ ≤ i + 1, we maintain a family of nonempty pairwise disjoint sets Z 1 , Z 2 , ..., Z q and a covering X 1 , X 2 , . . . , X q of X such that the following is true: for every 1

. 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 1 i+1 . Initially, for = 0, we start from Z 1 0 = C 1 , ..., Z p 0 = C p , and then the corresponding covering is ∀1 ≤ t ≤ p, X t 1 = B t ∪ {c} (with B 1 , B 2 , ..., 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 to + 1, we proceed as we did during the first phase. Specifically, for every t, let U t = N G [Z t ]. Since the sets Z t are pairwise disjoint, the computation of all the intermediate sets U t takes total O(m) time.

The proof is similar to that of Claim 3. Finally, in order to compute the new sets Z t +1 , let U = {U t : 1 ≤ t ≤ q }. While U = ∅, we select some vertex u ∈ V maximizing #{t : u ∈ U t }. Then, we create a new set t:u∈U t U t , and we remove {U t : u ∈ U t } from U. The running time is proportional to

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 2 m).