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