∗

A story of diameter, radius and (almost) Helly property

Guillaume Ducoffe1,2 and Feodor F. Dragan3
1
University of Bucharest, Romania
2
National Institute for Research and Development in Informatics, Romania
3
Computer Science Department, Kent State University, Kent, Ohio, USA

Abstract
We present new algorithmic results for the class of Helly graphs, i.e., for the discrete ana-
logues of hyperconvex metric spaces. Specifically, an undirected unweighted graph is Helly if
every family of pairwise intersecting balls has a nonempty common intersection. It is known
that every graph isometrically embeds into a Helly graph, that makes of the latter an important
class of graphs in Metric Graph Theory. We study diameter and radius computations within the
Helly graphs, and related graph classes. This is in part motivated by a conjecture on the fine-
grained complexity of these two distance problems within the graph classes of bounded fractional
Helly number — that contain as particular cases the proper minor-closed graph classes and the
bounded clique-width graphs. Note that 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, we first present algorithms which given an n-vertex
m-edge Helly graph √ G as input, compute with high probability (w.h.p.) its radius and its
diameter in Õ(m n) time (i.e., subquadratic in n + m). Our algorithms are based on the
Helly property and on the unimodality of the eccentricity function in Helly graphs: every
vertex of locally minimum eccentricity is a central vertex.
• Then, we improve our results for the C4 -free Helly graphs, that are exactly the Helly graphs
whose balls are convex. For this subclass, we present linear-time algorithms for computing
the eccentricity of all vertices. Doing so, we generalize previous results on strongly chordal
graphs to a much larger subclass, that includes, among others, all the bridged Helly graphs
and the hereditary Helly graphs.
• Lastly, we derive approximate versions of our results for the class of chordal graphs: with
the latter satisfying an almost-Helly-type property, and a stronger (induced-path) convex-
ity property than the C4 -free Helly graphs. For the chordal graphs, we can compute in
quasi linear time the eccentricity of all vertices with an additive one-sided error of at most
one, which is best possible under the Strong Exponential-Time Hypothesis (SETH). This
answers an open question of [Dragan, IPL 2019]. In fact, we obtain this last result as a
byproduct from a more general reduction: from diameter computation on chordal graphs
to the Disjoint Sets problem. Roughly, it implies that the split graphs are the only hard
instances for diameter computation on chordal graphs. We also get from our reduction
that on any subclass of chordal graphs with constant VC-dimension(and so, for undirected
path graphs), the diameter can be computed in truly subquadratic time.
∗
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, and by a grant of Romanian Ministry of Research and Innovation CCCDI-UEFISCDI.
project no. 17PCCDI/2018.

1
1 Introduction
For any undefined graph terminology, see [9]. Given an undirected unweighted graph G, the distance
distG (u, v) between two vertices u and v is the minimum number of edges on a uv-path. The
eccentricity eG (u) of a vertex u is the maximum distance from u to every other vertex. The radius
and the diameter of G, denoted rad(G) and diam(G), respectively, are the smallest and the largest
eccentricities of a vertex in G, respectively. We study the fundamental problems of computing the
diameter and the radius. There is a textbook algorithm for both problems, running in O(nm) time
on n-vertex m-edge graphs. However, it is a direct reduction to All-Pairs Shortest-Paths (APSP),
that is a seemingly more complex problem with a much larger (quadratic-size) output than for the
diameter and radius problems. As a continuous attempt 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 representations and/or some forbidden pattern (e.g., excluding a minor, or a family of
induced subgraphs). A typical such example is the class of interval graphs, a.k.a. the intersection
graphs of intervals on the real line [40, 58]. See [14, 27, 32, 44, 46, 48] for other examples.
We here study the Helly graphs as a broad generalization of interval 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 as the Helly property in what follows. We
believe that studying which of the many nice properties of the interval graphs leads to fast diameter
and radius computations is an interesting research topic on its own. This is especially so because
the interval graphs are less structured than most “easy” graph classes for diameter and radius
computations (i.e., they have unbounded treewidth and clique-width, and they do not exclude
any fixed minor). The Helly graphs, sometimes called absolute retracts or disk-Helly graphs (by
opposition to other Helly-type properties on graphs [33]) are well studied in Metric Graph Theory.
E.g., see the survey [2] 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 [42, 54]. In particular, let us consider the family of cycles. We denote
by Ck the cycle of length k. Although there are very simple graphs that are not Helly, such as (to
be provoking) C6 , every graph that contains a C6 is a distance-preserving subgraph of some Helly
graph. It implies that the Helly graphs cannot be characterized via some forbidden structure —
unlike the subclass of the interval graphs, that do exclude some infinite family of induced subgraphs.
Polynomial-time recognition algorithms for the Helly graphs were presented in [4, 34, 56], as well
as several structural properties of these graphs in [4, 5, 6, 21, 34, 35, 38, 59, 60]. 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 [14, 16, 41, 36, 38]. In particular, the diameter
and the radius of a dually chordal graph can be computed in linear time, that is optimal. However,
to the best of our knowledge it was open until this paper whether there are truly subquadratic-time
algorithms for these two problems on Helly graphs.

Related work Chordal graphs (graphs with no induced cycles of length > 3) are another impor-
tant generalization of interval graphs, with several nice geometric characterizations. E.g., they are
exactly the graphs whose balls are m-convex, i.e., such that every induced path between two ver-
tices in a ball is fully contained in this ball [47]. Furthermore, while not all chordal graphs are Helly,
they satisfy a very similar property: for any family of pairwise intersecting balls in a chordal graph,

2
there exists a vertex at distance at most some constant to all balls in the family (this result holds,
more generally, for every class of graphs with bounded hyperbolicity [28]). Chepoi and Dragan
proposed an elegant linear-time algorithm for computing a central vertex in a chordal graph [23].
However, they observed that 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 [22]. Under the Strong Exponential-Time Hypothesis (SETH), we cannot solve
Disjoint Sets in truly subquadratic time [68], and so neither we can compute the diameter of
split graphs [10] (see also [61] whose authors were the first to prove such a SETH-hardness result for
general graphs). It was also observed in [26] that assuming the so-called Hitting Set Conjecture
(HS), the reduction from [1] implies that the radius of a 2-hyperbolic graph cannot be computed
in truly subquadratic time. Therefore, the naive algorithm for radius and diameter computations
is conditionally optimal already for very simple graph classes from a metric point of view. On the
positive side, there exist linear-time algorithms for computing the diameter on various subclasses of
chordal graphs, e.g., interval graphs, directed path graphs and strongly chordal graphs [14, 30, 40].
Most of these special cases, including the three aforementioned examples, are strict subclasses of
chordal Helly graphs. As a result, our work pushes forward the tractability border for diameter
computation on chordal graphs and beyond.
More generally, this paper is part of a recent series of articles, with co-authors, where we try to
understand the role of abstract geometric properties, and of tools and concepts from Computational
Geometry, in the fast computation of metric graph invariants [43, 44, 45]. In this respect, Cabello
and Knauer showed in [20] how to use a standard data-structure for orthogonal range searching
in order to compactly represent the distances in a bounded-treewidth graph. Their approach
became the cornerstone of conditionally optimal algorithms for diameter computation on bounded-
treewidth graphs and other graph classes [1, 17, 43, 45]. Then in another seminal paper [19], Cabello
introduced a new framework based on abstract Voronoi diagrams in order to compute the diameter
of planar graphs in truly subquadratic time. See also [50] for improvements upon his work. Perhaps
surprisingly, both planar graphs and bounded-treewidth graphs are particular cases of a large family
of geometric graph classes, namely the graphs of bounded distance VC-dimension (with the latter
parameter being defined, for any graph G, as the VC-dimension of its ball hypergraph). This was
first proved by Chepoi et al. for the superclass of Kh -minor free graphs, which combined with a
fractional Helly property of all spaces of constant VC-dimension [57], allowed them to cover any
planar graph of diameter 2R with a constant number of balls of radius R [29]. – Recall that a class
H of hypergraphs has fractional Helly number at most k if for any positive α there is some positive
β such that, in any subfamily of hyperedges in a hypergraph of H, if there is at least a fraction α of
all the k-tuples of hyperedges with a non-empty common intersection, then there exists an element
that is contained in a fraction at least β of all hyperedges in this subfamily. Then, the fractional
Helly number of a graph class G is the fractional Helly number of the family of the ball hypergraphs
of all graphs in G. – Later the results of Chepoi et al. were extended to all hereditary graph classes
of constant distance VC-dimension [11, 13]. From the algorithmic side, it was proved in [45] that on
all proper minor-closed graph classes, and several other classes of bounded distance VC-dimension,
the diameter can be computed in truly subquadratic time. Seeking for a common property of
these graphs and of dually chordal graphs, we ask whether the diameter can be computed in truly
subquadratic time on every graph class with a fractional Helly property. As a first step toward
resolving this difficult question, our current research focuses on the simpler class of Helly graphs.

3
Our Contributions We present truly subquadratic-time algorithms for computing both the
radius and the diameter of Helly graphs (Theorem 4). In fact, for the Helly graphs, it is sufficient
to compute the diameter in order to derive the radius [34]. Note that such a property is not known
to hold for general graphs. Nevertheless, we present separate algorithms for diameter and radius
computations. Indeed, our approach for computing the radius can be applied to a broader class
than the Helly graphs, both as an exact and approximation algorithm. Our algorithms run in time
√
Õ(m n) w.h.p., and they use as their main ingredients several consequences of the unimodality of
the eccentricity function in Helly graphs [34]: every local minimum of the eccentricity function in
a Helly graph is a global minimum.
Then, in light of the gap between our running times and the known linear-time algorithms for
the dually chordal graphs, we studied whether stronger complexity results could hold true on more
restricted subclasses, such as chordal Helly graphs or, more generally, C4 -free Helly graphs. This
latter choice was also partly motivated by a nice characterization of hereditary Helly graphs: indeed,
they are exactly the 3-sun-free chordal graphs [34]. We stress that the C4 -free Helly graphs have
been studied on their own and that they have more interesting convexity properties than general
Helly graphs [34, 35]. In particular, the center C(G) of a C4 -free Helly graph G is convex and it
has diameter at most 3 and radius at most 2 [34, 35]. In contrast, the center C(G) of a general
Helly graph G is isometric but it can have arbitrarily large diameter; in fact, any Helly graph H is
the center of some other Helly graph G [34]. For the C4 -free Helly graphs, we are able to compute
the eccentricity of all vertices in linear time (Theorem 7), which for Helly graphs can be reduced
to computing the graph center. Our starting point for that is the well-known multi-sweep heuristic
of Corneil et al. [30], in order to compute vertices of provably large eccentricity. – As notified to us
by Chepoi (private communication), this heuristic can be arbitrarily bad for general Helly graphs,
that can be deduced from a careful analysis of the embedding method of arbitrary graphs into Helly
graphs [42, 54]. – Our approach is partly inspired by the algorithms of Chepoi and Dragan [23] and
Dragan and Nicolai [39], in order to compute a central vertex in chordal graphs and a diametral
pair in distance-hereditary graphs, respectively. Nevertheless, extending such ideas to the C4 -free
Helly graphs required us to prove several new nontrivial properties for this class. In particular, it
led us to a reduction from finding a diametral pair under some technical assumptions to the same
problem on split Helly graphs.
Finally, in light of this above reduction, we studied whether there are other graph classes where
the diameter can be efficiently computed from a subfamily of split graphs. In particular, can we
reduce diameter computation on general chordal graphs to the same problem on split graphs? This
would imply that the subclass of split graphs is, in some sense, the sole hard case for diameter
computation on chordal graphs. Furthermore, beyond the case of chordal Helly graphs, this could
help in finding new subclasses of chordal graphs for which we can compute the diameter faster than
in O(nm) time. We prove a slightly weaker result, namely, a reduction from diameter computation
on chordal graphs to Disjoint Sets (Theorem 8). As a byproduct of our reduction, we prove
that the diameter can be computed in truly subquadratic time on any subclass of chordal graphs
with constant VC-dimension (Theorem 10). This nicely complements the results from [45], which
mostly apply to sparse graph classes of constant distance VC-dimension or assuming a bounded
(sublinear) diameter. In particular, our result in this paper can be applied to undirected path graphs
since they have VC-dimension at most 3 [12]. Before our work, only a linear-time algorithm for
the subclass of directed path graphs was known [30]. Another application of our reduction is the
approximate computation in quasi linear time of the eccentricity of all vertices in a chordal graph

4
with an additive one-sided error of at most 1. The latter result answers an open question from [37].

Notations. We recall that we denote by distG (u, v) the distance between vertices u and v. The
metric interval IG (u, v) between u and v is defined as {w ∈ V | distG (u, w) + distG (w, v) =
distG (u, v)}. For any k ≤ distG (u, v), we can also define the slice L(u, k, v) := {w ∈ IG (u, v) |
distG (u, w) = k}. The ball of radius r and center v is defined as {u ∈ V | distG (u, v) ≤ r}, and
denoted NGr [v]. In particular, NG [v] := NG1 [v] and NG (v) := NG [v] \ {v} denote the closed and
open neighbourhoods of a vertex v, respectively.S More generally, for any vertex-subset S we define
r r
distG (u, S) := minv∈S distG (u, v), NG [S] := v∈S NG [v], NG [S] := NG1 [S] and NG (S) := NG [S]\S.
The metric projection of a vertex u on S, denoted P rG (u, S), is defined as {v ∈ S | distG (u, v) =
distG (u, S)}. Recall that the eccentricity of a vertex u is defined as maxv∈V distG (u, v) and denoted
by eG (u). We define the set FG (u) := {v ∈ V | distG (u, v) = eG (u)} of all the farthest vertices from
vertex 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. Finally,
C(G) := {v ∈ V | e(v) = rad(G)} is the center of G, a.k.a. the set of all the central vertices of G.

2 Fast Computations within Helly graphs

The main result in this section is a truly subquadratic algorithm for computing the diameter of a
Helly graph (Theorem 4). By the following Lemma 1, it can be easily turned into a subquadratic
algorithm for radius computation:
Lemma 1 ([34]). If G is a Helly graph then 2rad(G) ≥ diam(G) ≥ 2rad(G) − 1. In particular,
rad(G) = ddiam(G)/2e.
Section 2.1 is devoted to a subquadratic-time randomized algorithm for radius computation,
that can be turned to an exact or approximation algorithm for larger classes than the Helly graphs
(namely, in every class where the diameter equals twice the radius, up to some additive constant).
Then, we combine this approach with several other technical arguments in order to prove our
Theorem 4 (cf. Section 2.2).

2.1 Radius computation

We start this section with a simple randomized test, which is inspired from previous works on
adaptive greedy set cover algorithms [64].
Lemma 2. Let G = (V, E) be a graph, let r be a positive integer and let ε ∈ (0; 1). There is an
algorithm that w.h.p. computes a set DhG; r; εi in Õ(m/ε) time with the following two properties:
• if e(v) ≤ r then v ∈ DhG; r; εi;

• conversely, if v ∈ DhG; r; εi then |N r [v]| ≥ (1 − ε) · n.

Proof. Let p = c · log n log n
εn for some arbitrary large constant c. If p ≥ 1 then n ≤ c ε , and so
we can compute the set of all the vertices of eccentricity at most r in time Õ(m/ε) by running
a BFS from every vertex. From now on we assume that p < 1. By U (p) we mean a subset
in which every vertex was added independently at random with probability p. Observe that we
have E[|U (p)|] = c logε n > c · log n. By Chernoff bounds we get |U (p)| = Õ(ε−1 ) with probability

5
≥ 1 − n−c . Then, for every v ∈ V , we compute N r [v] ∩ U (p). For that, we run a BFS from
every vertex of U (p), that takes total time Õ(m/ε). We divide our analysis in two cases. First
let us assume that e(v) ≤ r. Then, with probability 1 we have U (p) ⊆ N r [v]. Second, let us
1
·c log n
assume that |N r [v]| < (1 − ε) · n. We get P rob[U (p) ⊆ N r [v]] < (1 − p)εn = (1 − p) p ≤ n−c .
r
Overall, let DhG; r; εi contain all the vertices v such that U (p) ⊆ N [v]. By a union bound over
at most n vertices, the set DhG; r; εi satisfies our two above-stated properties with probability
≥ 1 − n−(c−1) .

We derive from this simple test above an approximation algorithm for computing the radius
and the diameter, namely:

Lemma 3. Let G = (V, E) be a graph and r be a positive integer. There is an algorithm that w.h.p.
√
runs in Õ(m n) time and such that:

• If the algorithm accepts then diam(G) ≤ 2r;

• If the algorithm rejects then rad(G) > r.

Note that since diam(G) ≤ 2rad(G), this algorithm rejects any graph G with diam(G) > 2r.
However, it might also reject some graphs G such that diam(G) ≤ 2r but rad(G) > r.

Proof. For some ε to be defined later, we construct a set DhG; r; εi as in Lemma 2. W.h.p. it
takes time Õ(m/ε). There are two cases. If DhG; r; εi = ∅ then we know that rad(G) > r and we
stop. Otherwise, we pick any vertex c ∈ DhG; r; εi and we compute N r [c]. Here it is important to
observe that all the vertices of N r [c] are pairwise at a distance ≤ 2r. Furthermore, w.h.p. we have
|V \ N r [c]| ≤ ε · n. We end up computing a BFS from every vertex of V \ N r [c], accepting in the
end if and only if all these vertices have eccentricity ≤ 2r. By setting ε = n−1/2 , the total running
√
time is w.h.p. in Õ(m n).

An important consequence of Lemma 3 is that the hard instances for diameter and radius
approximations are those for which the difference 2rad(G) − diam(G) is large, namely:

Corollary 1. If 2rad(G) − diam(G) ≤ k then, w.h.p., we can compute an additive + bk/2c-

√
approximation of rad(G) and an additive +k-approximation of diam(G) in total Õ(m n) time.

Proof. We compute by dichotomic search the smallest

l r such mthat the algorithm of Lemma 3 accepts.
Note that w.h.p. r ≥ ddiam(G)/2e, and so r ≥ 2rad(G)−k
2 = rad(G) − bk/2c. Furthermore, we
have w.h.p. r ≤ rad(G), and so, 2r ≤ diam(G) + k. We output r and 2r as approximations of
rad(G) and diam(G), respectively.

Application to Helly graphs. By combining Lemma 1 with Corollary 1, we finally obtain the
main result of this section, namely:

Theorem 1. If G is a Helly graph then, w.h.p., we can compute rad(G) and an additive +1-
√
approximation of diam(G) in time Õ(m n).

We observe that one cannot compute a central vertex in a Helly graph by using our approach
in this section. This issue is resolved, in Sec. 3.1, for the subclass of C4 -free Helly graphs.

6
2.2 Diameter computation
We continue with a parameterized algorithm for computing all eccentricities up to some threshold
value in a Helly graph G. We recall that we denote by NGr [v] the ball of radius r and center v.

Problem 1 (Small Eccentricities).

Input: a graph G = (V, E); a vertex-subset A; a positive integer k.

Output: the set Bk := {b ∈ V | A ⊆ N k [b]}.

We note that already for k = 2, Problem 1 is unlikely to be solvable in truly subquadratic time.
Indeed, this special case is somewhat related to the Hitting Set problem [1]. We explain next
how to solve this problem in parameterized linear time when G is a Helly graph.
Theorem 2. If G is Helly then, for every subset A and every positive integer k, we can solve
Small Eccentricities in O(km) time.
Proof. We reduce the problem to the construction of a partition PAk = (Ak1 , Ak2 , . . . , Akpk ) of A, for
some arbitrary pk =def |PAk | ≤ |A|, with the following two properties:
• for every 1 ≤ j ≤ pk , we have ∩{N k [a] | a ∈ Akj } = Vjk 6= ∅;

• furthermore, the sets V1k , V2k , . . . , Vpkk are pairwise disjoint.

Indeed, observe that we have Bk 6= ∅ if and only if pk = 1, and in such a case Bk = V1k . It now
remains to prove that we can construct the partition PAk , and the associated sets Vjk , in O(km)
time. If k = 0, then we set PA0 = A and we are done (notice that for every aj ∈ A, the corresponding
set Vj0 is exactly the singleton {aj }). Otherwise, we show how to construct PAk and its associated
sets from PAk−1 and the Vjk−1 ’s, in linear time. For that, let us define for every j the new subset
Wjk := N [Vjk−1 ]. Notice that constructing the sets Wjk takes total linear time as by the hypothesis,
the sets Vjk−1 are pairwise disjoint. However, we may have Wjk ∩ Wjk0 6= ∅ for some j 6= j 0 .

Claim 1. Wjk = {N k [a] | a ∈ Ak−1

T
j }.

Proof. Since Vjk−1 = {N k−1 [a] | a ∈ Ak−1 }, Wjk ⊆ {N k [a] | a ∈ Ak−1

T T
j j }. Conversely, let
T k k−1 k−1 k−1
v ∈ {N [a] | a ∈ Aj } be arbitrary. Since N [v] and N [a], ∀a ∈ Aj pairwise intersect, by
k−1 k
the Helly property, N [v] ∩ Vj 6= ∅, proving that v ∈ Wj . 
We are left with computing the Vjk ’s from the Wjk ’s. For that, we need the following additional
result:
Claim 2. Let v ∈ V be such that #{j | v ∈ Wjk } is maximized. For any j 0 such that v ∈ / Wjk0 , we
have Wjk0 ∩ {Wjk | v ∈ Wjk } = ∅.
T

Proof. Suppose by contradiction that there is a vertex u ∈ Wjk0 ∩ {Wjk | v ∈ Wjk }. Then,
T

{j | v ∈ Wjk } ⊂ {j 0 | u ∈ Wjk0 }. However, this contradicts the maximality of vertex v. 

We now proceed as follows in order to compute PAk and the Vjk ’s. Let Fk be an empty family
of sets (we shall get Fk = (V1k , V2k , . . . , Vpkk ) at the end of this sub-procedure below). While

7
PAk−1 6= ∅ we pick a vertex v ∈ V such that #{j | v ∈ Wjk } is maximized. We add the new sets
Av := {Ak−1 | v ∈ Wjk } and {Wjk | v ∈ Wjk }, in the families PAk and Fk , respectively. Indeed,
S T
j
by Claim 1, {N k [a] | a ∈ Av } = {Wjk | v ∈ Wjk }. Then, we remove from PAk−1 every Ak−1
T T
j such
k
that v ∈ Wj . By Claim 2, the sets in Fk are pairwise disjoint. Finally, in order to construct Fk
efficiently, during a pre-processing step we compute #{j | v ∈ Wjk } for every vertex v. Since the
Wjk ’s can be constructed in total linear time, this pre-processing also takes linear time. We create
an array of |PAk−1 | lists, where ∀i the ith list contains all the vertices that are in exactly i subsets
Wjk (these lists are dynamically updated throughout the algorithm). We also need that, for every
vertex v, we can enumerate all the subsets Wjk such that v ∈ Wjk in time linear in the size of the
output (i.e., in O( {|Wjk | | v ∈ Wjk }) time). For that, it suffices to maintain the incidence graph
P

between V and the groups Wjk . Then, starting from i = |PAk−1 |, if the ith list is empty then i := i−1.
Otherwise, we can pick any vertex v of this list as it maximizes #{j | v ∈ Wjk }. In this latter case
the total running time of the step (including the lists updates) is in O( j|v∈W k |Ak−1 | + |Wjk |).
P
j j
Since all the subsets Ajk−1 ,
such that v ∈ Wjk ,
are subsequently removed from PAk−1 ,
after this step
k k−1 k−1
v is no more contained in a group Wj , for any Aj ∈ PA and so it will never be used again
during the sub-procedure. Overall, the running time is in O( j |Ajk−1 | + |Wjk |) = O(n + m).
P

Corollary 2. For any Helly graph G and positive integer k, we can compute the set of all the
vertices of eccentricity at most k in O(km) time.

Proof. It suffices to apply Theorem 2 with A = V .

If the diameter of a Helly graph is sublinear in the number of nodes, then by the above the
eccentricity of all vertices can be computed in subquadratic time. However, there exist very simple
Helly graphs, such as paths, for which the diameter is linear in the number of nodes. For such “giant-
diameter” Helly graphs, we next adapt a well-known sampling technique for distance oracles [8].
Recall that a function is called unimodal if every its local minimum is global. It was proved in [34]
that the eccentricity function in Helly graphs is unimodal, and that the latter implies the following
interesting property:

Lemma 4 ([34]). If G is Helly then, for every vertex v, e(v) = dist(v, C(G)) + rad(G).

Theorem 3. Let G be a Helly graph such that rad(G) > 3k = ω(log n). Then w.h.p. in Õ(mn/k)
time, we can compute a diametral pair for G.

Proof. Let p = c logk n for some sufficiently large constant c. Since we assume k = ω(log n), for
sufficiently large n we have p < 1. We construct a subset U (p) where every vertex is included
independently with probability p. By Chernoff bounds we have |U (p)| = Õ(n/k) w.h.p., and we
assume from now on that it is indeed the case. We perform a BFS from every vertex in U (p), in total
Õ(mn/k) time. Then, we define for every vertex v ∈ V : ē(v) := minu∈U (p)|dist(u,v)≤k dist(u, v)+e(u)
(by convention, ē(v) = 0 if every vertex of U (p) is at distance > k from v). We now divide our
analysis in two cases:

• Case e(v) < rad(G) + k. Then, for any u ∈ U (p) such that dist(u, v) ≤ k, we get e(u) ≤
e(v) + k < rad(G) + 2k. Hence, ē(v) < rad(G) + 3k ≤ 2 · rad(G) − 1. By Lemma 1, we get
that ē(v) < diam(G) with probability 1.

8
 • Case e(v) ≥ rad(G) + k. Note that in particular, we always fall in this case if v is an end of
a diametral path. Let us consider the set Sv of the k first vertices on a fixed shortest path
between v and a closest vertex of C(G). By Lemma 4, e(v) = dist(v, C(G)) + rad(G). In
particular, for every u ∈ Sv we have e(v) = dist(u, v) + e(u). If U (p) ∩ Sv 6= ∅, then this
implies ē(v) = e(v). Therefore, we are left proving that w.h.p., U (p) ∩ Sv 6= ∅. That is indeed
c log n
the case since P rob[U (p) ∩ Sv = ∅] = (1 − p)|Sv | = (1 − p)k = (1 − p) p ≤ n−c .

Altogether combined, w.h.p., a vertex v maximizing ē(v) is an end of a diametral path.

Combining Theorem 2 and Theorem 3, we finally obtain our main result, namely:
√
Theorem 4. A diametral pair in a Helly graph can be computed w.h.p. in Õ(m n) time.
√
Proof. Let k = 6 d ne. By Corollary 2 we can compute the set Bk of all the vertices of eccentricity
√
at most k in O(mk) = O(m n) time. There are now two cases. First assume that Bk = V . We can
compute by dichotomic search the smallest d ≤ k such that Bd = V , which is exactly the diameter,
√
in Õ(m n) time. Then, a vertex is an end of a diametral path if and only if it is in V \ Bd−1 , and
√
by Corollary 2 we can enumerate all such vertices in O(md) = O(m n) time. Otherwise, Bk 6= V ,
√
and so, diam(G) > k. Note that it implies rad(G) > k/2 ≥ 3 n. By Theorem 3, we can compute
√ √
a diametral pair of G w.h.p. in time Õ(mn/ n) = Õ(m n).

3 Journey to the Center of C4 -free Helly graphs

We now improve our results from Sec. 2, for the class of C4 -free Helly graphs.

3.1 Computing a central vertex

We start with general properties of Helly graphs and C4 -free Helly graphs which we will then use
in our analysis. The first such property is a consequence of the unimodality of the eccentricity
function in Helly graphs (see [34]). In what follows, recall that the metric interval IG (u, v) between
u and v is defined as {w ∈ V | distG (u, w) + distG (w, v) = distG (u, v)}. For any k ≤ distG (u, v), let
L(u, k, v) := {w ∈ IG (u, v) | distG (u, w) = k}. Finally, let FG (u) := {v ∈ V | distG (u, v) = eG (u)}
contain all the farthest vertices from vertex u.

Lemma 5 ([34]). Let G be a Helly graph. Then, for any vertex v of G and any farthest vertex
u ∈ F (v) we have L(u, rad(G), v) ∩ C(G) 6= ∅.

Pseudo-modular graphs are exactly the graphs where each family of three pairwise intersecting
balls has a common intersection [3]. Clearly, Helly graphs is a subclass of pseudo-modular graphs.

Lemma 6 ([3]). For every three vertices x, y, z of a pseudo-modular graph G there exist three
shortest paths P (x, y), P (x, z), P (y, z) connecting them such that either (1) there is a common
vertex v in P (z, y) ∩ P (x, z) ∩ P (x, y) or (2) there is a triangle 4(x0 , y 0 , z 0 ) in G with edge z 0 y 0 on
P (z, y), edge x0 z 0 on P (x, z) and edge x0 y 0 on P (x, y) (see Fig. 1). Furthermore, (1) is true if and
only if d(x, y) = p + q, d(x, z) = p + k and d(y, z) = q + k, for some k, p, q ∈ N, and (2) is true if
and only if d(x, y) = p + q + 1, d(x, z) = p + k + 1 and d(y, z) = q + k + 1, for some k, p, q ∈ N.

9
 x x

x′
v
z′ y′
z y z y

Figure 1: Vertices x, y, z and three shortest paths connecting them in pseudo-modular graphs.

The next properties are specific to C4 -free Helly graphs. A set S ⊆ V of a graph G = (V, E) is
called convex if for every x, y ∈ S, I(x, y) ⊆ S holds.

Lemma 7 ([35]). Every ball of a C4 -free Helly graph is convex.

Lemma 8. For every vertices v and u of a C4 -free Helly graph G and any integer k ≤ dist(u, v),
the set L(u, k, v) is a clique.

Proof. Consider any two vertices x, y ∈ L(u, k, v) and assume that they are not adjacent. Let
` = dist(x, y) ≥ 2. Consider balls N 1 [x], N `−1 [y] and N k−1 [u] in G. Since we have dist(x, y) = ` =
1 + (` − 1), dist(x, u) = k = 1 + (k − 1) and dist(y, u) = k ≤ (` − 1) + (k − 1) (i.e., because we
assume ` ≥ 2), these balls pairwise intersect. By the Helly property, there must exist a vertex z
on a shortest path from x to y which is at distance at most k − 1 from u. As by Lemma 7 the ball
N dist(v,x) [v] is convex, z must belong to N dist(v,x) [v]. Thus, dist(u, v) ≤ dist(u, z) + dist(z, v) ≤
k − 1 + dist(v, x) = dist(u, v) − 1, and a contradiction arises.

The multi-sweep heuristic consists in performing a BFS [31] from an arbitrary vertex v, then
from a farthest vertex u from v, and finally to output e(u) as an estimate of diam(G). On many
graph classes it gives us a constant additive approximation of the diameter [25, 30, 31, 34]. We
prove that it is the case for C4 -free Helly graphs.

Lemma 9. Let G be a C4 -free Helly graph with diameter d and radius r. Let s be an arbitrary
vertex, v be a vertex most distant from s, and (x, y) be a diametral pair of G. Then, e(v) ≥ d − 2.
Furthermore, if e(v) = d − 2, then e(v) = 2r − 3 = dist(v, x) = dist(v, y) and d = 2r − 1. So, in
particular, if e(v) is even, then e(v) ≥ d − 1.

Proof. By Lemma 1, d is either 2r or 2r − 1. Let ` = e(s) = dist(s, v). For vertices s, v, x, y of

G, we have dist(x, y) = d, dist(s, x) ≤ dist(s, v) = `, dist(s, y) ≤ dist(s, v) = `. Furthermore, the
three of dist(v, x), dist(v, y) and dist(s, v) = ` are at most e(v).
First we show that, if max{dist(v, y), dist(v, x)} ≤ 2k for some integer k, then d ≤ 2k + 1. By
the triangular inequality, we may assume that we have 2k ≤ 2e(s) = 2`. Consider balls N `−k [s],
N k [v], N k [y] in G. As dist(v, y) ≤ 2k and dist(s, y) ≤ `, those balls pairwise intersect. By the
Helly property, there is a vertex a in G belonging to all three balls. Necessarily, dist(a, s) = ` − k,
dist(a, v) = k and dist(a, y) ≤ k. Similarly, we can get a vertex b in G such that dist(b, s) = ` − k,
dist(b, v) = k and dist(b, x) ≤ k. As both a and b are in L(v, k, s), by Lemma 8, dist(a, b) ≤ 1.
Thus, d = dist(x, y) ≤ dist(x, b) + dist(b, a) + dist(a, y) ≤ 2k + 1.
Now, if e(v) = 2k for some integer k, then max{dist(v, y), dist(v, x)} ≤ e(v) = 2k and, therefore,
d ≤ 2k + 1 = e(v) + 1. If e(v) = 2k + 1 for some integer k, then either max{dist(v, y), dist(v, x)} <
e(v) = 2k + 1 and hence d ≤ 2k + 1 = e(v) or max{dist(v, y), dist(v, x)} = e(v) = 2k + 1. As in
the latter case max{dist(v, y), dist(v, x)} < 2k + 2, we also get d ≤ 2k + 3 = e(v) + 2.

10
 In what follows, we consider this case, when e(v) = 2k + 1 = max{dist(v, y), dist(v, x)}, in
more details. If d is even (i.e., d = 2r), then d ≤ 2k + 2 and therefore d ≤ e(v) + 1. Assume now
that d is odd (i.e., d = 2r − 1) and that d = e(v) + 2 = 2k + 3 = 2r − 1. That is, r = k + 2.
We will show that, under these conditions, dist(v, y) = dist(v, x) = 2k + 1 must hold. For that
assume w.l.o.g. that dist(v, y) = max{dist(v, y), dist(v, x)} = 2k + 1. Since v ∈ F (s), we have that
dist(s, y) ≤ ` = dist(s, v). Furthermore, by the triangular inequality, we have 2k + 1 = dist(v, y) ≤
dist(v, s)+dist(s, y) ≤ 2e(s) = 2`, and so ` ≥ k +1. We shall use the following intermediate results:

• If dist(s, y) = ` then, by Lemma 6, there is a triangle 4(v 0 , s0 , y 0 ) in G such that dist(s, s0 ) =

` − k − 1, dist(v 0 , v) = dist(y, y 0 ) = k. Necessarily, v 0 ∈ L(v, k, s) and s0 ∈ L(v, k + 1, s).

• If dist(s, y) ≤ ` − 1, consider balls N `−k−1 [s], N k+1 [v], N k [y] in G. As these balls pairwise
intersect, by the Helly property, there is a vertex a in G with dist(a, s) = `−k −1, dist(a, v) =
k + 1 and dist(a, y) = k. That is, a ∈ L(v, k + 1, s).

• If dist(v, x) ≤ 2k then, as before, we can get a vertex b in G with dist(b, s) = `−k, dist(b, v) =
k and dist(b, x) ≤ k. Necessarily, b ∈ L(v, k, s).

Summarizing, we get the following combinations. If dist(v, y) = 2k + 1, dist(v, x) ≤ 2k and

dist(s, y) = `, then d = dist(x, y) ≤ dist(x, b) + dist(b, v 0 ) + dist(v 0 , y 0 ) + dist(y 0 , y) ≤ k + 1 + 1 + k =
2k+2 (notice that, by Lemma 8, dist(b, v 0 ) ≤ 1), contradicting with d = 2k+3. If dist(v, y) = 2k+1,
dist(v, x) ≤ 2k and dist(s, y) ≤ ` − 1, then d = dist(x, y) ≤ dist(x, b) + dist(b, a) + dist(a, y) ≤
k + 2 + k = 2k + 2 (notice that, by Lemma 8, dist(b, a) ≤ 2 as a ∈ L(v, k + 1, s) and b ∈ L(v, k, s)),
contradicting with d = 2k + 3.
Hence, dist(v, x) = 2k + 1 = dist(v, y) must hold.

We left open whether the lower-bound of Lemma 9 can be refined to e(v) ≥ d − 1. Note that
this would be best possible. Indeed, although in some cases of interest, e.g., interval graphs, the
output of the multi-sweep heuristic always equals the diameter [40], this nice property does not
hold for strongly chordal graphs and so for C4 -free Helly graphs [30].
Then, before finally proving the main result of this subsection, we need the following gated
property of Helly graphs. The (weak) diameter of a set S is equal to diam(S) := maxx,y∈S dist(x, y).
We recall that the metric projection of a vertex u on S, denoted P r(u, S), is defined as {v ∈ S |
dist(u, v) = dist(u, S)}.

Lemma 10. Let G be a Helly graph and S be a subset T of weak diameter at most two. Then, for
/ S there exists a vertex gS (v) ∈ N dist(v,S)−1 [v] ∩ {N (x) | x ∈ P r(v, S)}.
any v ∈

Proof. Since S has weak diameter at most two the balls N dist(v,S)−1 [v] and N [x], ∀x ∈ P r(v, S)
pairwise intersect. Therefore, the result follows from the Helly property.

As it is standard [23] we call such a vertex a gate of v, and we denote it by gS (v).

Remark 1. A variant of Maximum Cardinality Search was proposed in [23, 24] in order to compute
all the gates in linear time. For that we first run a breadth-first search from S. Then, we recursively
assign a gate to every vertex of V \ S, as follows. If v ∈ N (S), then v is its own gate and we set
p(v) = |N (v) ∩ S|. Otherwise, we choose for every vertex v a father u, one step closer to S, that
maximizes p(u). Indeed, by induction, p(u) = |P r(u, S)|. Then, we choose for v the same gate as
for its father u, and we set p(v) = p(u).

11
 We observe that, more generally, if S is an arbitrary vertex-subset (possibly, of weak diameter
larger than two), then for every vertex v with a gate
S in N (S) this above procedure correctly computes
such a gate. Indeed, let us define I(v, S) := {I(v, s) | s ∈ P r(v, S)}. This above procedure
associates to every vertex v a vertex v ∗ ∈ N (S) ∩ I(v, S) which maximizes |N (v ∗ ) ∩ S|. If v has a
gate with respect to S (w.r.t.), then it follows that gS (v) := v ∗ must be a gate of v. This observation
is crucial in our proof of Theorem 7.

Theorem 5. If G is a C4 -free Helly graph then we can compute a central vertex and so rad(G) in
linear time.

Proof. Let v be an arbitrary vertex, let u ∈ F (v) and let w ∈ F (u). By Lemma 9, e(u) =
dist(u, w) ≥ diam(G) − 2. Therefore, by Lemma 1, rad(G) ∈ {de(u)/2e , d(e(u) + 1)/2e , 1 +
de(u)/2e} (two of these numbers being equal, it gives us two possibilities). In order to decide in
which case we are, we use the following result from [34]: if rad(G) = r, then L(w, r, u) ∩ C(G) 6= ∅.
By Lemma 8, for any r the set C = L(w, r, u) is a clique. We compute, for every x ∈ / C, its distance
dist(x, C) and a corresponding gate g(x) – which exists by Lemma 10. It takes linear time. Then,
rad(G) = r implies maxx∈V dist(x, C) = r. If so then note that a vertex of C has eccentricity r
if and only if it is adjacent to the gate of every vertex at a distance exactly r from C. Overall, in
order to compute rad(G) we pick the smallest r such that a vertex of eccentricity r can be extracted
from L(w, r, u).

3.2 Computing a diametral pair

We base on the results from Section 3.1 so as to prove the following theorem:

Theorem 6. If G is a C4 -free Helly graph then we can compute a diametral pair and so diam(G)
in linear time.

Digression: an application to chordal Helly graphs

Our results in the paper are proved valid assuming the input graph to be Helly. However, the best-
known recognition algorithms for this class of graphs run in quadratic time [56]. In what follows,
we first explain an interesting application of Theorem 6 to general chordal graphs. We recall that
it can be decided in linear time whether a given graph is chordal [62].
The Lexicographic Breadth-First-Search (LexBFS) [62], of which a description can be found in
Fig. 2, is a standard algorithmic procedure that runs in linear time [53].
We use the following results on LexBFS in our analysis:

Lemma 11 ([40]). Let v be the vertex visited last by an arbitrary LexBFS. If the graph is chordal,
then the eccentricity of v is within 1 of the diameter.

Lemma 12 ([30]). If the vertex u of a chordal graph G last visited by a LexBFS has odd eccentricity,
then e(u) = diam(G).

Altogether combined with Theorem 6 we obtain that:

Remark 2. Consider an arbitrary chordal graph G. If we assume G to be Helly then, by Theorem 6,

there exists a linear-time algorithm for computing a diametral pair of G. Note that, we can apply
this algorithm to G without the knowledge that it is Helly, and either the algorithm will detect that

12
 Figure 2: Algorithm LexBFS [62].

G is not Helly (e.g., because some property of Helly graphs does not hold for G) or it will output
some pair of vertices (x, y). Furthermore, if G is chordal Helly, then (x, y) is a diametral pair. Let
d = dist(x, y).We can check for a chordal graph G whether diam(G) = d, or G is not Helly, as
follows:

• Let u be the vertex visited last by a LexBFS. We may assume, by Lemma 11, that e(u) ∈
{d − 1, d} (otherwise, d 6= diam(G), and so G is not Helly) and, by Lemma 12, that e(u) is
even. Then, we compute rad(G), which takes linear time [23]. By Lemma 11, diam(G) ∈
{e(u), e(u) + 1}, and so either G is not Helly or, by Lemma 1, rad(G) ∈ {e(u)/2, e(u)/2 + 1}.

• If e(u) = d, d is even and rad(G) = d/2, then this certifies that diam(G) = e(u). Else,
either G is not Helly or we have e(u) = d − 1, d is odd and rad(G) = e(u)/2 + 1. Since
dist(x, y) = d = e(u) + 1, we get diam(G) = d by Lemma 11.

Proof of Theorem 6
The remainder of this subsection is devoted to the proof of Theorem 6. We first compute r =
rad(G), which by Theorem 5 can be done in linear time. We also apply the multi-sweep heuristic,
i.e., we pick an arbitrary vertex v and we perform a BFS from a vertex u ∈ F (v). There are two
main cases depending on the parity of e(u).
Case e(u) is even. By Lemma 9, e(u) ≥ diam(G) − 1. Since by Lemma 1 we have diam(G) ≥
2r − 1, it follows that e(u) ∈ {2r − 2, 2r}. In particular, if e(u) = 2r − 2 then diam(G) = 2r − 1,
otherwise diam(G) = e(u) = 2r. Therefore, the difficulty here is not to compute the diameter, but
rather to compute a diametral pair. Let us assume that we have diam(G) = e(u) + 1 = 2r − 1
(else, e(u) = 2r = diam(G), and we are done). Let w ∈ F (u). W.l.o.g., e(w) = 2r − 2 (else,
e(w) = diam(G) and we are done). Therefore, dist(u, w) = 2r − 2 and u, w are mutually far apart.
The next result is a cornerstone of our algorithm:

Lemma 13. Let u, w be mutually far apart vertices in a C4 -free Helly graph G such that dist(u, w) =
diam(G) − 1 = 2r − 2 is even, and let C = L(u, r − 1, w). Then, (x, y) is a diametral pair of G if
and only if dist(x, C) = dist(y, C) = r − 1 and P r(x, C) ∩ P r(y, C) = ∅.

Proof. Since e(u) = e(w) = 2r − 2, for any x ∈ V , the balls of radius r − 1 and with centers
u, w, x, respectively, pairwise intersect. The Helly property implies the existence of a vertex c ∈ V
such that max{dist(u, c), dist(w, c), dist(x, c)} ≤ r − 1. Since we also have dist(u, w) = 2r − 2, we

13
conclude that c ∈ L(u, r − 1, w) = C and dist(x, C) ≤ dist(x, c) ≤ r − 1. Now on one direction,
let (x, y) be a diametral pair. By Lemma 8, C is a clique, implying dist(x, y) ≤ dist(x, C) + 1 +
dist(y, C) ≤ 2r − 1 = diam(G). Therefore, dist(x, C) = dist(y, C) = r − 1. For similar reasons,
we must have P r(x, C) ∩ P r(y, C) = ∅ (otherwise, dist(x, y) ≤ dist(x, C) + dist(y, C) ≤ 2r − 2 <
diam(G), a contradiction). Conversely, let (x, y) be such that dist(x, C) = dist(y, C) = r − 1 and
P r(x, C) ∩ P r(y, C) = ∅. Suppose by contradiction dist(x, y) < diam(G). In particular, the balls
of radius r − 1 and respective centers u, v, x, y pairwise intersect. By the Helly property, there
exists a c ∈ C such that max{dist(x, c), dist(y, c)} ≤ r − 1 = dist(x, C) = dist(y, C). But then,
c ∈ P r(x, C) ∩ P r(y, C) = ∅, a contradiction. Hence, (x, y) is a diametral pair.

Our strategy now consists in computing a pair (x, y) that satisfies the condition of this above
Lemma 13. We do so by using the “gated property” of Lemma 10. Indeed, let C = L(u, r − 1, w)
be as above defined, and let S = {x∗ | ∃x ∈ V such that gC (x) = x∗ ∧ dist(x, C) = r − 1}. Since by
Lemma 8 C is a clique, this set S is well-defined, and it can be computed in linear time. In order
to compute a diametral pair of G, by Lemma 13 it is sufficient to compute a pair x∗ , y ∗ ∈ S such
that N (x∗ ) ∩ N (y ∗ ) ∩ C = ∅. At first glance this approach does not look that promising since it is a
particular case of the Disjoint Sets problem (sometimes called the monochromatic Orthogonal
Vector), that cannot be solved in truly subquadratic time under SETH [68]. Before presenting
our solution to this special Disjoint Sets problem (i.e., Lemma 16) we introduce a pruning rule
in order to discard some vertices from S:

Lemma 14. In a C4 -free Helly graph G, for any clique C and adjacent vertices s, t ∈ N (C),
the metric projections P r(s, C) and P r(t, C) are comparable, i.e., either P r(s, C) ⊆ P r(t, C) or
P r(t, C) ⊆ P r(s, C).

Proof. Let s, t ∈ N (C) be adjacent and suppose for the sake of contradiction that there exist
s∗ ∈ P r(s, C) \ P r(t, C) and t∗ ∈ P r(t, C) \ P r(s, C). Then, (s, t, t∗ , s∗ , s) induces a C4 .

If x∗ , y ∗ ∈ S are adjacent, then by Lemma 14 either N (x∗ ) ∩ C ⊆ N (y ∗ ) ∩ C or N (y ∗ ) ∩ C ⊆

N (x∗ ) ∩ C. Therefore, we can discard a vertex of {x∗ , y ∗ } with maximum number of neighbours in
C from S. Doing so, we only need to consider a subset of gates that are pairwise non-adjacent.

Lemma 15. Let u, w be two vertices in a C4 -free Helly graph G such that dist(u, w) = 2r − 2, let
C = L(u, r − 1, w) and let S ⊆ N (C) be a stable set. Then, H = G[C ∪ S] is a split Helly graph.

Proof. By Lemma 8, the subset C is a clique, hence H is a split graph. Furthermore, let us consider
a family of pairwise intersecting balls in H. We may assume w.l.o.g. that no such a ball is contained
in F = {NH [c] | c ∈ C} ∪ {NH 2 [z] | z ∈ C ∪ S}. Indeed, all of these balls fully contain C, and

so, there is a common intersection for all the balls in a family if and only if there is a common
intersection for the sub-family of all these balls that are not in F. In particular, we may consider
the family of pairwise intersecting balls to be a collection of closed neighbourhoods NH [z], for all
z ∈ S 0 , where S 0 is a subset of S. Since S (and so, S 0 ) is a stable set, the subsets NG (z) ∩ C, z ∈ S 0
pairwise intersect. Then, we have that the balls of radius r − 1 and with centers in u, w and
the balls of radius 1 and with centers in the vertices of S 0 pairwise intersect in G. By the Helly
property (applied to G), there exists a vertex c at a distance ≤ r − 1 from both u and w, and at
a distance ≤ 1 from all of S 0 . Since dist(u, w) = 2r − 2, we get c ∈ L(u, r − 1, w) = C and so,
c ∈ {NG (z) ∩ C | z ∈ S 0 }. Consequently, H is Helly.
T

14
 Since every split graph has constant diameter (at most three), then by Corollary 2 the eccentric-
ity of all vertices in a split Helly graph can be computed in total linear time. Nevertheless, in what
follows, we propose a different approach for computing the diameter of a split Helly graph than
the one we presented in Corollary 2. Interestingly, this approach also works for other Helly-type
properties, e.g. for split open-neighbourhood-Helly graphs [55].

Lemma 16. A diametral pair in a split Helly graph can be computed in linear time.

Proof. Let G = (C ∪ S, E) be a split Helly graph with clique C and stable set S (note that if C
and S are not given then they can be computed in linear time [52]). Assume G to be connected
and diam(G) > 1 (otherwise, we are done). By the Helly property, diam(G) = 2 if and only if
G contains a universal vertex. Furthermore, if it is the case then any pair x, y of non-adjacent
vertices is diametral. Hence, from now on we assume that diam(G) = 3. Let G0 := G and
letT(x1 , x2 , . . . , x|S| ) be an arbitrary total order of S. For every 1 ≤ i ≤ |S|, we define Gi :=
G[ {NG (xj ) | 1 ≤ j ≤ i} ∪ S]. Our algorithm proceeds the vertices xi ∈ S sequentially, for
i = 1 . . . |S|, and does the following: If xi has eccentricity 3 in Gi−1 , then we compute a diametral
pair in this subgraph which contains xi and we stop.
We claim that our algorithm above is correct. For that we prove by finite induction that for any
i ≥ 0, if the algorithm did not stop in less than i steps then: (i) Gi is connected; and (ii) (xp , xq )
is a diametral pair of Gi if and only if it is a diametral pair of G. Since G0 = G, this is true for i = 0.
From now on we assume i > 0. If the algorithm did not stop at step i then (since in addition Gi−1 is
connected by the induction hypothesis), xi has eccentricity two in Gi−1 . In particular, every vertex
has a common neighbour with xi , implying that there can be no isolated vertex in Gi . We so obtain
that Gi is connected. Furthermore, if (xp , xq ) is a diametral pair of G then, necessarily, it is also a
diametral pair of the connected subgraph Gi (i.e., because xp and xq have no common neighbour in
this subgraph, and so they are at distance 3 to each other). Conversely, let (xp , xq ) be a diametral
pair of Gi . Suppose, by contradiction, that (xp , xq ) is not a diametral pair of G, or equivalently
NG (xp ) ∩ NG (xq ) 6= ∅. Since the neighbour sets NT G (xj ), j ∈ {1, 2, . . . , i} ∪ {p, q} pairwise intersect,
by the Helly property, there exists a vertex w ∈ {NG (xj ) | j ∈ {1, 2, . . . , i} ∪ {p, q}}. But then,
(xp , xq ) is not a diametral pair of Gi (as diam(Gi ) ≥ diam(G) = 3), a contradiction. As a result,
our above algorithm for computing a diametral pair of G is correct.
We still have to explain how to execute this algorithm in linear time. For that, we main-
tain a partition of the clique, initialized to P0 := (C). At step i we refine the former partition
Pi−1 = (C1i−1 , C2i−1 , . . . , Cki−1
i−1
) into a new partition Pi = (C1i−1 ∩ NG (xi ), C1i−1 \ NG (xi ), C2i−1 ∩
NG (xi ), C2i−1 \ NG (xi ), . . . , Cki−1
i−1
∩ NG (xi ), Cki−1
i−1
\ NG (xi )). This partition refinement can be done
in time O(NG (xi )) (up to some initial pre-processing in O(|C|) time) [53]. Furthermore, an easy
induction proves that for any i ≥ 0 the first group of Pi is exactly C1i = {NG (xj ) | 1 ≤ j ≤ i} i.e.,
T
the clique of Gi . We finally explain how we use this partition in order to decide, at step i, whether xi
has eccentricity equal to 3 in Gi−1 . At the beginning of the algorithm T we compute the degree of ev-
ery vertex in S. Then, at step i we consider all the vertices in C2i = {NG (xj ) | 1 ≤ j < i} \ NG (xi )
sequentially (second group of the partition Pi ). For every w ∈ C2i we enumerate all its neighbours
in S and we decrease their respective degrees by one. In particular, if during step i the degree of
some vertex xp ∈ S falls to 0, then xp has no common neighbour with xi in Gi−1 . Equivalently,
(xi , xp ) is a diametral pair of Gi−1 and the eccentricity of xi , xp in this subgraph is 3. We observe
that the sets C2i on which we iterate are pairwise disjoint. As a result, the total complexity of the
algorithm is linear.

15
 This above Lemma 16 achieves proving Theorem 6 in the case when e(u) is even.
Case e(u) is odd. By Lemma 9, e(u) ≥ diam(G) − 2. Therefore, by Lemma 1, e(u) ∈
{2r − 3, 2r − 1}. In the first subcase, we deduce from Lemma 1 that diam(G) = 2r − 1. Let
w ∈ F (u), and assume e(w) = e(u) = dist(u, w) = 2r − 3 (otherwise, either e(w) = 2r − 2 is even
and we are back to the former case, or e(w) = 2r − 1 and then we are done since w is an end of a
diametral path).
Lemma 17. Let u, w be mutually far apart vertices in a C4 -free Helly graph G such that dist(u, w) =
diam(G) − 2 = 2r − 3 is odd, and let A = L(w, r − 2, u). Then, (x, y) is a diametral pair of G if
and only if dist(x, A) = dist(y, A) = r − 1, P r(x, A) ∩ P r(y, A) = ∅, and in addition dist(y, u) =
dist(y, w) = dist(x, u) = dist(x, w) = 2r − 3.
Proof. We first prove that for every vertex x we have dist(x, A) ≤ r − 1. Indeed, since w, u are
mutually far apart, we have dist(x, u) ≤ dist(w, u) = 2r − 3 and dist(x, w) ≤ dist(w, u) = 2r − 3.
Hence, balls N r−1 [u], N r−2 [w] and N r−1 [x] pairwise intersect. By the Helly property, there is a
vertex z ∈ A with dist(x, z) ≤ r − 1.
For any pair (x, y) we have dist(x, y) ≤ dist(x, A) + dist(P r(x, A), P r(y, A)) + dist(y, A) ≤
2r − 2 + dist(P r(x, A), P r(y, A)). By Lemma 8, A is a clique, which implies that we have
dist(P r(x, A), P r(y, A)) ≤ 1. As a result, if (x, y) is diametral, we get dist(x, A) = dist(y, A) = r−1
and P r(x, A) ∩ P r(y, A) = ∅. We also get dist(y, u) = dist(y, w) = dist(x, u) = dist(x, w) =
2r − 3 by Lemma 9. Conversely let (x, y) be any pair that satisfies all these above proper-
ties, and suppose for the sake of contradiction that we have dist(x, y) ≤ 2r − 2. Consider
balls N r−1 [x], N r−1 [y], N r−1 [u] and N r−2 [w]. By distance requirements, these balls pairwise in-
tersect. The Helly property implies that a vertex z ∈ A exists such that dist(x, z) = r − 1 and
dist(y, z) = r − 1. However, the latter contradicts with P r(x, A) ∩ P r(y, A) = ∅.
Overall, we can apply the same approach as in Lemma 13 in order to compute a diametral pair
in this subcase.
The most difficult subcase is when e(u) = 2r − 1. By Lemma 1, either diam(G) = 2r − 1 or
diam(G) = 2r. We explain below how, assuming diam(G) = 2r, we can compute in linear time
all central vertices. Then, if diam(G) = 2r, by Lemma 4, a pair (x, y) is diametral if and only if
both x and y are at a distance exactly r from all central vertices. We test a posteriori whether
dist(x, y) = 2r, and if not diam(G) = e(u) = 2r − 1. W.l.o.g. r ≥ 2.
Lemma 18. If G is a C4 -free Helly graph of diameter 2r ≥ 4, then C(G) is a clique.
Proof. Every central vertex is at a distance exactly r from both ends x, y of any diametral path.
In particular, C(G) ⊆ L(x, r, y), which is a clique by Lemma 8.
Therefore, if diam(G) = 2r, by Lemma 18, for any central vertex c, we have C(G) ⊆ N [c] = S.
Note that, by Theorem 5, we can compute such a central vertex c in linear time. Furthermore,
diam(S) ≤ 2. For every x ∈ / S, we compute dist(x, S) and a corresponding gate g(x), which exists
by Lemma 10. By construction, maxx dist(x, S) ≤ maxx dist(x, c) ≤ r. Furthermore, every vertex
at a distance ≤ r − 2 from S is at a distance ≤ r from every vertex of S. As a result, we only need
to consider the vertices at a distance ≥ r − 1 from S.
In fact, and as already observed in the proof of Theorem 5, for a vertex of S to be central it
needs to be adjacent to the gates of all the vertices at a distance exactly r from S. All the vertices
which satisfy this necessary condition can be computed in linear time. Hence, we can restrict
ourselves to the vertices that are at distance exactly r − 1 from S.

16
Lemma 19. Let G be a C4 -free Helly graph and let S be such that diam(S) ≤ 2. If dist(x, S) = r−1,
then there exists a vertex pgS (x) ∈ N r−1 [x] such that S ∩ N r [x] ⊆ N [pgS (x)]. Moreover, pgS (x) is
in the closed neighbourhood of some gate of x.

We call such a vertex a pseudo-gate of x.

Proof. The existence of such a pseudo-gate follows from the fact that the balls N r−1 [x] and N [s], s ∈
S ∩ N r [x] pairwise intersect, and from the Helly property. Now, let pg(x) and g(x) be arbitrary
pseudo-gate and gate of x, respectively, and assume pg(x) 6= g(x) and pg(x)g(x) ∈ / E (else, we are
done). In particular, pg(x) ∈ / P r(x, S). Note that, since we have P r(x, S) ⊆ N (g(x)) ∩ N (pg(x)),
dist(g(x), pg(x)) = 2. Then, the balls N r−2 [x], N [g(x)] and N [pg(x)] pairwise intersect. By the
Helly property, there exists a vertex x∗ in their common intersection. We claim that x∗ is a gate of
x, that will prove the lemma. Indeed, for every s ∈ P r(x, S) we get a cycle (s, pg(x), x∗ , g(x), s).
Since G is C4 -free, this implies sx∗ ∈ E.

By taking advantage of the property that pg(x) is either equal or adjacent to some gate g(x),
we next explain how we can adapt the technique from [23, 24] in order to compute all pseudo-gates
in total linear time.

Remark 3. For every x ∈ N (S), we can choose as its pseudo-gate any vertex of N [x] that maxi-
mizes the intersection of S with its closed neighbourhood (possibly, x itself ). Then, when we compute
a gate for every vertex, we break ties by choosing one such a gate whose pseudo-gate maximizes its
intersection with S. In doing so, we can compute a pseudo-gate for every vertex at distance r − 1
from S, in total linear time.

Finally, if diam(G) = 2r, then the central vertices are exactly those adjacent to the gates of all
the vertices at distance r from S and either equal or adjacent to the pseudo-gates of all the vertices
at distance r − 1 from S.

3.3 Computing all eccentricities

We are now ready to present the main result of this section, namely:

Theorem 7. If G is a C4 -free Helly graph then we can compute the eccentricity of all vertices in
linear time.

Proof. By Lemma 4, we only need to compute C(G). Our main tool for that is our parameterized
linear-time algorithm for Small Eccentricities, for k = 2 (Theorem 2). In particular, by
Corollary 2, we may assume that rad(G) = r ≥ 3. Let diam(G) = d and let (x, y) be a diametral
pair. By Theorem 6, it can be computed in linear time. We assume in what follows d = 2r − 1
(else, by Lemma 1, d = 2r, and we already explained in Sec. 3.2 how to compute C(G)). Obviously,
C(G) ⊆ N r [x]∩N r [y]. Since dist(x, y) = 2r−1 we get N r [x]∩N r [y] = L(x, r−1, y)∪L(y, r−1, x)∪Z,
where Z := {z ∈ V | dist(z, x) = dist(z, y) = r}. Furthermore, for a C4 -free Helly graph, by
Lemma 8 the slices L(x, r − 1, y) and L(y, r − 1, x) are cliques; we can reuse the same idea as for
Theorem 5 in order to compute C(G) ∩ (L(x, r − 1, y) ∪ L(y, r − 1, x)) in linear time. From now on
we focus on Z.
Claim 3. Every z ∈ Z has adjacent neighbours in L(x, r − 1, y) and L(y, r − 1, x), resp.

17
Proof. Let p = q = r−1 and k = 0. We have dist(x, y) = p+q+1, dist(x, z) = p+k+1, dist(y, z) =
q + k + 1. Since G is pseudo-modular, by Lemma 6, z is adjacent to the two ends of an edge in the
middle of some shortest xy-path. 
Since both L(x, r − 1, y) and L(y, r − 1, x) are cliques, the above implies that Z has weak diameter
at most 3 ≤ r. More generally, every vertex at a distance ≤ r − 2 from L(x, r − 1, y) ∪ L(y, r − 1, x)
is at a distance ≤ r from every vertex of Z. Therefore, we further restrict our study to the vertices
w such that dist(w, L(x, r − 1, y) ∪ L(y, r − 1, x)) ≥ r − 1.
Subcase dist(w, L(x, r − 1, y) ∪ L(y, r − 1, x)) = r − 1. Let C := L(x, r − 1, y) and consider the
set Wx of all vertices w such that dist(w, L(x, r − 1, y) ∪ L(y, r − 1, x)) = dist(w, C) = r − 1. Let
Ax contain a gate gC (w) for every w ∈ Wx , which exists by Lemma 10.
Claim 4. For every z ∈ Z, we have maxw∈Wx dist(z, w) ≤ r if and only if Ax ⊆ N 2 [z].
Proof. First assume Ax ⊆ N 2 [z], or equivalently ∀a ∈ Ax , N [a]∩N [z] 6= ∅. Let w ∈ Wx and let a :=
gC (w) ∈ Ax . Then, dist(z, w) ≤ dist(z, a) + dist(a, w) ≤ 2 + (r − 2) = r. Conversely, let us assume
maxw∈Wx dist(z, w) ≤ r, and let w ∈ Wx be arbitrary. The balls N r−1 [x], N r−1 [w], N r [y], N [z]
pairwise intersect. Therefore, by the Helly property, N [z]∩P r(w, C) 6= ∅. For any gate gC (w) ∈ Ax ,
it implies N [z] ∩ N [gC (w)] ⊇ N [z] ∩ P r(w, C) 6= ∅. 
Overall with this above claim we are reduced to Small Eccentricities, with k = 2, which by
Theorem 2 can be solved in linear time. Our approach also works for C 0 := L(y, r − 1, x), up to
reversing the respective roles of x and y.
Subcase dist(w, L(x, r − 1, y) ∪ L(y, r − 1, x)) > r − 1. Let W ∗ contain all vertices w such that
dist(w, L(x, r − 1, y) ∪ L(y, r − 1, x)) ≥ r.
Claim 5. For every w ∈ W ∗ we have dist(x, w) = dist(y, w) = 2r − 1 and dist(w, Z) = r − 1.
Moreover, P r(w, Z) = L(w, r − 1, x) ∩ L(w, r − 1, y) is a clique.
Proof. We first prove that dist(x, w) = dist(y, w) = 2r − 1. Indeed, suppose for the sake of
contradiction that dist(x, w) ≤ 2r − 2. Since the balls N r−1 [x], N r−1 [w], N r [y] pairwise intersect,
by the Helly property, we get dist(w, L(x, r − 1, y)) ≤ r − 1, a contradiction. Hence, the balls
N r−1 [w], N r [x], N r [y] pairwise intersect, which implies, by the Helly property, dist(w, Z) = r − 1.
In this situation, we have P r(w, Z) = L(w, r − 1, x) ∩ L(w, r − 1, y). By Lemma 8, we get that
P r(w, Z) is a clique. 
The combination of this above claim with Lemma 10 implies the existence of a gate gZ (w) ∈
N r−2 [w] ∩ {N (v) | v ∈ P r(w, Z)} for every vertex w ∈ W ∗ . Note that we can compute the gate
T
of all such vertices w in linear time, by adapting the techniques from [23, 24]. So, let A∗ contain a
gate gZ (w) for every vertex w ∈ W ∗ . We prove as before:
Claim 6. For every z ∈ Z, we have maxw∈W ∗ dist(z, w) ≤ r if and only if A∗ ⊆ N 2 [z].
Proof. We can prove this above condition to be sufficient for having maxw∈W ∗ dist(z, w) ≤ r in the
exact same way as we did for Claim 4. Conversely, let us assume that we have maxw∈W ∗ dist(z, w) ≤
r, and let w ∈ W ∗ be arbitrary. The balls N [z], N r−1 [w], N r [x], N r [y] pairwise intersect, and so,
by the Helly property, N [z] ∩ P r(w, Z) = N [z] ∩ (L(w, r − 1, x) ∩ L(w, r − 1, y)) 6= ∅. It implies
that N [z] ∩ N [gZ (w)] ⊇ N [z] ∩ P r(w, Z) 6= ∅. Equivalently, A∗ ⊆ N 2 [z]. 
We are done by reducing a final time to Small Eccentricities, with k = 2, which by Theorem 2
can be solved in linear time.

18
4 More reductions to split graphs
We conclude by considering diameter computation within another class than Helly graphs, namely
chordal graphs. This is motivated by our results in Section 3.2 where we reduced the problem of
computing a diametral pair on C4 -free Helly graphs (and so, on chordal Helly graphs) to the same
problem on split Helly graphs. We prove next that there exists a (randomized) reduction from
diameter computation on general chordal graphs to the same problem on split graphs. Specifically,
a sparse representation of a split graph is the list of the closed neighbourhoods of vertices in its
stable set [44]. – Such a representation may not be unique, since it depends on a specific bipartition
of the split graph into a clique and a stable set. – Then, the Disjoint Sets problem consists in
computing the diameter of a split graphP given by one of its sparse representations. For a split graph
H with stable set U we define `(H) := u∈U degH (u), a.k.a. the size of its sparse representation.

Theorem 8. For any chordal graph G, we can compute in Õ(m)-time the sparse representations
of a family (Hi ) of split graphs such that, if for every i we can compute diam(Hi ) in time O(`(Hi ) ·
|V (Hi )|b ), then we can compute diam(G) in time Õ(mnb ).
The OV problem is given as inputs the sparse representation of a split graph G and two subsets
A, B in its stable set, and it asks what the largest distance in G is between a vertex of A and a
vertex of B. We highlight the following variant of our Theorem 8. Although it is not clear whether
the two statements are equivalent, our proofs for both results are nearly identical.
Theorem 80 . For a subclass C of chordal graphs, let S contain all split graphs that are induced
subgraphs of a graph in C. If for every G ∈ S, for every bipartition A, B of its stable set, we can
solve OV in O(`b ) time, for some b ≥ 1, then there is a randomized O(mb log2 n)-time algorithm
for computing w.h.p. the diameter of chordal graphs in C.

4.1 Preliminaries
We shall use the following metric properties of chordal graphs. We stress that these are quite
similar to some metric properties of C4 -free Helly graphs that we proved in Section 3.
Lemma 20 ([23]). For any clique C in T a chordal graph G, we can compute in linear time the
distance dist(x, C) and a gate g(x) ∈ {I(x, w) | w ∈ P r(x, C)} adjacent to all vertices from
P r(x, C), for all vertices x.
Lemma 21 ([23]). In a chordal graph G, for any clique C and adjacent vertices s, t ∈ / C the metric
projections P r(s, C) and P r(t, C) are comparable, i.e., either P r(s, C) ⊆ P r(t, C) or P r(t, C) ⊆
P r(s, C).

4.2 The reduction

Our reduction is one-to-many. We recall that a clique-tree of a graph G is a tree T of which the
nodes are the maximal cliques of G, and such that for every vertex v the set of all the maximal
cliques that contain v induces a connected subtree. It is known that G is chordal if and only if it
has a clique-tree [18, 49, 67] and, furthermore, a clique-tree can be computed in linear time [66]. –
See also [7, 15] and the references therein –. We may see a clique-tree
P T as a node-weighted tree
where, for any maximal clique C, w(C) = |C|. Then, let w(T ) := C w(C). For a chordal graph,
w(T ) = O(n + m) [7]. We will use a standard result on weighted centroids in trees, namely:

19
Lemma 22 ([51]). Every node-weighted tree T has at least one weighted centroid, that is, a node
v whose removal leaves components of maximum weight ≤ w(T )/2. Moreover, a weighted centroid
can be computed in linear time.

Let T be a fixed clique-tree of G. If T is reduced to a single node, or to exactly two nodes,

respectively (equivalently, either G is a complete graph or it is the union of two crossing complete
subgraphs), then we output diam(G) = 1, or diam(G) = 2, respectively (base case of our reduction).
Otherwise, let S ∈ V (T ) be a weighted centroid of T . By Lemma 22, the clique S can be computed
in O(|V (T )|) = O(n) time if we are given T in advance. S Furthermore, let T1 , T2 , . . . , T` be the
components of T \ {S}, and for every 1 ≤ i ≤ ` let Vi := ( V (Ti )) \ S. Since ∀i, NG (Vi ) ⊆ S is
a clique, the closed neighbourhoods NG [Vi ], 1 ≤ i ≤ ` induce distance-preserving subgraphs of G,
which we denote by G1 , G2 , . . . , G` . We apply our reduction recursively on each of these subgraphs
Gi . Then, let dS := maxvi ∈Vi ,vj ∈Vj |i6=j dist(vi , vj ). We have: diam(G) = max{dS , max{diam(Gi ) |
1 ≤ i ≤ `}}. So, we are left with computing dS . For that, we define ∀i, di := maxvi ∈Vi dist(vi , S).
We order the sets Vi by non-increasing value of di . Since S is a clique, we get d1 + d2 ≤ dS ≤
d1 + d2 + 1. In order to decide in which case we are, we proceed as follows:

• We discard all sets Vi s.t. di < d2 . Doing so we are left with sets V1 , V2 , . . . , Vk , k ≤ `.

• Then, for every 1 ≤ i ≤ k and v ∈ Vi , if dist(v, S) = di then we compute a gate for vertex
v, which exists by Lemma 20. Furthermore, if two such gate vertices are adjacent then they
must be in the same connected component of G \ S, and by Lemma 21 their respective metric
projections on S are comparable. It implies that we can remove any of these two vertices
with largest metric projection on S. Thus, from now on, we assume all selected gate vertices
to be pairwise non-adjacent.

• Finally, let a, b ∈
/ V be fresh new vertices which we make adjacent to each other and to all
vertices of S. There are two subcases:

– Case d1 6= d2 . We make vertex a adjacent to all gatesS of the vertices in V1 , while we

make vertex b adjacent to all gates of the vertices in ki=2 Vi .
– Case d1 = d2 . For every 1 ≤ i ≤ k, with probability 1/2 we make vertex a adjacent to
all gates of the vertices in Vi (otherwise, we do so with vertex b).

Doing as above we get a split graph H whose clique and stable set are S ∪ {a, b} and the selected
gate vertices, respectively. We stress that deciding whether diam(H) = 3 is here equivalent to
deciding whether the largest distance in H \ {a, b} between a vertex of A = NH (a) \ (S ∪ {b}) and a
vertex of B = NH (b) \ (S ∪ {a}) is equal to 3. Furthermore, H \ {a, b} is an induced split subgraph
of G by construction.

Claim 7. If diam(H) = 3 then dS = d1 + d2 + 1. Conversely, if dS = d1 + d2 + 1 then diam(H) = 3

with probability ≥ 1/2.

Proof. Let x∗ and y ∗ be two gates such that distH (x∗ , y ∗ ) = 3. By construction of H, x∗ , y ∗ are
the respective gates of two vertices x, y such that min{distG (x, S), distG (y, S)} ≥ d2 . Furthermore,
since {a, b} ∩ (NH (x∗ ) ∩ NH (y ∗ )) = ∅, we get that x, y are in different components of G \ S, and
{distG (x, S), distG (y, S)} = {d1 , d2 }. Hence, dS ≥ dist(x, y) ≥ d1 + d2 + 1. Conversely, let us
assume the existence of a pair (x, y) such that: x and y are in different components of G \ S, and

20
dist(x, y) = d1 + d2 + 1. W.l.o.g., let dist(x, S) = d1 and dist(y, S) = d2 . Let also x∗ , y ∗ be the
two gates computed for x and y, respectively (we may assume, w.l.o.g., that x∗ , y ∗ are indeed in
the stable set of H). We must have NH (x∗ ) ∩ NH (y ∗ ) ⊆ {a, b}. In particular, if d1 6= d2 then
NH (x∗ ) ∩ NH (y ∗ ) = ∅, else P rob[NH (x∗ ) ∩ NH (y ∗ ) = ∅] ≥ 1/2. 

Overall, we may repeat the construction of this above split graph H up to O(log n) times in
order to compute dS with high probability.

4.3 Analysis
Since at every step of our reduction we pick a weighted centroid in the clique-tree of every subgraph
Gi considered, there are O(log w(T )) = O(log n) recursion levels. Therefore, up to polylogarithmic
factors, the total running-time of the reduction is of the same order of magnitude as the worst-case
running time of a single step. Furthermore, it is not hard to prove that the first step, when we only
consider the full input graph G, runs in linear time (i.e., omitting the computation of the diameter
for the related split graph H). However, during the next steps of our reduction we may need to
consider pairwise overlapping subgraphs Gi , thereby making the analysis more delicate. The key
insight here is that the clique-trees of all these subgraphs form a family of pairwise disjoint subtrees
of T . We next explain how to perform the first step, and so all subsequent ones, in time O(w(T )).
Since w(T ) = O(n + m) [7], doing so we can compute all the desired split graphs H throughout
our reduction in total quasi linear time Õ(n + m).

Lemma 23. Let S be any clique of a chordal graph G. If a clique-tree T is given, then in time
O(w(T )) we can compute ∀v ∈
/ S, dist(v, S) and a corresponding gate g(v).

Proof. Let C := V (T ) ∪ {S} be the set of all maximal cliques of G, to which we also add the
clique S if it is not maximal. We define a set of fresh new vertices indexed by C, namely let
XC := {xC | C ∈ C}. Then, let J := (V ∪ XC , {vxC | v ∈ C}) be the vertex-clique incidence graph
of G. Note that we can construct J by scanning once the clique S and all the maximal cliques of
the graph G.
We prove as a subclaim that for every vertex v we have distJ (v, xS ) = 2·distG (v, S)+1. Indeed,
since by construction NJ (xS ) = S, we get distJ (v, xS ) = 1 + minu∈S distJ (v, u) = 1 + distJ (v, S).
Furthermore, in every vS-path of J, that is in every path between v and a closest vertex of S, half
of the internal vertices must be in XC . Since in addition two vertices that are adjacent to a same
maximal clique in J are adjacent in G, it allows us to transform such a path in J to a vS-path in
G that is twice shorter. Conversely, any vS-path of G can be transformed into a vS-path of J that
is twice longer, simply by adding between every two consecutive vertices a maximal clique which
contains both of them. – Note that combining the two constructions, the latter exactly characterizes
the shortest vS-paths in J. – As a result, we proved as claimed that distJ (v, S) = 2 · distG (v, S).
It implies that after a BFS in J rooted at xS we get distG (v, S), ∀v ∈ / S.
Then, we recursively define p(α), ∀α ∈ V (J) \ NJ [xS ] as follows (recall that NJ [xS ] = {xS } ∪ S):
if α = xC for some C ∈ C \ {S}, and C ∩ S 6= ∅ (equivalently, distJ (xS , α) = 2), then p(α) = |C ∩ S|
(number of neighbours at distance one from xS ); otherwise, p(α) = max{p(β) | β ∈ NJ (α) ∩
IJ (xS , α)}. Note that, we can compute all those values p(α) during a BFS with no significant
computational overhead. Furthermore, we claim that ∀v ∈ V, p(v) = |P rG (v, S)|. Indeed, by
induction, p(v) = max{|C ∩S| | xC ∈ XC ∩IJ (v, xS ), C 6= S}. We recall our earlier characterization

21
of the shortest vS-paths in J as those obtained from the shortest vS-paths in G by adding a
maximal clique between every two consecutive vertices. It implies that for every clique C such
that xC ∈ XC ∩ IJ (v, S), we have C ∩ S ⊆ P rG (v, S). In particular, if we start from a shortest
vS-path in G that contains a gate gS (v), there is a corresponding vS-path in J that contains a
clique C ⊇ P r(v, S) ∪ {gS (v)}. As a result, p(v) is exactly |P rG (v, S)|.
Finally, we recursively define g(α), ∀α ∈ V (J)\NJ2 [xS ] as follows (recall that NJ2 [xS ] = S ∪{xC |
C ∩ S 6= ∅}): if α ∈ V and α ∈ NG (S) (equivalently, distJ (xS , α) = 3), then g(α) = α; otherwise,
g(α) ∈ {g(β) | β ∈ NJ (α) ∩ IJ (xS , α) ∧ p(α) = p(β)}. Again, we can compute all those values g(α)
during a BFS with no significant computational overhead. Furthermore, it also follows from our
above characterization of shortest vS-paths in J that we have, ∀v ∈ / S, g(v) is a gate of v.

Lemma 24. For a clique-tree T of a given chordal graph G, let H be the split graph constructed
as in Section 4.2. A sparse representation of the split graph H can be computed in O(w(T )) time.
Furthermore, if U ⊆ V (H) is the stable set of H, then |U | = O(|V (T )|).

Proof. After Lemma 23, we need to select a subset of pairwise non-adjacent gates in order to
construct U . For that, we consider all the maximal cliques C sequentially. If C contains at least
two gates, then we suppress all the gates in C but one with minimum metric projection on S.
Overall, this post-processing also takes time O(w(T )). Doing so there P
is at most one gate
Pselected
per maximal clique, i.e., |U | ≤ |V (T )|. Furthermore, we have `(H) = u∈U degH (u) ≤ C |C| =
w(T ). We end up adding a, b and the edges incident to these two vertices and the stable set U ,
that takes total time O(|U |) = O(|V (T )|).

Finally, in order to complete the proof of Theorem 8, let (Hi ) be the family of split graphs
considered for a given recursive step of the reduction. Let usPassume that for every i, we can
compute diam(Hi ) in O(`(Hi ) · |V (Hi )|b ) time. By Lemma 24, i `(Hi ) = O(w(T )) = O(n + m).
Furthermore, maxi |V (Hi )| ≤ n. As a result, computing diam(Hi ) for all i takes total time O(mnb ).
In the same way, if we can solve diam(Hi ) in O(`(Hi )b ) time, for some b ≥ 1, then computing
diam(Hi ) for all i takes total time O(mb ) (as explained in Sec. 4.2, the latter reduces to OV on a
Hi0 ⊆ Hi , where Hi0 is an induced split subgraph of G). Note that we need to repeat our probabilistic
construction of the Hi ’s at most O(log n) times for each step, and that there are O(log n) steps in
total. As a result, the running time is in O(mb log2 n).

4.4 Applications
It was proved in [37] that for all chordal graphs, an additive +2-approximation of all eccentricities
can be computed in total linear time. Using our previous reduction from Section 4.2, we improve
this result to an additive +1-approximation, but at the price of a logarithmic overhead in the
running time.

Theorem 9. For every n-vertex m-edge chordal graph, we can compute an additive +1-approximation
of all eccentricities in total O(m log n) time.

Roughly, Theorem 9 follows from the observation that, in a split graph, if we set e(v) = 2 for
every vertex v, then we get an additive +1-approximation of all the eccentricities.

Proof. In what follows, let G be chordal and let T be a fixed clique-tree of G. We can assume that
G has at least two vertices.

22
 • If T is reduced to a single node, or equivalently, G is a complete graph, every vertex has
eccentricity equal to 1. In the same way if T is reduced to exactly two nodes, then G is the
union of two crossing complete subgraphs C1 and C2 . Furthermore, every vertex of C1 ∩ C2
has eccentricity equal to 1, whereas every vertex of the symmetric difference C1 ∆C2 has
eccentricity equal to 2.
• Otherwise, let S ∈ V (T ) be a weighted centroid of T . By Lemma 22, the clique S can be
computed in time O(|V (T )|) = O(w(T )) if we are given T in advance.

S T1 , T2 , . . . , T` be the components of T \ {S}, and for every 1 ≤ i ≤ ` let Vi :=

– Let
( V (Ti )) \ S. We recall that the closed neighbourhoods NG [Vi ], 1 ≤ i ≤ ` induce
distance-preserving subgraphs of G. As in Section 4.2, we denote these subgraphs by
G1 , G2 , . . . , G` . We apply our reduction recursively on each of the Gi ’s. Doing so, for
every i and every vertex vi ∈ Vi we get an additive +1-approximation of eGi (vi ).
– Then, for every vertex v ∈ / S, we compute distG (v, S) and a gate gS (v). By Lemma 23
this can be done in total O(w(T )) time if T is given in advance. Furthermore, notice
that since S is a clique, for every s ∈ S we have that maxv∈V distG (v, S) is an additive
+1-approximation of eG (s).
– Finally, we observe that for every i and every vertex vi ∈ Vi we have:
eG (vi ) = max{eGi (vi ), max distG (vi , u)}.
u∈V
/ i

As in Section 4.2 we define ∀i, di := maxvi ∈Vi dist(vi , S). If we compute the two largest
values amongst the di ’s, then we can compute ∀i, ei := maxj6=i dj . We are done as for
every vi ∈ Vi , distG (vi , S) + ei is an additive +1-approximation of maxu∈V
/ i distG (vi , u).

As already observed in Section 4.3, there are O(log w(T )) = O(log n) recursion levels. Since
at any level, the clique-trees of all the subgraphs considered form a family of pairwise disjoint
subtrees of T , each step can be done in O(w(T )) time. Therefore, the total running time is in
O(w(T ) log n) = O(m log n) [7].
Finally, the VC-dimension of a graph G is the largest cardinality of a subset S such that
{N [v] ∩ S | v ∈ V } = 2S (we say that S is shattered by G). For instance, interval graphs have
VC-dimension at most two [12].
Theorem 10. For every d > 0, there exists a constant ηd ∈ (0; 1) such that in O(mn1−ηd ) time,
we can compute the diameter of any chordal graph of VC-dimension at most d.
Proof. If a split graph H has VC-dimension at most d0 , then we can compute its diameter in truly
subquadratic time O(`(H) · |V (H)|1−εd0 ), for some εd0 ∈ (0; 1) [45, Theorem 1]. As a result, it is
sufficient to prove that all the split graphs Hi , which are output by the reduction of Theorem 8,
have a VC-dimension upper bounded by a function of d. We observe that every such Hi is obtained
from an induced subgraph Hi0 of G by adding two new vertices a and b (see Section 4.2). Since G
has VC-dimension at most d, so does Hi0 . Then, let S be a largest subset shattered by Hi . We can
extract from S a maximal shattered subset S 0 ⊆ V (Hi0 ) (i.e., not containing a and b). In particular,
0
|S 0 | ≥ |S| − 2. Furthermore, since S 0 is shattered by Hi , {N [v] ∩ S 0 | v ∈ V (Hi )} = 2S holds. It
0
implies that |{N [v] ∩ S 0 | v ∈ V (Hi0 ) = V (Hi ) \ {a, b}}| ≥ 2|S | − 2. By the Sauer-Shelah-Perles
Lemma [63, 65], we also have |{N [v] ∩ S 0 | v ∈ V (Hi0 )}| = O(|S 0 |d ), which implies |S 0 | = O(d log d).
Consequently, every Hi has VC-dimension in O(d log d).

23
 An undirected path graph is the intersection graphs of paths in a tree. Since the undirected
path graphs have VC-dimension at most 3 [12], the following result is a direct consequence of our
Theorem 10:
Corollary 3. There is a truly subquadratic-time algorithm for computing the diameter of undirected
path graphs.

References
[1] A. Abboud, V. Vassilevska Williams, and J. Wang. Approximation and fixed parameter sub-
quadratic algorithms for radius and diameter in sparse graphs. In SODA, pages 377–391.
SIAM, 2016. URL: [Link]

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

[3] H.-J. Bandelt and H. Mulder. Pseudo-modular graphs. Discrete Mathematics, 62(3):245–260,
1986.

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

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

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

[7] J. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In Graph theory
and sparse matrix computation, pages 1–29. 1993.

[8] B. Bollobás, D. Coppersmith, and M. Elkin. Sparse distance preservers and additive spanners.
SIAM Journal on Discrete Mathematics, 19(4):1029–1055, 2005.

[9] J. A. Bondy and U. S. R. Murty. Graph theory. 2008.

[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] G. Borradaile and E. Chambers. Covering nearly surface-embedded graphs with a fixed number
of balls. Discrete & Computational Geometry, 51(4):979–996, 2014.

[12] N. Bousquet, A. Lagoutte, Z. Li, A. Parreau, and S. Thomassé. Identifying codes in hereditary
classes of graphs and VC-dimension. SIAM Journal on Discrete Mathematics, 29(4):2047–2064,
2015.

[13] N. Bousquet and S. Thomassé. VC-dimension and Erdős–Pósa property. Discrete Mathematics,
338(12):2302–2317, 2015.

[14] A. Brandstädt, V. Chepoi, and F.F. Dragan. The algorithmic use of hypertree structure and
maximum neighbourhood orderings. Discrete Applied Mathematics, 82(1-3):43–77, 1998.

24
[15] A. Brandstädt, V. Chepoi, and F.F. Dragan. Tree-structured graphs. In Handbook of Graph
Theory, Combinatorial Optimization, and Algorithms. CRC Press, 2016.

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

[17] K. Bringmann, T. Husfeldt, and M. Magnusson. Multivariate analysis of orthogonal range

searching and graph distances parameterized by treewidth. In IPEC, 2018.

[18] P. Buneman. A characterisation of rigid circuit graphs. Discrete Mathematics, 9(3):205–212,

1974.

[19] S. Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in
planar graphs. ACM Transactions on Algorithms, 15(2):21, 2018.

[20] S. Cabello and C. Knauer. Algorithms for graphs of bounded treewidth via orthogonal range
searching. Computational Geometry, 42(9):815–824, 2009.

[21] 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.

[22] V. Chepoi and F.F. Dragan. Disjoint sets problem. 1992.

[23] V. Chepoi and F.F. Dragan. A linear-time algorithm for finding a central vertex of a chordal
graph. In ESA, pages 159–170. Springer, 1994.

[24] V. Chepoi and F.F. Dragan. Finding a central vertex in an HHD-free graph. Discrete Applied
Mathematics, 131(1):93–111, 2003.

[25] V. Chepoi, F.F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and
approximating trees of δ-hyperbolic geodesic spaces and graphs. In SocG, pages 59–68. ACM,
2008.

[26] V. Chepoi, F.F. Dragan, M. Habib, Y. Vaxès, and H. Alrasheed. Fast approximation of eccen-
tricities and distances in hyperbolic graphs. Journal of Graph Algorithms and Applications,
23(2):393–433, 2019.

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

[28] V. Chepoi and B. Estellon. Packing and covering δ-hyperbolic spaces by balls. In Approxi-
mation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages
59–73. Springer, 2007.

[29] V. Chepoi, B. Estellon, and Y. Vaxès. Covering planar graphs with a fixed number of balls.
Discrete & Computational Geometry, 37(2):237–244, 2007.

[30] 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.

[31] D. Corneil, F.F. Dragan, and E. Köhler. On the power of BFS to determine a graph’s diameter.
Networks: An International Journal, 42(4):209–222, 2003.

25
[32] 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.

[33] 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.

[34] F.F. Dragan. Centers of graphs and the Helly property. PhD thesis, Moldova State University,
1989.

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

[36] F.F. Dragan. HT-graphs: centers, connected r-domination and Steiner trees. The Computer
Science Journal of Moldova, 1(2):64–83, 1993.

[37] F.F. Dragan. An eccentricity 2-approximating spanning tree of a chordal graph is computable
in linear time. Information Processing Letters, 2019.

[38] F.F. Dragan and A. Brandstädt. r-dominating cliques in graphs with hypertree structure.
Discrete Mathematics, 162(1-3):93–108, 1996.

[39] F.F. Dragan and F. Nicolai. LexBFS-orderings of distance-hereditary graphs with application
to the diametral pair problem. Discrete Applied Mathematics, 98(3):191–207, 2000.

[40] F.F. Dragan, F. Nicolai, and A. Brandstädt. LexBFS-orderings and powers of graphs. In WG,
pages 166–180. Springer Berlin Heidelberg, 1997.

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

[42] A. Dress. Trees, tight extensions of metric spaces, and the cohomological dimension of cer-
tain groups: a note on combinatorial properties of metric spaces. Advances in Mathematics,
53(3):321–402, 1984.

[43] G. Ducoffe. A New Application of Orthogonal Range Searching for Computing Giant Graph
Diameters. In SOSA, 2019.

[44] G. Ducoffe, M. Habib, and L. Viennot. Fast diameter computation within split graphs. In
COCOA, pages 155–167. Springer, 2019.

[45] 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.

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

[47] M. Farber and R. Jamison. Convexity in graphs and hypergraphs. SIAM Journal on Algebraic
Discrete Methods, 7(3):433–444, 1986.

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

26
[49] F. Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal
of Combinatorial Theory, Series B, 16(1):47–56, 1974.

[50] P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann. Voronoi diagrams on

planar graphs, and computing the diameter in deterministic Õ(n5/3 ) time. In SODA, pages
495–514. SIAM, 2018.

[51] A. Goldman. Optimal center location in simple networks. Transportation science, 5(2):212–
221, 1971.

[52] M. Golumbic. Algorithmic graph theory and perfect graphs, volume 57. Elsevier, 2004.

[53] M. Habib, R. McConnell, C. Paul, and L. Viennot. Lex-BFS and partition refinement, with
applications to transitive orientation, interval graph recognition and consecutive ones testing.
Theoretical Computer Science, 234(1-2):59–84, 2000.

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

[55] V.B. Le, A. Oversberg, and O. Schaudt. A unified approach to recognize squares of split
graphs. Theoretical Computer Science, 648:26–33, 2016.

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

[57] J. Matousek. Bounded VC-dimension implies a fractional Helly theorem. Discrete & Compu-
tational Geometry, 31(2):251–255, 2004.

[58] 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.

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

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

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

[62] D. Rose, R. Tarjan, and G. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM
Journal on computing, 5(2):266–283, 1976.

[63] N. Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A,
13(1):145–147, 1972.

[64] S. Sen and V. Muralidhara. The covert set-cover problem with application to Network Dis-
covery. In WALCOM, pages 228–239. Springer, 2010.

[65] S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary
languages. Pacific Journal of Mathematics, 41(1):247–261, 1972.

27
[66] R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs,
test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on
computing, 13(3):566–579, 1984.

[67] J. R. Walter. Representations of rigid cycle graphs. PhD thesis, Wayne State University,
Department of Mathematics, 1972.

[68] R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. The-
oretical Computer Science, 348(2-3):357–365, 2005.

28