11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For the computation of diameter, once the clique tree is given, chordal graphs behave (almost) the same as trees. Likewise, in an interval graph, a dominating pair (which exists in any AT-free graphs) necessarily decides the diameter. $\endgroup$ – Yixin Cao Jun 30 '13 at 13:08
  • $\begingroup$ @YixinCao But in general, the number of distinct clique trees a chordal graph can have is exponential in the number of vertices. Futhermore, I don't think the diameter is the same in every clique tree. I think this is a problem, but in a ur-chordal graph the diameter of the clique tree is unambigious. Did you have something else in mind? $\endgroup$ – Juho Jun 30 '13 at 13:23
  • $\begingroup$ I'm not saying the diameter of the chordal graph is the same as that of its clique tree. (A star of $k+1$ vertices can have a clique tree that is a path of $k$ nodes.) What I meant is the diameter of the graph must be between some pair of leaves (any simplicial vertex in it) in the clique tree. $\endgroup$ – Yixin Cao Jun 30 '13 at 18:17
  • $\begingroup$ @YixinCao OK, now I understand better. Even so, a (fast) algorithm is still not obvious to me. If you have any additional details or references, please feel free! $\endgroup$ – Juho Jun 30 '13 at 18:58
9
$\begingroup$

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.

rising sun graph
(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.

$\endgroup$
  • $\begingroup$ Interesting, thanks! And yes, I did mean $O(n+m)$ rather than $o(n^2)$. Seems like the graphs I care about at the moment don't contain either of the subgraphs mentioned, so this is indeed nice. $\endgroup$ – Juho Jul 1 '13 at 17:17
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.