In the MAXIMUM CUT problem we are given an undirected graph G = (V, E) with a weight w(e)...

In the MAXIMUM CUT problem we are given an undirected graph G = (V, E) with a weight w(e) on each edge, and we wish to separate the vertices into two sets S and V – S so that the total weight of the edges between the two sets is as large as possible.

For each S ⊆ V, define w(S) to be the sum of all wuv over all edges {u, v} such that |S ∩ {u, v}| = 1. Obviously, MAX CUT is about maximizing w(S) over all subsets of V.

Consider the following local search algorithm for MAX CUT:

 start with any S ⊆ V
 while there is a subset S' c V such that
  |(S' –S) ∪ (S – S')|=1 and w(S') > w(S) do:
   set S = S'

(a) Show that this is an approximation algorithm for MAX CUT with ratio 2.

(b) But is it a polynomial-time algorithm?