Graph bisection

The graph bisection problem in mathematics consists of dividing a graph into two pieces, such that the pieces are of about the same size and there are few connections between the pieces.

Consider a graph $G(V,E)$, where V denotes the set of vertices and E the set of edges. The standard (unweighted) version of the graph bisection problem is: Given G, partition V into two parts (subsets) V₁, V₂ such that the two parts are disjoint and have equal size, and the number of edges with endpoints in different parts is minimized. In practical applications, a small imbalance in the part sizes is usually allowed.

The graph bisection problem correspond to the graph partitioning problem when the number of partitions is equal to two.