Graph classes for which the diameter can be computed in linear time

Question

Recall the diameter of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) and returns the length of the longest path found.

It is known that the APSP problem can be solved in optimal $O(n^2)$ time for several graph classes. For general graphs, there is an algebraic graph theoretic approach running in $O(M(n) \log n)$ time, where $M(n)$ is the bound for matrix multiplication. However, computing the diameter is apparently not critically linked to APSP, as shown by Yuster.

Are some non-trivial graph classes known for which the diameter can be computed even faster, say in linear time?

I am especially interested in chordal graphs, and any subclasses of chordal graphs such as block graphs. For example, I think the diameter of a chordal graph $G$ can be computed in $O(n+m)$ time, if $G$ is uniquely representable as a clique tree. Such a graph is also known as ur-chordal.

Answer 1

The eccentricity of a vertex $v$ is the length of a longest shortest path starting from $v$. The diameter is the maximal eccentricity over all vertices. Any BFS from a vertex will establish its eccentricity. A key idea for efficient diameter finding is therefore to preprocess the graph to find a small set of vertices, at least one of which achieves maximal eccentricity.

Running a lexicographic breadth-first search, the end-vertex often has high eccentricity. In particular, it is guaranteed to have eccentricity at most one less than the diameter for chordal graphs. For some subclasses of chordal graphs such as interval graphs, it is guaranteed to have maximal eccentricity. This also holds for some non-chordal classes such as $\{\text{AT},\text{claw}\}$-free graphs.

LBFS and BFS are both linear in the size of the graph, but of course if $m = \Omega(n^2)$ (such as $K_n$) then the runtime will not be $o(n^2)$. Your discussion implies that you probably really want a linear algorithm $O(m+n)$ rather than $o(n^2)$.

So for some subclasses of chordal graphs, a linear algorithm is to run LBFS, take the end-vertex, then run BFS starting at that vertex. For chordal graphs this will determine the diameter with an error of at most 1. The graphs for which this is exact seem to be those where the even powers are chordal. These are precisely those chordal graphs that contain no rising sun or $(\text{rising sun}- K_2)$ subgraph that preserves distances.

_{(source: graphclasses.org)}

• Feodor F. Dragan, Falk Nicolai and Andreas Brandstädt, LexBFS-orderings and powers of graphs, WG 1996, LNCS 1197, 166–180. doi:10.1007/3-540-62559-3_15

I do not know if this can be extended to compute the diameter for all chordal graphs precisely. Corneil's survey seems to indicate that this was still open in 2004. I also don't know if an analysis has been done on extending the search from one vertex to a small constant number or $\log n$ starting vertices; this might be interesting to explore.

• Derek G. Corneil, Lexicographic Breadth First Search – A Survey, WG 2004, LNCS 3353, 1–19. doi:10.1007/978-3-540-30559-0_1

Answer 2

The mentioned block graphs in the question are distance-hereditary. A linear time algorithm for computing the diameter for distance-hereditary graphs is given in [1] (see Theorem 5).

---

[1] Dragan, Feodor F. Dominating cliques in distance-hereditary graphs. Springer Berlin Heidelberg, 1994.