Lower bounds to the Graph Partitioning Problem through generalized linear programming and network flows

The well-known Graph Partitioning Problem (GPP), has many applications, both in its weighted and unweighted versions: optimal VLSI circuit design and layout, systems analysis, data analysis and clustering, decomposition of large scale mathematical programming problems, etc. The authors investigate here a new way of getting lower bounds based on a reformulation as a large scale set partitioning problem, where the columns correspond to all subsets of the vertex set X. It is shown that the continuous relaxation of this large scale problem can be solved exactly by means of a generalized linear programming technique, the column generation process being reducible to maximum network flow computations. Preliminary computational results on a number of small-to-medium sized problems are reported, and directions for future investigations are suggested in the conclusion.