This paper explores new solution approaches for the graph partitioning problem. While the classic formulations for graph partitioning are compact, they either suffer from a poor relaxation, symmetry, or contain a cubic number of constraints regardless of the graph density. These shortcomings often result in poor branch-and-bound performance. We approach this problem from perspective of finding a minimum cost multicut such that the connected components of the residual graph are valid partitions. First, we provide a polyhedral description of the multicuts and provide a set covering formulation aimed at partitioning the trees of connected subgraphs. Next, we develop several new extended formulations for the graph partitioning problem and prove they are equal in strength to the triangle formulation, yet are better suited for solving sparse instances. Furthermore, we study the graph partitioning problem over graphs which are trees and develop a pseudo-polynomial dynamic programming algorithm to solve this problem. Finally, we provide an extensive computational study to compare the strength of each formulation.
Article
View Solving Graph Partitioning on Sparse Graphs: Cuts, Projections, and Extended Formulations