Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
3  
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
1  
@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

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
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
5  
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.

share|improve this answer
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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