An old open problem asks whether the diameter of a graph (the maximum distance between any two vertices) can be computed more quickly than all pairwise shortest paths (APSP). In arXiv:1011.6181, Raphael Yuster shows that the answer (for unweighted directed graphs) is yes. Or at least, he provides the first algorithm for computing diameter that is faster in the worst case (for dense graphs) that is faster than known APSP algorithms.

Both the new algorithm and the known fastest APSP algorithms are based on fast matrix multiplication techniques, and have running times that depend in complicated ways on the bounds for matrix multiplication. The APSP algorithm of Zwick (JACM 2002) takes time \( O(n^{2.616}) \) using the best known matrix multiplication algorithms, while the new diameter algorithm takes time \( O(n^{2.575}) \).

One of the things I found intriguing about this paper is the connection it makes between approximate and exact algorithms. There's been a lot of work in recent years on algorithms for computing shortest paths approximately, more quickly than they can be computed exactly. The main idea of Yuster's paper seems to be that these approximations can then be used to find a small set of candidate pairs, one of which is guaranteed to be a diametral pair.

Another curiosity among this week's arXiv algorithm submissions: two papers on the same problem, minimum dominating sets in claw-free graphs. It's long been known that domination problems behave somewhat nicely on claw-free graphs: there exists a minimum dominating set that is also an independent set, and the largest independent set (necessarily itself a dominating set) can be found in polynomial time. However, the minimum dominating set problem remains NP-complete in these graphs. The two new papers both show that it's fixed-parameter tractable. They don't reference each other, which I guess means that they're independent discoveries. I haven't read the papers carefully enough to have an opinion on which one's algorithms are preferable, but I like the second title better: "Domination when the Stars Are Out". Shades of Lovecraft?




Comments:

eternal_spring:
2010-12-06T19:56:51Z

With this information, might you be able to answer one -- or both -- of the following Stack/MathOverflow questions?

Good algorithm for finding the diameter of a (sparse) graph? http://stackoverflow.com/q/1190543 http://mathoverflow.net/questions/11444

Neither received satisfactory answers, and I'd be happy to accept an answer with the information you know.

Thanks.

11011110:
2010-12-06T20:01:31Z

Thanks for the pointers, but I don't think this new paper really helps answer those questions. The problem is that the improvements it describes only kick in (compared to the much easier approach of doing n different BFS's, one from each possible starting vertex) for dense graphs, whereas the overflow questions are about sparse graphs.

I'll put an answer referring to it on the mathoverflow one, though (I don't have a stackoverflow account) because it is at least closely related enough to be worth mentioning.

eternal_spring:
2010-12-06T20:13:48Z

Yes, I saw the dense/sparse issue.

On the other hand, you seem to have the knowledge that "an old open problem asks whether the diameter of a graph (the maximum distance between any two vertices) can be computed more quickly than all pairwise shortest paths". This also answers my questions.

Thanks.

virgi:
2010-12-08T00:23:12Z

Just a small comment: APSP in directed unweighted graphs is in \( n^{2.575} \) time via Zwick's algorithm (if you use rectangular matrix multiplication); Raphy shows that the diameter can be solved in slightly better than that time: \( n^{2.561} \). I also find it interesting for the following reason: usually in shortest paths papers we split the problem into two different cases (low degree/high degree or short path/long path etc); Raphy managed to find a way to split the algorithm into three instead of two cases, thus getting an improvement. I'm actually quite convinced that APSP should be in \( n^{\omega} \) time, and this may be something like a half-step in that direction :)

11011110:
2010-12-08T00:28:05Z

Thanks for the correction, and even more for the insight.

I didn't know you had an LJ! But you don't seem to be posting much to it.

virgi:
2010-12-08T00:40:04Z

Yes, I'm not much of a blogger but I do read other people's posts occasionally :-)

raphael_yuster:
2011-01-14T09:15:14Z

Thanks David for mentioning this.

I just posted to the ArXiv a revised version that also handles the integer weighted case (both positive and negative weights) using essentially the same algorithm (and with the same sub-APSP running time).

For positive only weights I included a new algorithm that runs in \( O(Mn^w) \) time (edge weights in \( 1\dots M \)).

On the other hand, the purely unweighted case turns out to have a much simpler solution (as observed in some lecture notes of Uri Zwick) that is based on repeated squaring of boolean matrices and binary searching for the right exponent. This does not, however, work for the weighted case (not even for weights in \( \{-1,0,1\}\) ) so the algorithm in the paper is indeed the first algorithm that is sub-APSP for the general integer weighted setting.