Graph Diameter#

For a graph $G = (V, E)$, the eccentricity of a vertex $v \in V$ is the maximum distance between $v$ and another vertex, i.e., essentially the height of the BFS-tree rooted in $v$. The diameter of $G$ is the largest eccentricity over all vertices.

A vertex with minimum eccentricity 2, one with maximum
eccentricity 4, and the corresponding diameter path of length 4. — page 1 — A vertex with minimum eccentricity 2, one with maximum eccentricity 4, and the corresponding diameter path of length 4.

A vertex with minimum eccentricity 2, one with maximum
eccentricity 4, and the corresponding diameter path of length 4. — page 2 — A vertex with minimum eccentricity 2, one with maximum eccentricity 4, and the corresponding diameter path of length 4.

It’s Hard#

The diameter can be trivially computed by running a BFS from every vertex, yielding running time $O(nm)$. For sparse graphs, this is the best we can do: under OV, there is no $O(n^{2 - \varepsilon})$ algorithm that distinguishes between diameter 2 or 3 in sparse graphs [3, 4].

Typical Inputs#

It is probably fair to say that real-world networks are an important type of input for computing the diameter.

There are probably other applications where computing the diameter appears as a subproblem. It would be nice to have a collection of instances coming from such applications.

Too Easy!#

There are actually multiple diameter algorithms that are way too fast. To name two examples:

BoundingDiameters runs a BFS from only 21 vertices to compute the diameter of the social network hyves with 8 M vertices and 871 M edges [5].
iFUB runs a BFS from only 7 vertices to compute the diameter of the computer network as-skitter with 1.7 M vertices and 22 M edges [6].

iFUB#

The iFUB algorithm [6] first computes a central vertex $c$ that (hopefully) has low eccentricity. Afterwards it runs a BFS from all vertices that are far away from the center $c$. Assume we have run the BFS for every vertex with distance at greater than $d$. Then any future BFS from the remaining vertices can only yield new paths of length at most $2d$, as we can always go via the vertex $c$. Thus, if we have already found a shortest path of length $2d$, we can stop.

Vertex $v$ has eccentricity $2d$.
Between any two vertices in the blue region, the distance is at most
$2d$. Thus, if we have done a BFS form every vertex outside the blue
region, we have found the diameter. — page 1 — Vertex $v$ has eccentricity $2d$. Between any two vertices in the blue region, the distance is at most $2d$. Thus, if we have done a BFS form every vertex outside the blue region, we have found the diameter.

There are different heuristics to find a central vertex.

max degree

Choose a vertex of maximum degree.

double sweep

Start with an arbitrary vertex $u$ chooses a vertex $v$ at maximum distance, with the idea that $v$ is at the “periphery” of the graph. As central vertex, choose a vertex $w$ that is in the middle layer of the BFS tree of $v$.

4-sweep

Run two double sweeps, starting the second double sweep with the result of the first double sweep. One can also start the first double sweep with a vertex of maximum degree.

BoundingDiameters#

BoundingDiameters [5] makes use of the following observation. Running a BFS from one vertex to compute its eccentricity also lets us learn something about the eccentricity of other vertices. Specifically, if two vertices $u$ and $v$ have distance $d$, then their eccentricities differ by at most $d$.

Running a BFS from $v$
tells us not only that $v$'s eccentricity is $4$, but also that $u$
and $w$ have eccentricity between $3$ and $5$. — page 1 — Running a BFS from $v$ tells us not only that $v$’s eccentricity is $4$, but also that $u$ and $w$ have eccentricity between $3$ and $5$.

This yields lower and upper bounds for the eccentricities, which in turn yield lower and upper bounds for the diameter. The algorithm BoundingDiameters essentially tries to pick a small set of root vertices $R \subseteq V$, such that running a BFS from each root suffices to know the exact diameter. This is done by iteratively adding vertices to $R$. A vertex $v$ is excluded from being added to $R$ if:

the lower and upper eccentricity bound for $v \in V$ coincide or
improving the eccentricity bound of $v$ can no longer improve the diameter bound (e.g., its eccentricity is known to be smaller than the diameter).

The search is stopped, if:

there are no root-candidates left or
the upper and lower bound for the diamter coincide.

There are different strategies for selecting the next root [5]. Alternating between vertices with small lower bound and vertices with high upper bond on their eccentricity is most successful.

SumSweep#

The SumSweep algorithm [13] is similar to BoundingDiameters but works for arbitrary directed graphs. The core differences come from dealing with the graph being directed, e.g., the algorithm maintains a forward and backward eccentricity and for each root a forward and backward BFS are performed.

It is probably fair to view SumSweep as an extension of BoundingDiameters and to assume that insights for the former likely translate to the latter.

WTF?#

There are multiple approaches attempting to explain the good performance, together yielding a decent understanding.

Locality and Heterogeneity#

The experiments in [1] study how many BFS runs iFUB requires depending on locality and heterogeneity, comparing generated graphs with real-world networks.

Locality, heterogeneity, and graph models.

The locality of a graph measures how distant the endpoints of an edge are in the rest of the graph. Think of high locality as: the graph has an underlying geometry, it has many triangles, there is a high dependence between the edges.

The heterogeneity of a graph describes the variance of the degree distribution. Road networks are homogeneous with all vertices having roughly the same degree. Social networks tend to be heterogeneous with low average degree and a heavy tail of few high-degree vertices (think power-law).

The experiment setup in [1] is roughly as follows. Generate graphs with varying locality and heterogeneity (and constant average degree). Locality is achieved with an underlying geometry. Heterogeneity is achieved with connection probabilities depending on vertex weights. This essentially provides a clean lab-environment, where one can observe how the running time of algorithms changes depending on locality and heterogeneity in isolation from other graph properties. These experiments on generated graphs are complemented and compared with experiments on a large number of real-world networks from different domains.

Insight#

On inputs that have locality or a heterogeneous degree distribution (or both), we can expect iFUB with 4-sweep to be fast. Notable exception: Graphs with an underlying geometry that wraps around (e.g., sphere or torus).

Explanatory Power#

The empirical observations paint a coherent picture.

One can observe a clear dependence on locality and heterogeneity that is consistent between generated and real-world networks.

Changing the heuristic that selects the central vertex consistently impacts the running time for different graphs between generated and real-world networks.

For homogeneous graphs with geometry, the models predict good performance unless the geometry wraps around (sphere, torus, etc.). Visualizations of real-world graphs with matching properties and bad performance show wrapping geometry.

Limitations#

These are only experiments, not proofs.

The number of BFS runs has high variance, even for the model when generating multiple graphs with the same parameter. This indicates that a theoretical analysis on the model might be difficult and that the properties locality and heterogeneity do not fully capture the running time behavior.

Random Geometric Graphs#

In [14], there is an analysis of iFUB on random geometric graphs (RGG). RGGs are usually obtained by placing vertices at random positions in the unit square and connecting vertices that are close. Alternatively, a torus RGG is generated by using the flat torus instead (i.e., unit square with opposite sides identified).

Insight#

On random geometric graphs with average degree $n^x$, iFUB with double sweep runs a BFS from $\tilde O(n^{1 - \frac{2}{3}x})$ vertices. On torus RGGs, it requires $\Omega(n)$ BFS runs.

Explanatory Power#

The theoretical result matches the general trend of the empirical observations: RGGs are prototypical for homogeneous graphs with locality, which should result in a low running time, unless the geometry wraps around.

Limitations#

The upper bounds are very far from matching empirical performance. It in particular makes no statement about sparse graphs.

Power-Law Graphs#

One can obtain strong performance bounds for iFUB and SumSweep by assuming four (rather technical) properties that I would summarize as follows [20]:

The size of the BFS layers for different vertices of the same degree grows at a similar rate.
Let $A \subseteq V$ and $B \subseteq V$ be the $i$-th and $j$-th layer of a BFS from $s \in V$ and $t \in V$, respectively. If $|A| \cdot |B| \ge n^{1 + \varepsilon}$, then $\mathrm{dist}(s, t) \le i + j$, i.e., the BFS search spaces from $s$ and $t$ have met after $i$ respectively $j$ steps.
The search spaces in property 2 rarely meet much earlier.
The degree distribution follows a power law.

Properties 2 and 3 can in a sense be viewed as requiring sufficient stochastic independence between edges such that the birthday paradox can be applied: An edge between $A$ and $B$ is likely if and only if there are enough pairs of vertices in $A \times B$ that could form an edge.

Insight#

On graphs satisfying properties 1 – 4 (power-law degree distribution, stochastic independence of edges, uniform search-space growth), iFUB and SumSweep run in almost linear time.

Explanatory Power#

The almost linear upper bounds are quite strong and fit well to the empirical observations.

The deterministic properties make it so that the results are not specific to just one probabilistic network model.

The authors provide experiments that aim to validate the properties for real-world networks.

Limitations#

The results are restricted to graphs with a power-law degree distribution and logarithmic diameter.

Many real-world networks have strong dependence between edges. Properties 2 and 3 requiring enough independence to apply the birthday paradox seem questionable in this context.

The properties are very complicated. Also see the discussion on deterministic properties.

The properties are difficult to check:

They involve asymptotics using big O notation, which is not meaningful for individual inputs.

Statements on search-space growth are difficult to check when there are only few steps due to a logarithmic diameter.

Small Certificates#

The efficiency of BoundingDiameters and iFUB is based on the existence of a small diameter certificate: a small set of vertices $X \subseteq V$ such that knowing the distance from every vertex in $x$ to all other vertices provides matching upper and lower bounds for the diameter. With this, one can ask these two questions:

Why do many practical inputs have a small diameter certificates?
If there is a small diameter certificate, why can it be found efficiently?

Question 2 is answered positively by [21]:

Insight#

If there is a truly sublinear diameter certificate, then there is a truly subquadratic randomized algorithm finding it.

Explanatory Power#

The considered certificates fit to those found by algorithms that are efficient in practice.

There are several graphs classes that have small diameter certificates [21]. This to some degree also answers question 1 of why many inputs have small certificates.

Limitations#

For constant certificates, the running time is still $O(m \sqrt{n})$, which is quite pessimistic.

While this provides an algorithm that finds a small certificate (somewhat) efficiently, this does not explain why the specific strategies of BoundingDiameters or iFUB find it efficiently.

One could argue that this parameter (size of a diameter certificate) is quite close to the running time; see the discussion on deterministic properties.

References#

On the External Validity of Average-case Analyses of Graph Algorithms by Thomas Bläsius, Philipp Fischbeck (2023)
Fast approximation algorithms for the diameter and radius of sparse graphs by Liam Roditty, Virginia Vassilevska Williams (2013)
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs by Karl Bringmann, ‪Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian (2022)
Determining the diameter of small world networks by Frank W. Takes, Walter A. Kosters (2011)
On computing the diameter of real-world undirected graphs by Pilu Crescenzi, Roberto Grossi, Michel Habib, L. Lanzi, Andrea Marino (2012)
Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs by Michele Borassi, Pierluigi Crescenzi, Michel Habib, Walter A. Kosters, Andrea Marino, Frank W. Takes (2015)
Diameter Computation on (Random) Geometric Graphs by Thomas Bläsius, Annemarie Schaub, Marcus Wilhelm (2026)
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs by Michele Borassi, Pierluigi Crescenzi, Luca Trevisan (2017)
Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs by Feodor F. Dragan, Guillaume Ducoffe, Michel Habib, Laurent Viennot (2025)