Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck
We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. We present stronger lower bounds, improved branching rules, and a new decomposition technique that contracts entire regions of the graph without losing optimality guarantees. In practice, our algorithm works particularly well on instances with relatively small minimum bisections, solving large real-world graphs (with tens of thousands to millions of vertices) to optimality.
In Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12)
Publisher Society for Industrial and Applied Mathematics