Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

My question on Stack Overflow was recently tagged "math". Despite a bounty, it never received a satisfactory answer, so I thought I would ask it here:

I have a large, connected, sparse graph in adjacency-list form. I would like to find the diameter of the graph and two vertices achieving it.

Is there a better approach than computing all-pairs shortest paths?

I am interested in this problem in both the undirected and directed cases, for different applications. In the directed case, I of course care about directed distance (the maximum over pairs of vertices of the length of the shortest directed path from the first vertex to the second).

share|improve this question
    
See the "non-matrix methods" section of sawww.epfl.ch/SIC/SA/publications/SCR98/scr10-page3.html –  Steve Huntsman Jan 11 '10 at 16:49
1  
@Steve: Thanks for the reference. Their "matrix methods" section essentially runs the Bellman–Ford algorithm in time O(V^3). Their "non-matrix methods" sections runs Dijktra for each vertex, which is Johnson's algorithm at O(V^2 log V + VE). However, they combine this with an upper bound for the diameter, obtained from the diameter of the minimum spanning tree (which can be computed quite efficiently). Unfortunately, if their bound is not met (and they have no reason to believe it will be), their suggestion is simply Johnson's algorithm for all-pairs shortest paths. –  aorq Jan 11 '10 at 17:17
1  
Do you need the exact diameter, or would approximate methods suffice? (I have the suspicion that an exact "truly subcubic" diameter finding algorithm would yield a subcubic all-pairs shortest paths algorithm on unweighted graphs. But note, the latter can be theoretically solved in matrix multiplication time...) –  Ryan Williams Jan 13 '10 at 1:45
1  
I just wonder. If the graph is a tree, then there is a simple trick. Just, start with a point, find the point furthest away. Then search the point furthest away from that point. Then you have the longest path (or one of them, in case of multiple solutions). Suppose you apply the same method on a graph, instead of tree. The points on the paths already found, can not be the end points of such longest path. So, you skip them as potential candidates. You repeat this, until all points have been tried. Could this work? –  Lucas K. Dec 6 '10 at 21:04
add comment

6 Answers 6

up vote 6 down vote accepted

It's only helpful in the dense case, not the sparse case that you're asking about, but Yuster has recently shown that the diameter of an unweighted directed graph can in fact be computed more efficiently than known algorithms for all pairs shortest paths. See his paper "Computing the diameter polynomially faster than APSP" on arXiv:1011.6181.

share|improve this answer
add comment

In general it does not seem that the diameter computation implies APSP. Indeed If the graph is undirected the following can be applied.

Pilu Crescenzi, Roberto Grossi, Michel Habib, Leonardo Lanzi, Andrea Marino: On computing the diameter of real-world undirected graphs. TCS 2012.

and if the graph is directed the following can be applied.

Pierluigi Crescenzi, Roberto Grossi, Leonardo Lanzi, Andrea Marino: On Computing the Diameter of Real-World Directed (Weighted) Graphs. SEA 2012.

In the worst case the complexity of these methods is the same as computing APSP, but in real world cases it has been experimentally shown that they run in O(m), where m is the number of edges. Both can be used even if the graph is weighted.

Regards

Andrea Marino

share|improve this answer
add comment

For road networks: http://arxiv.org/abs/1209.4761

share|improve this answer
add comment

There is a rather nice algorithm by Johnson, with time $O(n^2 log n + mn)$; the reference is D. Johnson, Efficient algorithms for shortest paths in sparse graphs, Journal of the ACM, 24:1--13, 1977.

share|improve this answer
    
I asked if there was a better approach than computing all-pairs shortest paths. Johnson's algorithm computes all-pairs shortest paths by running Dijkstra for each vertex (after a preprocessing step take makes weights non-negative). –  aorq Jan 11 '10 at 17:11
1  
Well, I more or less doubt one can compute the diameter without doing work equivalent to computing all shortests paths... –  Mariano Suárez-Alvarez Jan 12 '10 at 0:58
add comment

It is a longstanding open problem whether it is possible to compute the shortest path between a particular pair of vertices in time less than known algorithms for computing all-pairs shortest path. So you are asking whether there is an algorithm for computing the maximum over the set of all shortest paths that runs faster than any known algorithm for computing any particular shortest path.

I'm pretty sure the answer is no, but I can't off the top of my head think of a reduction to the single pair shortest path problem.

share|improve this answer
    
What? Computing the shortest path between a pair of vertices takes at most as long as the single-source shortest path problem, which can be solved by Dijkstra's algorithm in time O(V log V + E). The best known all-pairs shortest path algorithm is Johnson's algorithm (running Dijkstra for each vertex), which takes time O(V^2 log V + VE). What's this "longstanding open problem"? –  aorq Jan 12 '10 at 15:43
    
Djikstra's algorithm does not work for negative edge weights; for this, you need Bellman Ford, which runs in time O(|V||E|) = O(|V|^3) for dense graphs. The best algorithm for the all-pairs shortest paths is Floyd-Warshall, which also runs in time O(|V|^3). Note that Johnson's algorithm is faster only on sparse graphs. –  Wilson Jan 12 '10 at 17:31
    
I see, thanks for the details. However, my question above is for unweighted, sparse graphs. At worst, I can restrict to sparse graphs with positive weights. –  aorq Jan 12 '10 at 20:47
add comment
  1. Extract MST.
  2. Find its diameter.
  3. Or am I wrong? :)
share|improve this answer
1  
The diameter of the MST can be larger than the diameter of the underlying graph. For instance even if the underlying graph is something as simple as an unweighted complete graph, its diameter is one but any tree has diameter at least two. –  David Eppstein Apr 17 '11 at 17:59
    
@David; The nice counterexample of yours. PS I was too sleepy at the time of my answering. Have a nice day, everybody! –  trg787 Apr 18 '11 at 3:08
add comment

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.