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

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

• Btw, of course an improvement in the max-flow algorithm will lead to an improvement here as well. But I guess $O(n^{8/3})$ is the best max-flow algorithm known currently? – Vinayak Pathak Sep 5 '11 at 16:00
• Maybe I am misunderstanding something, but doesn't the Karger-Stein randomized mincut algorithm have running time $\tilde{O}(n^2)$? – Sasho Nikolov Sep 5 '11 at 16:27
• Is $O(n^2)$ the expected running time? The algorithm I have described is completely deterministic. – Vinayak Pathak Sep 5 '11 at 22:21
• The algorithm is Monte Carlo: it always completes in time $\tilde{O}(n^2)$ and outputs the minimum cut with high probability. The probability of failure depends inversely on running time, of course. Sorry, given that your citation is Alon-Spencer I just assumed that the algorithm is randomized :) – Sasho Nikolov Sep 6 '11 at 2:47
• If you're looking for a deterministic algorithm I think you should specify that in the question. I am not aware of a deterministic algorithm better than $O(mn + n^2\log n)$ for min cut (see Stoer-Wagner for an easy algorithm that achieves this running time). It's interesting how much better we can do deterministically for the problem you specify (8/3 in the exponent seems unnatural for a best bound, but who knows). – Sasho Nikolov Sep 6 '11 at 5:34

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