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

  • $\begingroup$ 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? $\endgroup$ Sep 5 '11 at 16:00
  • $\begingroup$ Maybe I am misunderstanding something, but doesn't the Karger-Stein randomized mincut algorithm have running time $\tilde{O}(n^2)$? $\endgroup$ Sep 5 '11 at 16:27
  • 2
    $\begingroup$ Is $O(n^2)$ the expected running time? The algorithm I have described is completely deterministic. $\endgroup$ Sep 5 '11 at 22:21
  • 3
    $\begingroup$ 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 :) $\endgroup$ Sep 6 '11 at 2:47
  • $\begingroup$ 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). $\endgroup$ 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$.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.