Suppose $\Gamma(V, E)$ is a strongly connected oriented graph and $|V| = n$. Let’s define distance from vertex $v_1$ to vertex $v_2$ as the minimal possible length $d(v_1, v_2)$ of an oriented path from $v_1$ to $v_2$. Let’s define variance of a vertex $v$ as $\sum_{u \in V} (d(v, u))^2$. What is the computational complexity of finding a vertex with minimal variance? The graph is given by its adjacency matrix.
On one hand, it is clearly $\Omega(n^2)$ because it takes that time to process the input. On the other hand, there exists an algorithm that works for $O(n^3)$:
Firstly, we use DFS to determine the distances from any vertex to any vertex. DFS is $O(n^2)$ and will be initiated $n$ times. Thus $O(n^3)$. Then we calculate the variances of each vertex using the distances. That’s $O(n^2)$. And then we choose the vertex with the minimal one. Thats $O(n)$. $O(n^3) + O(n^2) + O(n) = O(n^3)$.
But maybe some better algorithm exists...