Maximum cut optimisation

Question

Consider the algorithm below which calculates a V cut

• Initialize $V_1 = V$ et $V_2 = \emptyset$

• Attempt to improve the value of the cut in any of the following ways

  Check if there is a $v \in V_1$ such as $c(V_1-\{v\}, V_2 \cup \{v\}) > c(V_1,V_2)$

  If yes continue with $V_1 = V_1 -\{v\}$ et $V_2 = V_2 \cup \{v\}$.

  Check if there is a $v \in V_2$ such as $c(V_1 \cup \{v\}, V_2 - \{v\}) > c(V_1,V_2)$ If yes continue with $V_1 = V_1 \cup \{v\}$ et $V_2 = V_2 - \{v\}$.

• When improvement is no longer possible, return the cut $V_1, V_2$

1 . How can I prove that the algorithm is executed in polynomial time by displaying done at most $|E|$ iterations.

Let $(V_1,V_2)$ be a cut. For a $v \in V_1$ we call $\alpha(v)$ the neighbors of $v$ which are in $V_1$ and $\beta(v)$ the neighbors of $v$ which are in $V_2$.If $v \in V_2$, we set $\alpha(v)$ and $\beta(v)$ the neighbors of $v$ which are in $V_2$ and $V_1$ respectively.

2. How to prove that if the algorithm can no longer advance then for everything $v \in V$ we have $|\alpha(v)| \leq |\beta(v)|$​

Answer 1

1) is easy. As you say the algorithm can perform at most $O(|E|)$ iterations. Initially $c(V_1, V_2)=0$. Each iteration, except the last, increases $c(V_1, V_2)$ by at least $1$. The claim follows since $c(V_1, V_2) \le |E|$.

2) Suppose that, for some $v \in V_1$, $|\alpha(v)| > |\beta(v)|$ Then moving $v$ from $V_1$ to $V_2$ increases the value of $c(V_1, V_2)$ by $|\alpha(v)|$ and decreases it by $|\beta(v)|$, therefore $c(V_1 \setminus \{v\}, V_2 \cup \{v \}) = c(V_1, V_2) + |\alpha(v)| - |\beta(v)| > c(V_1, V_2)$. This shows that the algorithm could not have terminated. The case $v \in V_2$ is symmetric.