Maximum cut using a 1/2 approximation greedy algorithm

Question

I have the following greedy algorithm for max cut problem:

1. Initialization: $A \leftarrow \{v_1\}$ , $B \leftarrow \{v_2\}$

2. For $v \in V − \{v_1, v_2\}$ do:

   if $d(v,A) \geq d(v,B)$ then $B \leftarrow B \cup \{v\}$,

   else $A \leftarrow A \cup \{v\}$.

3. Output $A$ and $B$.

Here, $v_1$ and $v_2$ are arbitrary vertices in $G$ and $d(v,A)$ denotes the number of edges between vertex $v$ and set $A \subset V$.

To show that this is a factor 1/2 approximation algorithm, I used the upper bound that $opt \leq |E|$ and internal_degree(v) and external_degree(v).

But there is a problem, I can not say that when the algorithm terminates, we have external_degree(v) $\geq$ internal_degree(v) for all v (there is a counterexample) , of course since each vertex is check once so time complexity is O(n).

Is there any other way to show this factor?

Answer 1

Let us say that an edge $(v,w)$ belongs to $v$ if when $v$ is processed, $w \in A \cup B$, and that $(v_1,v_2)$ belongs to $v_2$. Denote by $N_v$ the number of edges belonging to $v$, and by $C_v$ the number of those edges that are cut by the algorithm. Step 2 ensures that $C_v \geq N_v/2$ (this clearly holds for $v = v_2$ as well). Therefore $\sum_v C_v \geq \sum_v N_v/2$. Finally, notice that $\sum_v N_v$ is the number of edges in the graph, and $\sum_v C_v$ is the size of the cut produced by the algorithm.

Here is a sketch of another proof. At any point in time, define the score of an edge $(u,v)$ as follows:

• If $u,v \in A$ or $u,v \in B$, the score is 0.
• If $u \in A$ and $v \in B$ or vice versa, the score is 1.
• Otherwise the score is 1/2.

You can check that the initial score is at least half the number of edges, the score never decreases, and the final score is number of edges cut by the algorithm.