Skip to main content
Log in

On the cut polytope

  • Published:
Mathematical Programming Submit manuscript

Abstract

The cut polytopeP C (G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofP C (G). We describe three methods with which new facet-defining inequalities ofP 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 ofP C (G) ifG is not contractible toK 5. We give a simple characterization of adjacency inP C (G) and prove that for complete graphs this polytope has diameter one and thatP C (G) has the Hirsch property. A relationship betweenP C (G) and the convex hull of incidence vectors of balancing edge sets of a signed graph is studied.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. F. Barahona, “On the computational complexity of Ising spin glass models,”Journal of Physics A Mathematics and General 15 (1982) 3241–3250.

    Article  MathSciNet  Google Scholar 

  2. F. Barahona, “The max cut problem in graphs not contractible toK 5,”Operations Research Letters 2 (1983) 107–111.

    Article  MATH  MathSciNet  Google Scholar 

  3. F. Barahona, M. Grötschel and A.R. Mahjoub, “Facets of the bipartite subgraph polytope,”Mathematics of Operations Research 10 (1985) 340–358.

    Article  MATH  MathSciNet  Google Scholar 

  4. M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).

    MATH  Google Scholar 

  5. M. Grötschel, L. Lovász and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–197.

    Article  MATH  MathSciNet  Google Scholar 

  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.

    MATH  MathSciNet  Google Scholar 

  7. F.O. Hadlock, “Finding a maximum cut of planar graph in polynomial time”,SIAM Journal on Computing 4 (1975) 221–225.

    Article  MATH  MathSciNet  Google Scholar 

  8. F. Harary, “On the notion of balance of a signed graph,”The Michigan Mathematic Journal 2 (1953) 143–146.

    Article  Google Scholar 

  9. P.D. Seymour, “Matroids and multicommodity flows,”European Journal of Combinatorics 2 (1981) 257–290.

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

The research of this author was performed at the Institut fur Operations Research, Universität Bonn, West Germany, and supported by the Alexander von Humbold Stiftung.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Barahona, F., Mahjoub, A.R. On the cut polytope. Mathematical Programming 36, 157–173 (1986). https://doi.org/10.1007/BF02592023

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02592023

Key words

Navigation