Improved compact formulations for a wide class of graph partitioning problems in sparse graphs

Given an undirected connected graph G=(V,E) where |V|=n and |E|=m, we consider a wide class of graph partitioning problems, which includes as special cases several versions classically considered in the literature. These problems are to find a partition of the nodes in V into clusters satisfying several generic constraints (of set function type) on the clusters, in order to minimize the number (or the total weight) of the edges whose end-nodes do not belong to the same cluster. Partitions of V are often modeled by using compact integer programming formulations containing O(n3) triangle inequalities. The latter is the same whatever the sparsity of graph G could be, i.e. its size does not depend on m. In this paper, we show that one can reduce the size of the integer programming formulation to O(nm) triangle inequalities. Moreover, it is shown that, when the additional constraints on the clusters satisfy some monotonicity property, the strength of the linear programming relaxation is preserved by this reduction. We present numerical experiments on two important special cases arising from applications to show the benefit in terms of computational efficiency of using the reduced formulation.