Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Question

Consider the following local search approximation algorithm for the unweighted max cut problem: start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you can move 1 or 2 vertices from one side of the partition to the other, or switch between 2 vertices on opposite sides of the partition, in a way that improves the cut, do so.

I know that this algorithm is a 2-approximation algorithm. I want to prove that this approximation is tight. That is, the algorithm is not an $\alpha$-approximation algorithm for any $\alpha < 2$ .

I found an example for the tightness of the "regular" local search approximation algorithm of max-cut, where at each iteration, you can move only 1 vertex from one side of the partition to the other, and can't switch between two vertices on opposite sides. The example is of the complete bipartite graph $ K_{2n,2n} $. If the initial cut includes $n$ vertices from each side of the graph in each side of the partition, the cut will include half of the edges, while the optimal cut will include all of them. The "regular" algorithm will not be able to improve the cut from this initial position.

However, this example doesn't work for the algorithm described on top, because we can improve the cut by switching between two vertices from opposite sides of the partition.

Can someone please describe an example or a give clue for an example that can prove that the approximation is tight? Thanks.

Answer 1

Let's denote by $u_1,\ldots,u_{2n}$ and $v_1,\ldots,v_{2n}$ the nodes in the two sides of $K_{2n,2n}$ respectively. We remove the $2n$ edges $(u_1,v_1),(u_2,v_2),\ldots,(u_{2n},v_{2n})$ from $K_{2n,2n}$. You can verify the resulting graph is an example showing the approximation ratio of your algorithm is at least $2-1/n$, when the initial cut is $\left(\{u_1,\ldots,u_n,v_1,\ldots,v_n\},\{u_{n+1},\ldots,u_{2n},v_{n+1},\ldots,v_{2n}\}\right)$.

Answer 2

Here is an illustration.

The graph is a slight modification on your example of $ K_{2n,2n}$. It is the complete bipartite graph of vertices sets $\{0,1,2,\cdots, 2n-1\}$ and $\{2n, 2n+1,\cdots, 4n-1\}$, plus edges $\{0,2n-1\}, \{1, 2n-2\}, \cdots, \{n-1, n\}$, $\{2n, 4n-1\}, \{2n+1, 4n-2\}, \cdots, \{3n-1,4n\}$. The initial cut is shown by that red line in the middle. We can check that cut cannot be improved by moving 1 or 2 vertices from one side of the partition to the other, nor by switching 2 vertices on opposite sides of the cut.

The maximum cut is along the original complete bipartite graph, which has $2n\cdot 2n=4n^2$ edges. The cut above has $2n^2+2n$. The approximation ratio is $$\frac{2n^2+2n}{4n^2}=\frac12+\frac{1}{2n}.$$

---

Exercise. Show that the algorithm is not an $\alpha$-approximation algorithm for any $\alpha > \frac12$ even if we are allowed to switch up to $k$ points for some fixed $k$.