No label defined (Q3974969)

[For the entire collection see Zbl 0726.00015.] Given an undirected graph \(G=(V,E)\), a multicut is the set of edges connecting two different clusters of some partition of \(V\). The order of a multicut is the number of corresponding clusters. A multicut is \(s\)- balanced if different clusters have cardinalities differing by at most \(s\). A multicut polyhedron of \(G\) is the convex hull in \(R^ E\) of the incidence vectors of the multicuts of \(G\) with some particular property. In this paper these polyhedra are studied for following properties: all \(s\)-balanced multicuts, those of order at most (resp. at least or equal to) \(k\), and this for any \(s\). The aim is to describe families of facet generating inequalities. The main part of the text consists of a complete enumeration of the facets of all these polyhedra for the complete graph on 5 vertices. This leads to the determination of several families of facets for the multicut polyhedra of higher order complete graphs. The paper ends with a similar, but much simpler, complete description for the complete 4-graphs.