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 gettinglower bounds for problems like: Shortest Paths(with/without negative weights), Mincut, s-t Maximum flows, Maximum (cardinality/weighted) matching. Any references related tothis 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-201EDIT: As suggested by Robin Kothari in the comments, I am making the question more directed.
Lower Bounds on Running time of Graph Algorithms
cc.complexity theory;reference request;graph algorithms;lower bounds