<p>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:</p>

<ol>
<li>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</li>
<li>problems, where there is no known expression of lower bounds in terms of other complexity measures, an example would be All-Pair shortest paths</li>
</ol>

<p>Both examples are based on my limited knowledge of the literature</p>

CC BY-SA 4.0
2020-06-04T05:14:43.293Z
You may want to look at surveys on fine-grained complexity. Virginia Williams from  MIT has several pointers on her web page. http://people.csail.mit.edu/virgi/
Chandra Chekuri
CC BY-SA 4.0
2020-06-04T14:02:00.773Z
In a sense, almost all problems that have no known linear-time algorithms satisfy your requirement.
Yixin Cao
<graph-theory><graph-algorithms><time-complexity><big-list>
Graph problems in P with unknown lower bounds
Ilk
# Graph problems in P with unknown lower bounds

(Asked by: username_0 on 2020-06-04)

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

**Tags:** graph-theory, graph-algorithms, time-complexity, big-list

> **Comments:**
> **username_1**: You may want to look at surveys on fine-grained complexity. Virginia Williams from  MIT has several pointers on her web page. http://people.csail.mit.edu/virgi/  
> **username_2**: In a sense, almost all problems that have no known linear-time algorithms satisfy your requirement.  

---

## 0 answers

