21
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Kaveh Dec 10 '13 at 10:40
  • 3
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Dec 10 '13 at 16:45
  • 2
    $\begingroup$ @MohammadAl-Turkistany see Nikolov's comment. $\endgroup$ – vb le Dec 11 '13 at 9:14
  • 1
    $\begingroup$ Also, note that 16/17 approximation is NP-hard, not 1/2. GW give ~0.878 approximation using SDP in their seminal paper. $\endgroup$ – Yonatan Dec 11 '13 at 9:17
  • 1
    $\begingroup$ @Yonatan See this question cstheory.stackexchange.com/questions/3846/… $\endgroup$ – Mohammad Al-Turkistany Dec 11 '13 at 15:09
13
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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$). $\endgroup$ – Yury Dec 12 '13 at 23:35
  • $\begingroup$ 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. $\endgroup$ – Alex ten Brink Dec 13 '13 at 21:15
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Dec 21 '13 at 12:50
12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Nice counterexample. $\endgroup$ – Kaveh Dec 11 '13 at 15:00
  • $\begingroup$ this still gets very close to $|E|/2$ though. it would be nice to see an example where the algorithm does worse $\endgroup$ – Sasho Nikolov Dec 12 '13 at 5:52

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.