<p><em><sup>My earlier claim of $\frac{2}{c+6}$ did not take into account the cut of size $n^2/4$ already present in the graph. The following construction appears to result (emperically - I have created a question at math.stackexchange.com for a rigorous proof) in a $O\left(\frac{1}{\log c}\right)$ fraction.</sup></em></p>

<p>The algorithm performs badly on unions of several disconnected, differently sized complete graphs. We denote the complete graph on $n$ vertices as $K_n$. Consider the behavior of the algorithm on $K_n$: it repeatedly adds an arbitrary vertex not yet in $S$ to $S$ - all such vertices are identical and so the order does not matter. Setting the number of vertices not yet added to $S$ by the algorithm $|\bar{S}| = k$, the size of the cut at that moment is $k (n-k)$.</p>

<p>Consider what happens if we run the algorithm on several disconnected $K_{x_i n}$ graphs with $x_i$ constants between 0 and 1. If $k_i$ is the number of elements not yet in $S$ in the $i$th complete graph, then the algorithm will repeatedly add a vertex to $S$ from the complete graph with highest $k_i$, breaking ties arbitrarily. This will induce `round' based additions of vertices to $S$: the algorithm adds a vertex from all complete graphs with the highest $k = k_i$, then from all complete graphs with $k_i=k-1$ (with $k_i$ updated after the previous round), and so on. Once a complete graph has a vertex added to $S$ in a round, it will do so for every round from then on.</p>

<p>Let $c$ be the number of complete graphs. Let $0 &lt; x_i \leq 1$ with $0 \leq i \leq c - 1$ be the size modifier for the $i$-th complete graph. We order these size modifiers from large to small and set $x_0 = 1$. We now have that if there are $c'$ graphs with exactly $k$ elements not yet added to $S$, then the size of the cut at that time is $\sum_{i=0}^{c'-1} k (x_i n - k) = k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$. The total number of edges is $|E| = \sum_{i=0}^{c-1} \frac{x_i n (x_i n - 1)}{2} \approx \frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2$.</p>

<p>Note that $k n \sum_{i=0}^{c'-1} x_i - c' k^2$ is a quadratic function in $k$ and hence has a maximum. We will therefore have several locally maximal cuts. For example, if $c=1$ our maximal cut is at $k=\frac{n}{2}$ of size $\frac{n^2}{4}$. We are going to pick $x_1$ so that $x_1 = 1/2 - \varepsilon$, which means the second complete graph will not change the size of this locally maximal cut at $k=\frac{n}{2}$. We then get a new locally maximal cut at $k=3/8 n - \varepsilon'$ and so we pick $x_2 = 3/8 n - \varepsilon''$ (with $\varepsilon, \varepsilon', \varepsilon''$ small constants). We will ignore the $\varepsilon$s for the moment and just assume we can pick $x_1 = 1/2$ - we should ensure $x_1 n = \frac{n}{2} - 1$, but this will not affect the final results if $n$ is large enough.</p>

<p>We wish to find the local maxima of our cuts. We differentiate $k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$ to $k$, yielding $n \sum_{i=0}^{c'-1} (x_i) - 2 c' k$. Equating to $0$ gives $k = \frac{n}{2c'} \sum_{i=0}^{c'-1} x_i$, which gives a cut of size $\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$.</p>

<p>Let $k_i$ be the $k$ determined in the previous paragraph if $c'=i$. We will ensure that the formula holds by demanding that $x_i n &lt; k_i$ - all complete graphs $i'$ with $i'&gt;i$ are then smaller than the $k_i$ of this locally maximal cut and hence do not increase the size of the cut. This means we have $c$ cuts at these $k_i$ that are larger than all other cuts found by the algorithm.</p>

<p>Filling in $x_i n &lt; k_i$, we get the recurrence $x_i = \frac{1}{2c'} \sum_{i=0}^{c'-1} x_i$ (plus some small $\varepsilon$) with $x_0 = 1$. Solving this yields $x_i = \frac{\binom{2i}{i}}{4^i}$: <a href="https://math.stackexchange.com/q/614746/19258">see my question on math.stackexchange.com</a> for the derivation by @Daniel Fisher. Plugging this into $\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$ and using our insight into the recurrence gives us cuts of size $\frac{n^2}{4c'} \left(2c' \frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = n^2 c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2$. Using <a href="http://en.wikipedia.org/wiki/Central_binomial_coefficient#Properties" rel="nofollow noreferrer">properties of this central binomial coefficient</a>, we have $\lim_{c' \to \infty} c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = \frac{1}{\pi}$ (also see <a href="http://en.wikipedia.org/wiki/Central_binomial_coefficient#Properties" rel="nofollow noreferrer">my question on math.stackexchange.com</a>).</p>

<p>The number of edges is approximately $\frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2 = \frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{\binom{2i}{i}}{4^i}\right)^2$. <a href="http://en.wikipedia.org/wiki/Central_binomial_coefficient#Properties" rel="nofollow noreferrer">By known properties</a> we have $\frac{1}{\sqrt{4i}} \leq \frac{\binom{2i}{i}}{4^i}$. Filing in gives at least $\frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{1}{\sqrt{4i}}\right)^2 = \frac{n^2}{8} \sum_{i=0}^{c-1} \frac{1}{i}$ which is asymptotically $\frac{n^2}{8} \log c$ as $c$ goes to infinity.</p>

<p>We therefore have $\frac{\delta(S, \bar{S})}{|E|}$ is asymptotically equal to $\frac{8}{\pi \log c}$ as $c$ goes to infinity, showing that the algorithm can return cuts that are arbitrarily low fractions of $|E|$.</p>

CC BY-SA 3.0
2013-12-12T23:35:17.593Z
With a slight modification, your construction gives $1/4$. Fix $\varepsilon$ and chose a sufficiently large $N$. Let $V=\{1,\dots, N\}$. Connect every two vertices in $\{1,\dots, \varepsilon N\}$ with an edge; then additionally connect every two vertices in $V$ w.p. $\varepsilon^2$. The total number of edges is approximately $(\varepsilon n)^2 /2 + \varepsilon^2 \cdot (n^2/2) = \varepsilon^2 n^2$. The algorithm finds a cut that cuts approximately $\varepsilon^2 n^2/4$ edges (up to lower order terms in $\varepsilon$).
Yury
CC BY-SA 3.0
2013-12-13T21:15:41.983Z
I think I'll rewrite my answer to just include the final results (with more detail) soon, as it's a bit of a mess right now.
Alex ten Brink
CC BY-SA 3.0
2013-12-21T12:50:58.750Z
Regarding the sum $\frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{\binom{2i}{i}}{4^i}\right)^2$, since each term is $\Theta(1/(i+1))$, the sum is a harmonic series which sums to $\Theta(\log c)$, and in total we get $\Theta(n^2\log c)$.
Yuval Filmus
CC BY-SA 3.0
2013-12-12T20:29:43.047Z
2013-12-21T12:27:15.053Z
2017-04-13T12:19:19.363Z
Alex ten Brink
<p>After a while of thinking and asking around, here's a counter-example, courtesy of <a href="https://mathoverflow.net/users/27663/ami-paz">Ami Paz</a>:</p>

<p>Let $n$ be even and $G$ be a graph which is the union of $K_n$ with a matching of $n+2$ vertices (that is, a matching with $n/2+1$ edges).</p>

<p>How does the algorithm run on this graph? It just takes vertices from the clique part in arbitrary order. After having taken $k$ vertices from the clique, the cut is of size $k\cdot (n-k)$. This is maximal for $k=n/2$, which gives a cut of size $\frac{n^2}{4}$, while the number of edges in the graph is $\frac{n^2}{2}+1$. </p>

<p>The algorithm as prescribed will continue adding vertices from the clique, reducing the number of edges crossing the cut, until what remains from the clique is just a single edge. At this point it cannot obtain anything better than $\frac{n}{2}+2$.</p>

CC BY-SA 3.0
2013-12-11T15:00:56.837Z
Nice counterexample.
Kaveh
CC BY-SA 3.0
2013-12-12T05:52:24.517Z
this still gets very close to $|E|/2$ though. it would be nice to see an example where the algorithm does worse
Sasho Nikolov
CC BY-SA 3.0
2013-12-11T14:40:21.657Z
2013-12-11T14:40:21.657Z
2017-04-13T12:57:54.777Z
Yonatan
<p>OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic:</p>

<p>Given an undirected graph $G=(V,E)$, give an algorithm that finds a cut $(S,\bar{S})$ such that $\delta(S,\bar{S})\geq |E|/2$, where $\delta(S,\bar{S})$ is the number of edges crossing the cut. Time complexity must be $O(V+E)$.</p>

<p>For some reason, I got a lot of the following solution. Now, it does use too much time, so it's not a matter of grading, but I got curious. It doesn't "seem" correct, but all my attempts at counterexamples have failed. Here it is:</p>

<ol>
<li>Set $S\leftarrow \emptyset$</li>
<li>Let $v$ be a max degree vertex in the graph</li>
<li>Add $v$ to $S$</li>
<li>Delete all edges adjacent to $v$</li>
<li>If $\delta(S,\bar{S}) &lt; |E|/2$ return to 2</li>
</ol>

<p>Note that $E$ in step 5 refers to the original graph. Also note that had we skipped step 4, this would obviously be wrong (for example the union of a triangle with two isolated edges).</p>

<p>Now, any simple proof has the following problem - it might be that when we add a new vertex $v$ we actually remove $|S|$ edges from the cut while adding $d(v)$ new edges (where $d(v)$ refers to the graph with edges deleted). The thing is, that if this is detrimental to our cause, it means that this vertex $v$ "used to" have an ever higher degree, so it "should have been" selected earlier.</p>

<p>Is this a well known algorithms? Is there some simple counterexample for it?</p>

CC BY-SA 3.0
2013-12-10T10:40:47.337Z
It looks similar to the 2-approximation for vertex cover. The correct greedy algorithm I think would pick the vertex with more neighbors in the part it is that in the other part and move it till there is no such vertex and it is not difficult to show that at that point the answer is at least $|E|/2$. But the correctness of that algorithm depends on the fact that: we are looking at the difference between the number of neighbors for the vertex in the two sides of the cut and not just max degree. Also the correct algorithm moves vertices in both direction, not just from $\bar{S}$ to $S$.
Kaveh
CC BY-SA 3.0
2013-12-10T16:45:57.643Z
@Kaveh I think OP knows the algorithm you describe (he assigned it as homework). His question is whether the algorithm he describes achieves any approximation.
Sasho Nikolov
CC BY-SA 3.0
2013-12-10T16:50:51.840Z
@Sasho, yes, I know.
Kaveh
CC BY-SA 3.0
2013-12-11T08:59:40.240Z
Random partition of nodes achieves at least $|E|/2$ cut. Finding a better cut is NP-hard.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-11T09:14:50.520Z
@MohammadAl-Turkistany see Nikolov's comment.
vb le
CC BY-SA 3.0
2013-12-11T09:17:46.413Z
Also, note that 16/17 approximation is NP-hard, not 1/2. GW give ~0.878 approximation using SDP in their seminal paper.
Yonatan
CC BY-SA 3.0
2013-12-11T15:09:24.810Z
@Yonatan See this question http://cstheory.stackexchange.com/questions/3846/is-max-cut-approximation-resistant
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-12T05:47:56.757Z
@MohammadAl-Turkistany I think maybe you misunderstood the answer to the question you cite. finding a cut better than $|E|/2$ is not always possible, but when a cut of value $|E|/2 + \delta|E|$ exists, you can find efficiently a cut of value $|E|/2 + (\delta/\log n) |E|$ (and doing better is hard)
Sasho Nikolov
<graph-algorithms><max-cut><greedy-algorithms>
Max-Cut algorithm that shouldn't work, unclear why
Yonatan
# Max-Cut algorithm that shouldn't work, unclear why

(Asked by: username_0 on 2013-12-10)

OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic:

Given an undirected graph $G=(V,E)$, give an algorithm that finds a cut $(S,\bar{S})$ such that $\delta(S,\bar{S})\geq |E|/2$, where $\delta(S,\bar{S})$ is the number of edges crossing the cut. Time complexity must be $O(V+E)$.

For some reason, I got a lot of the following solution. Now, it does use too much time, so it's not a matter of grading, but I got curious. It doesn't "seem" correct, but all my attempts at counterexamples have failed. Here it is:

1. Set $S\leftarrow \emptyset$
2. Let $v$ be a max degree vertex in the graph
3. Add $v$ to $S$
4. Delete all edges adjacent to $v$
5. If $\delta(S,\bar{S}) < |E|/2$ return to 2

Note that $E$ in step 5 refers to the original graph. Also note that had we skipped step 4, this would obviously be wrong (for example the union of a triangle with two isolated edges).

Now, any simple proof has the following problem - it might be that when we add a new vertex $v$ we actually remove $|S|$ edges from the cut while adding $d(v)$ new edges (where $d(v)$ refers to the graph with edges deleted). The thing is, that if this is detrimental to our cause, it means that this vertex $v$ "used to" have an ever higher degree, so it "should have been" selected earlier.

Is this a well known algorithms? Is there some simple counterexample for it?

**Tags:** graph-algorithms, max-cut, greedy-algorithms
> **Comments:**
> **username_1**: It looks similar to the 2-approximation for vertex cover. The correct greedy algorithm I think would pick the vertex with more neighbors in the part it is that in the other part and move it till there is no such vertex and it is not difficult to show that at that point the answer is at least $|E|/2$. But the correctness of that algorithm depends on the fact that: we are looking at the difference between the number of neighbors for the vertex in the two sides of the cut and not just max degree. Also the correct algorithm moves vertices in both direction, not just from $\bar{S}$ to $S$.  
> **username_2**: @Kaveh I think OP knows the algorithm you describe (he assigned it as homework). His question is whether the algorithm he describes achieves any approximation.  
> **username_1**: @Sasho, yes, I know.  
> **username_3**: Random partition of nodes achieves at least $|E|/2$ cut. Finding a better cut is NP-hard.  
> **username_4**: @MohammadAl-Turkistany see Nikolov's comment.  
> **username_0**: Also, note that 16/17 approximation is NP-hard, not 1/2. GW give ~0.878 approximation using SDP in their seminal paper.  
> **username_3**: @Yonatan See this question http://cstheory.stackexchange.com/questions/3846/is-max-cut-approximation-resistant  
> **username_2**: @MohammadAl-Turkistany I think maybe you misunderstood the answer to the question you cite. finding a cut better than $|E|/2$ is not always possible, but when a cut of value $|E|/2 + \delta|E|$ exists, you can find efficiently a cut of value $|E|/2 + (\delta/\log n) |E|$ (and doing better is hard)  

---

## 2 answers

### Answer by username_5 on 2013-12-12. Score: 13

*My earlier claim of $\frac{2}{c+6}$ did not take into account the cut of size $n^2/4$ already present in the graph. The following construction appears to result (emperically - I have created a question at math.stackexchange.com for a rigorous proof) in a $O\left(\frac{1}{\log c}\right)$ fraction.*

The algorithm performs badly on unions of several disconnected, differently sized complete graphs. We denote the complete graph on $n$ vertices as $K\_n$. Consider the behavior of the algorithm on $K\_n$: it repeatedly adds an arbitrary vertex not yet in $S$ to $S$ - all such vertices are identical and so the order does not matter. Setting the number of vertices not yet added to $S$ by the algorithm $|\bar{S}| = k$, the size of the cut at that moment is $k (n-k)$.

Consider what happens if we run the algorithm on several disconnected $K\_{x\_i n}$ graphs with $x\_i$ constants between 0 and 1. If $k\_i$ is the number of elements not yet in $S$ in the $i$th complete graph, then the algorithm will repeatedly add a vertex to $S$ from the complete graph with highest $k\_i$, breaking ties arbitrarily. This will induce `round' based additions of vertices to $S$: the algorithm adds a vertex from all complete graphs with the highest $k = k\_i$, then from all complete graphs with $k\_i=k-1$ (with $k\_i$ updated after the previous round), and so on. Once a complete graph has a vertex added to $S$ in a round, it will do so for every round from then on.

Let $c$ be the number of complete graphs. Let $0 < x\_i \leq 1$ with $0 \leq i \leq c - 1$ be the size modifier for the $i$-th complete graph. We order these size modifiers from large to small and set $x\_0 = 1$. We now have that if there are $c'$ graphs with exactly $k$ elements not yet added to $S$, then the size of the cut at that time is $\sum\_{i=0}^{c'-1} k (x\_i n - k) = k n \sum\_{i=0}^{c'-1} (x\_i) - c' k^2$. The total number of edges is $|E| = \sum\_{i=0}^{c-1} \frac{x\_i n (x\_i n - 1)}{2} \approx \frac{n^2}{2} \sum\_{i=0}^{c-1} x\_i^2$.

Note that $k n \sum\_{i=0}^{c'-1} x\_i - c' k^2$ is a quadratic function in $k$ and hence has a maximum. We will therefore have several locally maximal cuts. For example, if $c=1$ our maximal cut is at $k=\frac{n}{2}$ of size $\frac{n^2}{4}$. We are going to pick $x\_1$ so that $x\_1 = 1/2 - \varepsilon$, which means the second complete graph will not change the size of this locally maximal cut at $k=\frac{n}{2}$. We then get a new locally maximal cut at $k=3/8 n - \varepsilon'$ and so we pick $x\_2 = 3/8 n - \varepsilon''$ (with $\varepsilon, \varepsilon', \varepsilon''$ small constants). We will ignore the $\varepsilon$s for the moment and just assume we can pick $x\_1 = 1/2$ - we should ensure $x\_1 n = \frac{n}{2} - 1$, but this will not affect the final results if $n$ is large enough.

We wish to find the local maxima of our cuts. We differentiate $k n \sum\_{i=0}^{c'-1} (x\_i) - c' k^2$ to $k$, yielding $n \sum\_{i=0}^{c'-1} (x\_i) - 2 c' k$. Equating to $0$ gives $k = \frac{n}{2c'} \sum\_{i=0}^{c'-1} x\_i$, which gives a cut of size $\frac{n^2}{4c'} \left(\sum\_{i=0}^{c'-1} x\_i\right)^2$.

Let $k\_i$ be the $k$ determined in the previous paragraph if $c'=i$. We will ensure that the formula holds by demanding that $x\_i n < k\_i$ - all complete graphs $i'$ with $i'>i$ are then smaller than the $k\_i$ of this locally maximal cut and hence do not increase the size of the cut. This means we have $c$ cuts at these $k\_i$ that are larger than all other cuts found by the algorithm.

Filling in $x\_i n < k\_i$, we get the recurrence $x\_i = \frac{1}{2c'} \sum\_{i=0}^{c'-1} x\_i$ (plus some small $\varepsilon$) with $x\_0 = 1$. Solving this yields $x\_i = \frac{\binom{2i}{i}}{4^i}$: [see my question on math.stackexchange.com](https://math.stackexchange.com/q/614746/19258) for the derivation by @Daniel Fisher. Plugging this into $\frac{n^2}{4c'} \left(\sum\_{i=0}^{c'-1} x\_i\right)^2$ and using our insight into the recurrence gives us cuts of size $\frac{n^2}{4c'} \left(2c' \frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = n^2 c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2$. Using [properties of this central binomial coefficient](http://en.wikipedia.org/wiki/Central_binomial_coefficient#Properties), we have $\lim\_{c' \to \infty} c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = \frac{1}{\pi}$ (also see [my question on math.stackexchange.com](http://en.wikipedia.org/wiki/Central_binomial_coefficient#Properties)).

The number of edges is approximately $\frac{n^2}{2} \sum\_{i=0}^{c-1} x\_i^2 = \frac{n^2}{2} \sum\_{i=0}^{c-1} \left(\frac{\binom{2i}{i}}{4^i}\right)^2$. [By known properties](http://en.wikipedia.org/wiki/Central_binomial_coefficient#Properties) we have $\frac{1}{\sqrt{4i}} \leq \frac{\binom{2i}{i}}{4^i}$. Filing in gives at least $\frac{n^2}{2} \sum\_{i=0}^{c-1} \left(\frac{1}{\sqrt{4i}}\right)^2 = \frac{n^2}{8} \sum\_{i=0}^{c-1} \frac{1}{i}$ which is asymptotically $\frac{n^2}{8} \log c$ as $c$ goes to infinity.

We therefore have $\frac{\delta(S, \bar{S})}{|E|}$ is asymptotically equal to $\frac{8}{\pi \log c}$ as $c$ goes to infinity, showing that the algorithm can return cuts that are arbitrarily low fractions of $|E|$.

> **Comments:**
> **username_6**: With a slight modification, your construction gives $1/4$. Fix $\varepsilon$ and chose a sufficiently large $N$. Let $V=\{1,\dots, N\}$. Connect every two vertices in $\{1,\dots, \varepsilon N\}$ with an edge; then additionally connect every two vertices in $V$ w.p. $\varepsilon^2$. The total number of edges is approximately $(\varepsilon n)^2 /2 + \varepsilon^2 \cdot (n^2/2) = \varepsilon^2 n^2$. The algorithm finds a cut that cuts approximately $\varepsilon^2 n^2/4$ edges (up to lower order terms in $\varepsilon$).  
> **username_5**: I think I'll rewrite my answer to just include the final results (with more detail) soon, as it's a bit of a mess right now.  
> **username_7**: Regarding the sum $\frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{\binom{2i}{i}}{4^i}\right)^2$, since each term is $\Theta(1/(i+1))$, the sum is a harmonic series which sums to $\Theta(\log c)$, and in total we get $\Theta(n^2\log c)$.  

---

### Answer by username_0 on 2013-12-11. Score: 12

After a while of thinking and asking around, here's a counter-example, courtesy of [Ami Paz](https://mathoverflow.net/users/27663/ami-paz):

Let $n$ be even and $G$ be a graph which is the union of $K\_n$ with a matching of $n+2$ vertices (that is, a matching with $n/2+1$ edges).

How does the algorithm run on this graph? It just takes vertices from the clique part in arbitrary order. After having taken $k$ vertices from the clique, the cut is of size $k\cdot (n-k)$. This is maximal for $k=n/2$, which gives a cut of size $\frac{n^2}{4}$, while the number of edges in the graph is $\frac{n^2}{2}+1$.

The algorithm as prescribed will continue adding vertices from the clique, reducing the number of edges crossing the cut, until what remains from the clique is just a single edge. At this point it cannot obtain anything better than $\frac{n}{2}+2$.

> **Comments:**
> **username_1**: Nice counterexample.  
> **username_2**: this still gets very close to $|E|/2$ though. it would be nice to see an example where the algorithm does worse  

---

