Describe a polynomialtime 2approximation algorithm for MAX C

Describe a polynomial-time 2-approximation algorithm for MAX CUT.

Solution

Let us notice that in the algorithm presented in the previous section, the assumption of bounded maximum degree is needed only to obtain an induced bipartite graph. Now we relax this assumption and study the complexity of the method in general graphs. Let us formalize that as Algorithm B. The input of B is a weighted graph G = (V, E, w) and the output is a maximum cut in G with respect to the weight function w. Step 1. Find a maximal independent set I0 in G. Step 2. Find a maximal independent set I1 in G[V \\ I0]. Let B be the union of I0 and I1. Step 3. Enumerate all partitions of elements of V \\ B into two subsets (all 0 1 assignments) and for each find an optimal extension of the partial partition. Step 4. Find a cut C that has the largest weight among all checked in Step 3. Return the cut C. To complete the description of the algorithm, we need to provide a procedure that finds an induced bipartite subgraph in Steps 1 and 2. From Turan’s theorem follows that the size of a maximum independent set is at least n/(d+ 1), and as shown in [7], there is a linear-time algorithm that constructs an independent set of at least that size. As the time complexity of B depends on |B|, we need to give a lower bound on the size of the bipartite subgraph B. Claim 4. The set B of vertices constructed in Step 2 of Algorithm B has size at least 2/(d+ 2). Proof. Let i = |I0| and m0 be the number of edges of the subgraph G[I0 I1]. If i 2n/(d + 2), then |B| 2n/(d + 2) and the claim follows. Suppose i < 2n/(d + 2). The average degree d 0 in the graph G[V I0] is d 0 = 2(m m0 )/(n i). Notice that m0 n i, since I0 is an independent set. Hence, d 0 2n/(n i) 2 and since i < 2n/(d + 2), we have d 0 < d. It follows that |B| = i + (n i)/(d 0 + 1) 2n/(d + 2). Having established the lower-bound on the size of B, we can claim the running time of Algorithm B. Notice that 2/(d + 2) = n/(n + m) and n |B| mn/(m + n). Theorem 5. Algorithm B computes max-cut in a graph G with n vertices and m edges in time O (2mn/(m+n) ), and polynomial space.