Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations

This paper explores integer programming formulations for solving graph partitioning problems that impose an upper limit on the weight of the partition clusters. Traditional efforts have concentrated on studying a model commonly known as the triangular formulation, which has some undesirable properties, like requiring a cubic number of constraints with respect to the number of vertices. We study some alternative formulations arising from different perspectives. In particular, we consider the idea of modeling the problem from the standpoint of an attacker who wants to deteriorate the graph’s integrity by removing edges and show that some of the structural properties of the proposed formulations can be exploited to speed up the solution times. To compare the strength of the formulations’ LP bounds, we study their projection into the space of the edges and show that all of them concentrate on partitioning subtrees of the input graph. Inspired by this observation, we develop a formulation based on a dynamic program for the problem on trees and show how to use it to derive strong valid inequalities for the problem on general graphs. As part of the technical developments of the paper, we also expand the polyhedral characterization of the problem’s solution space, introducing new families of inequalities and provide empirical evidence of their efficacy to improve the quality of the proposed formulations. Finally, we conduct an extensive computational study to compare the strength of our developments.