# Lower Bounds on Running time of Graph Algorithms

Are there any non-trivial lower bounds on the running time of graph algorithms in RAM/PRAM/ models of computation ? I am not looking for the NP-Hardness results here.

Following is a result that I could find [see ref L92]:

• 3-Coloring of an n-cycle requires $\Omega(\log^*{n})$ time.

I was curious to know whether there has been any progress/work in the direction of getting lower bounds for problems like: Shortest Paths(with/without negative weights), Mincut, s-t Maximum flows, Maximum (cardinality/weighted) matching. Any references related to this are very much appreciated and helpful.

Reference

[ L92 ] N. Linial, Locality in distributed graph algorithms, SIAM Journal on Com- puting, 1992, 21(1), pp. 193-201

EDIT: As suggested by Robin Kothari in the comments, I am making the question more directed.

• Without restricting the model, an adequate answer to this question could go on for pages. Besides the restriction to graph problems, this question is basically asking "What lower bounds are known in CS?" And the restriction to graph problems isn't a strong one, since in models in which we can prove good lower bounds for some problem (e.g., streaming, decision trees, communication complexity), we can prove good lower bounds for graph problems too. Commented Jun 27, 2012 at 14:17
• @RobinKothari I have edited the question now I am looking for lower bounds in PRAM/RAM models. Do you suggest any more changes? Commented Jun 27, 2012 at 17:05

In the PRAM model without bit operations, fairly strong lower bounds are known. For example, in this model, one cannot solve min-cut in $O(\sqrt{n})$ time on $2^{O(\sqrt{n})}$ processors [1].