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||E|)
  • O(|V|2|E|)
  • O(|V||E|2)

The diameter of a graph G is the maximum of the set of shortest path distances between all pairs of vertices in a graph.

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

Answer

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):

enter image description here


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.

Attribution
Source : Link , Question Author : Gigili , Answer Author : Community

Leave a Comment