Max-Cut algorithm that shouldn't work, unclear why

Question

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?

Answer 1

^{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 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, 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).

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

Answer 2

After a while of thinking and asking around, here's a counter-example, courtesy of 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$.