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

<p>Strangely enough, the only reference I find to this result is <a href="http://dx.doi.org/10.1109/ICBBE.2008.127">this</a> from a bioinformatics conference. I'd be really curious to see whether it has been proven somewhere else.</p>

<p><strong>Edit:</strong> An earlier reference is: Gary Chartrand: <a href="http://dx.doi.org/10.1137/0114065">A Graph-Theoretic Approach to a Communications Problem</a>, SIAM J. Appl. Math. 14-4 (1966), pp. 778-781.</p>

CC BY-SA 3.0
2012-06-20T19:28:36.260Z
2012-06-21T08:48:02.283Z
2012-06-21T08:48:02.283Z
Falk Hüffner
<p>Chapter 1 of the book The Probabilistic Method, by Alon and Spencer mentions the following problem:</p>

<p>Given a graph $G$, decide if its edge connectivity is at least $n/2$ or not.</p>

<p>The author mentions the existence of a $O(n^3)$ algorithm by Matula and improves it to $O(n^{8/3}\log n)$.</p>

<p>My question is, what's the best known running time for this problem?</p>

<p>Let me describe the improved algorithm.</p>

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

<p>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.</p>

<p>Next, it uses the following not very difficult to prove fact:</p>

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

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

CC BY-SA 3.0
2011-09-05T16:00:25.553Z
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
CC BY-SA 3.0
2011-09-05T16:27:19.920Z
Maybe I am misunderstanding something, but doesn't the Karger-Stein randomized mincut algorithm have running time $\tilde{O}(n^2)$?
Sasho Nikolov
CC BY-SA 3.0
2011-09-05T22:21:56.853Z
Is $O(n^2)$ the expected running time? The algorithm I have described is completely deterministic.
Vinayak Pathak
CC BY-SA 3.0
2011-09-06T02:47:41.853Z
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
CC BY-SA 3.0
2011-09-06T05:34:33.873Z
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
CC BY-SA 3.0
2011-09-06T13:27:57.827Z
Hmm... Do you know the best known bound for max-flow, i.e., given two vertices of the graph, find the max-flow between them? The book uses an algorithm with running time $O(n^{8/3})$. If there exists a better algorithm for this problem, then the algorithm stated in my question can also be improved.
Vinayak Pathak
CC BY-SA 3.0
2011-09-06T14:35:54.813Z
Oh I see. The best algorithm for exact max-flow is Goldberg-Rao with running time $\tilde{O}(m\cdot \min\{n^{2/3}, m^{1/2}\})$, which is $O(n^{8/3})$ in for a dense graph.
Sasho Nikolov
<ds.algorithms><open-problem><graph-algorithms>
Given a graph, decide if its edge connectivity is at least n/2 or not
Vinayak Pathak
# Given a graph, decide if its edge connectivity is at least n/2 or not

(Asked by: username_0 on 2011-09-05)

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

**Tags:** ds.algorithms, open-problem, graph-algorithms
> **Comments:**
> **username_0**: 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?  
> **username_1**: Maybe I am misunderstanding something, but doesn't the Karger-Stein randomized mincut algorithm have running time $\tilde{O}(n^2)$?  
> **username_0**: Is $O(n^2)$ the expected running time? The algorithm I have described is completely deterministic.  
> **username_1**: 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 :)  
> **username_1**: 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).  
> **username_0**: Hmm... Do you know the best known bound for max-flow, i.e., given two vertices of the graph, find the max-flow between them? The book uses an algorithm with running time $O(n^{8/3})$. If there exists a better algorithm for this problem, then the algorithm stated in my question can also be improved.  
> **username_1**: Oh I see. The best algorithm for exact max-flow is Goldberg-Rao with running time $\tilde{O}(m\cdot \min\{n^{2/3}, m^{1/2}\})$, which is $O(n^{8/3})$ in for a dense graph.  

---

## 1 answers

### Answer by username_2 on 2012-06-20. Score: 12

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](http://dx.doi.org/10.1109/ICBBE.2008.127) 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](http://dx.doi.org/10.1137/0114065), SIAM J. Appl. Math. 14-4 (1966), pp. 778-781.


---

