zbMATH — the first resource for mathematics

On the cut polytope. (English) Zbl 0616.90058
The cut polytope \(P_ C(G)\) of a graph \(G=(V,E)\) is the convex hull of the incidence vectors of all edge sets of cuts of G. We show some classes of facet-defining inequalities of \(P_ C(G)\). We describe three methods with which new facet-defining inequalities of \(P_ C(G)\) can be constructed from known ones. In particular, we show that inequalities associated with chordless cycles define facets of this polytope; moreover, for these inequalities a polynomial algorithm to solve the separation problem is presented. We characterize the facet defining inequalities of \(P_ C(G)\) if G is not contractible to \(K_ 5\). We give a simple characterization of adjacency in \(P_ C(G)\) and prove that for complete graphs this polytope has diameter one and that \(P_ C(G)\) has the Hirsch property. A relationship between \(P_ C(G)\) and the convex hull of incidence vectors of balancing edge sets of a signed graph is studied.

90C27 Combinatorial optimization
52Bxx Polytopes and polyhedra
90C35 Programming involving graphs or networks
Full Text: DOI
[1] F. Barahona, ”On the computational complexity of Ising spin glass models,”Journal of Physics A Mathematics and General 15 (1982) 3241–3250.
[2] F. Barahona, ”The max cut problem in graphs not contractible toK 5,”Operations Research Letters 2 (1983) 107–111. · Zbl 0525.90094
[3] F. Barahona, M. Grötschel and A.R. Mahjoub, ”Facets of the bipartite subgraph polytope,”Mathematics of Operations Research 10 (1985) 340–358. · Zbl 0578.05056
[4] M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). · Zbl 0411.68039
[5] M. Grötschel, L. Lovász and A. Schrijver, ”The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–197. · Zbl 0492.90056
[6] M. Grötschel and G.L. Nemhauser, ”A polynomial algorithm for the max-cut problem on graphs without long odd cycles”,Math. Programming 29 (1984) 28–40. · Zbl 0532.90074
[7] F.O. Hadlock, ”Finding a maximum cut of planar graph in polynomial time”,SIAM Journal on Computing 4 (1975) 221–225. · Zbl 0321.05120
[8] F. Harary, ”On the notion of balance of a signed graph,”The Michigan Mathematic Journal 2 (1953) 143–146. · Zbl 0056.42103
[9] P.D. Seymour, ”Matroids and multicommodity flows,”European Journal of Combinatorics 2 (1981) 257–290. · Zbl 0479.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.