This is second in a series of node your homework! writeups

The proof is by reduction from max-cut (see Garey and Johnson). The series of reductions goes this way: max-cut --> max bisection --> (minimum) Graph Bisection.

First given the input graph to max-cut of n vertices and e edges, we transform it by placing n additional independent vertices. We note that given the original input, we can always distribute the n additional vertices among the two subsets such that the number of vertices in the subsets are equal. So now, solving the max-bisection problem on the transformed input is equivalent to solving the max-cut problem.

From max bisection, we can transform the input by getting the complement of the input to max bisection (the complement is obtained by adding edges where there was none, and removing edges if they originally existed in the source graph). Now, since the min bisection of the transformed graph is actually the max bisection of the original graph.

Thus, any algorithm solving the min-bisection solves the max bisection problem, which in turn solves the max-cut problem, which is NP-complete.

This is based heavily on the proof from