# The time complexity of finding the diameter of a graph

What is the time complexity of finding the diameter of a graph $G=(V,E)$?

• ${O}(|V|^2)$
• ${O}(|V|^2+|V| \cdot |E|)$
• ${O}(|V|^2\cdot |E|)$
• ${O}(|V|\cdot |E|^2)$

The diameter of a graph $G$ is the longest distance between two vertices in graph.

I have no idea what to do about it, I need a complete analysis on how to solve a problem like this.

-
Please elaborate a tad. Why is this problem of interest to you? Do you need a hint, a complete analysis or a reference? Are you interested in worst- or average-case time? Is $G$ directed? –  Raphael Mar 10 '12 at 12:52
@Raphael: Obviously I don't need a hint, I need a complete analysis. I edited my question anyway. –  Gigili Mar 10 '12 at 13:04
@Gigili You mean $\Theta$ in all cases, right? Otherwise, all are subsumed by the last possibility (which is on general graphs equal to $\cal{O}(|V|^5)$) which makes it a correct answer, assuming at least one answer is supposed to be correct. An additional concern is that in a graph with cycles, there is no longest path. What is meant by "longest distance"? –  Raphael Mar 10 '12 at 13:31
@Gigili Where do the four choices come from? –  uli Mar 10 '12 at 13:50

### Update:

This solution is not correct.

The solution is unfortunately only true (and straightforward) for trees! Finding the diameter of a tree does not even need this. Here is a counterexample for graphs (diameter is 4, the algorithm returns 3 if you pick this $v$):

If the graph is directed this is rather complex, here is some paper claiming faster results in the dense case than using algorithms for all-pairs shortest paths.

However my main point is about the case the graph is not directed and with non-negative weigths, I heard of a nice trick several times:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

Its complexity is the same as two successive breadth first searches¹, that is $O(|E|)$ if the graph is connected².

It seemed folklore but right now, I'm still struggling to get a reference or to prove its correction. I'll update when I'll achieve one of these goals. It seems so simple I post my answer right now, maybe someone will get it faster.

¹ if the graph is weighted, wikipedia seems to say $O(|E|+|V|\log|V|)$ but I am only sure about $O(|E|\log|V|)$.

² If the graph is not connected you get $O(|V|+|E|)$ but you may have to add $O(α(|V|))$ to pick one element from each connected component. I'm not sure if this is necessary and anyway, you may decide that the diameter is infinite in this case.

-
To mkae Dijsktra work in the time bound specified you need to use Fibonacci heaps, not the usual implementation. –  Suresh Mar 11 '12 at 6:43
This is strongly wrong answer, this algorithm is folklore but in trees not general graphs. P.S: I can see your counter example, but it's not good answer to be marked as answer. –  user742 Apr 2 '12 at 23:15

I assume you mean the diameter of $G$ which is the longest shortest path found in $G$.

Finding the diameter can be done by finding all pair shortest paths first and determining the maximum length found. Floyd-Warshall algorithm does this in $\Theta(|V|^3)$ time. Johnson's algorithm can be implemented to achieve $\cal{O}(|V|^2\log |V| + |V|\cdot|E|)$ time.

A smaller worst-case runtime bound seems hard to achieve as there are $\cal{O}(|V|^2)$ distances to consider and calculating those distance in sublinear (amortised) time each is going to be tough; see here for a related bound. Note this paper which uses a different approach and obtains a (slightly) faster algorithm.

-
If you get paywalled on those papers, check Google Scholar. –  Raphael Mar 10 '12 at 14:12

You can also consider an algebraic graph theoretic approach. The diameter $\text{diam}(G)$ is the least integer $t$ s.t. the matrix $M=I+A$ has the property that all entries of $M^t$ are nonzero. You can find $t$ by $O(\log n)$ iterations of matrix multiplication. The diameter algorithm then requires $O(M(n) \log n)$ time, where $M(n)$ is the bound for matrix multiplication. For example, with the generalization of the Coppersmith-Winograd algorithm by Vassilevska Williams, the diameter algorithm would run in $O(n^{2.3727} \log n)$. For a quick introduction, see Chapter 3 in Fan Chung's book here.

If you restrict your attention to a suitable graph class, you can solve the APSP problem in optimal $O(n^2)$ time. These classes include at least interval graphs, circular arc graphs, permutation graphs, bipartite permutation graphs, strongly chordal graphs, chordal bipartite graphs, distance-hereditary graphs, and dually chordal graphs. For example, see Dragan, F. F. (2005). Estimating all pairs shortest paths in restricted graph families: a unified approach. Journal of Algorithms, 57(1), 1-21 and the references therein.

-
It's worth noting that this algorithm only works in the unweighted case. –  GMB Jan 23 at 13:32