The partition problem (Q2366610): Difference between revisions

The authors are dealing with two graph partitioning problems: \(\text{GPP1}(k)\): partition the node set \(V\) of a given graph \(G=(V,E)\) - - with edge weights \(C(e)\) -- into \(r\) subsets, so as to minimize the total weight of the edges with end points in two different subsets (i.e. the edgecuts) and \(r\leq k\) for a given integer \(k\). \(\text{GPP2}(k)\): partition the \(\dots\) and \(r\geq k\) for a given integer \(k\). Both problems are NP-complete. The paper gives integer programming formulations for both problems, identifies the dimensions of the associated polytopes and explores conditions under which certain kinds of inequalities (non-negativity, cycle inequality, clique inequality, wheel inequality, bicycle wheel inequality resp. for \(\text{GPP2}(k)\): spanning tree inequality, \(q\)-super-tree inequality, \(q\)-cycle-inequality, prism inequality) are facet defining.