The Graph Bisection problem is: given a graph G(V,E) of V vertices and E edges, divide V into two subsets with equal number of vertices such that a certain function is optimized.
Usually, this function is the number of edges going from vertices of one set to vertices of the other, also called
the bisection width. Normally, we want to minimize the bisection width (min bipartition), although sometimes we also want to find the max bipartition.
Graph bisection is also often called graph bipartition. Bipartition has many applications, such as in VLSI desgin, network topology, and parallel task scheduling.
Graph Bisection is NP-complete.