The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998

Detailed Solutions

Chapter 8, Problem 24

As in the case of VC, a deceptively simple iterative algorithm actually works. The algorithm is very simple indeed: start from any cut at all -- even from the empty cut into (V,empty) if so desired. Denote the current cut by (S,V-S); as long as moving one vertex from S to V-S or from V-S to S increases the number of cut edges, carry out the move and update S appropriately. Once no more improvement can be made with the transfer of a single vertex, stop and return the current cut. This is clearly a polynomial-time algorithm -- even with a very naïve implementation, each step takes at most |V|² time and, since we have |E| edges in all and must improve the cut by at least 1 at each step, the number of steps is bounded by |E|, so that even a naïve implementation must run in O(|E|*|V|²) time. We claim the the cut returned by this algorithm cuts as least half as many edges as the optimal cut. Denote an optimal cut by (T,V-T); let S₁=S inter T, S₂=S-T, S₃=T-S, and S₄=V-(S union T). Then we can write the approximate solution as (S₁ union S₂,S₃ union S₄) and the optimal solution as (S₁ union S₃,S₂ union S₄). Let us consider what we know about the number of edges between vertices in S and vertices in S_j, for 1 <= i # j <= 4, call it n_ij. By construction the approximate solution cannot be improved by moving any single vertex across the cut; thus, in particular, if we consider a vertex in S₁, the number of edges connecting it to other vertices in S₁ and S₂ is no larger than the number of edges connecting it to vertices in S₃ and S₄. Summing this inequality over all vertices in S₁, we get 2n₁₁+n₁₂ <= n₁₃+n₁₄ Of course, the exact same reasoning can be made about the other three subsets, so we get in all


      2n₁₁+n₁₂ <= n₁₃+n₁₄
      2n₂₂+n₁₂ <= n₂₃+n₂₄
      2n₃₃+n₃₄ <= n₁₃+n₂₃
      2n₄₄+n₃₄ <= n₁₄+n₂₄

Each of these numbers is at least 0, so we can drop the first term in each inequality and write


      n₁₂ <= n₁₃+n₁₄
      n₁₂ <= n₂₃+n₂₄
      n₃₄ <= n₁₃+n₂₃
      n₃₄ <= n₁₄+n₂₄

Combining the four inequalities yields n₁₂+n₃₄ <= n₁₃+n₁₄+n₂₃+n₂₄ Note that the right-hand side is exactly the number of edges cut in the approximate solution; the left-hand side is a subset of the edges cut by the optimal solution -- we need to add in n₁₄+n₂₃. We write n₁₄+n₂₃ <= n₁₃+n₁₄+n₂₃+n₂₄ which is obviously true (again because no number is negative) and add it to our previous inequality to yield n₁₂+n₁₄+n₂₃+n₃₄ <= 2(n₁₃+n₁₄+n₂₃+n₂₄) or, in shorthand optimal <= 2*approximate which proves the result.