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.