Chapter 1 of the book The Probabilistic Method, by Alon and Spencer mentions the following problem:
Given a graph $G$, decide if its edge connectivity is at least $n/2$ or not.
The author mentions the existence of a $O(n^3)$ algorithm by Matula and improves it to $O(n^{8/3}\log n)$.
My question is, what's the best known running time for this problem?
Let me describe the improved algorithm.
First, decide if $G$ has its minimum degree at least $n/2$ or not. If not, then the edge connectivity is clearly less than $n/2$.
Next, if that is not the case, then compute a dominating set $U$ of $G$ of size $O(\log n)$. This can be done in time $O(n^2)$, by an algorithm described in the previous section of the book.
Next, it uses the following not very difficult to prove fact:
If the minimum degree is $\delta$, then for any edge cut of size at most $\delta$ that divides $V$ into $V_1$ and $V_2$, any dominating set of $G$ must have its vertices in both $V_1$ and $V_2$.
Now consider the dominating set $U = \{u_1, \ldots , u_k\}$. Since $G$ has minimum degree $n/2$, any edge cut of size less than $n/2$ must also separate $U$. Thus for each $i\in \{2, k\}$, we find the size of the smallest edge cut that separates $u_1$ and $u_i$. Each of these things can be done in time $O(n^{8/3})$ using a max-flow algorithm. Thus total time taken is $O(n^{8/3}\log n)$.