Given a graph, decide if its edge connectivity is at least n/2 or not

Question

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)$.

Answer 1

You can easily check this in linear time, since a graph has edge connectivity at least $n/2$ if and only if its minimum degree is at least $n/2$. You already argued for the “only if” part. Consider now a graph where every vertex has degree at least $n/2$ and a cut that divides the graph into two vertex sets $X$ and $\bar X$ with $x := |X| \leq n/2$. A vertex in $X$ can have at most $x - 1$ connections to other vertices in $X$, and thus must contribute at least $n/2 - (x - 1)$ edges to the cut. Thus, the cut must have size at least $x (n/2 - x + 1)$. It remains to show that $x (n/2 - x + 1) \geq n/2$, which is true since $(x - 1)(n/2 - x) \geq 0$.

Strangely enough, the only reference I find to this result is this from a bioinformatics conference. I'd be really curious to see whether it has been proven somewhere else.

Edit: An earlier reference is: Gary Chartrand: A Graph-Theoretic Approach to a Communications Problem, SIAM J. Appl. Math. 14-4 (1966), pp. 778-781.