8
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Jun 27, 2012 at 14:17
  • $\begingroup$ @RobinKothari I have edited the question now I am looking for lower bounds in PRAM/RAM models. Do you suggest any more changes? $\endgroup$
    – rizwanhudda
    Jun 27, 2012 at 17:05

1 Answer 1

Reset to default
3
$\begingroup$

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].

Despite being a restricted model, it is strong enough to compute the determinant efficiently, and includes most standard algorithms for poly-time combinatorial optimization problems. See here, here, or the original paper for more details.

[1] Mulmuley, K. Lower Bounds in a Parallel Model without Bit Operations. SIAM J. Comput., 28(4), 1460–1509, 1999. (from author's webpage without paywall)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.