3
$\begingroup$

I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes:

  1. problems, where we know of a lower bound expression in terms of decision tree complexity, but lower bounds not mentioning decision tree complexity are unknown, this would be the case with minimum spanning tree
  2. problems, where there is no known expression of lower bounds in terms of other complexity measures, an example would be All-Pair shortest paths

Both examples are based on my limited knowledge of the literature

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ You may want to look at surveys on fine-grained complexity. Virginia Williams from MIT has several pointers on her web page. people.csail.mit.edu/virgi $\endgroup$ – Chandra Chekuri Jun 4 '20 at 5:14
  • 3
    $\begingroup$ In a sense, almost all problems that have no known linear-time algorithms satisfy your requirement. $\endgroup$ – Yixin Cao Jun 4 '20 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.