Graph bisection

Graph bisection is the problem of partitioning the vertices of a graph into two subsets of equal (or nearly equal) size such that the number of edges crossing between the subsets is minimized. Unlike the general graph partition problem, which allows arbitrary subset sizes, bisection imposes a strict balance constraint that makes it both more constrained and more representative of real-world load-balancing problems. The problem is NP-hard in general, but the Fiedler vector provides a polynomial-time approximation whose quality is bounded by Cheeger\'s inequality.

The graph bisection problem appears wherever a system must be divided into two comparable halves with minimal interaction between them: parallel computing, VLSI design, and minimum bisection algorithms for community detection. The constraint of equal size is what makes the problem difficult — without it, the minimum cut can be found by isolating a single vertex, a trivial solution that is useless in practice.