Abstract
Given a graphG = (V, E), the metric polytopeS (G) is defined by the inequalitiesx(F) − x(C∖F) ⩽ |F| − 1 for\(F \subseteq C\), |F| odd,C cycle ofG, and 0 ⩽x e ⩽ 1 fore ∈ E. Optimization overS (G) provides an approximation for the max-cut problem. The graphG is called 1/d-integral if all the vertices ofS(G) have their coordinates in{i/d ∣ 0 ⩽ i ⩽ d}. We prove that the class of 1/d-integral graphs is closed under minors, and we present several minimal forbidden minors for 1/3-integrality. In particular, we characterize the 1/3-integral graphs on seven nodes. We study several operations preserving 1/d-integrality, in particular, thek-sum operation for 0 ⩽k ⩽ 3. We prove that series parallel graphs are characterized by the following stronger property. All vertices of the polytopeS (G) ∩ {x ∣ ℓ ⩽ x ⩽ u} are 1/3-integral for every choice of 1/3-integral boundsℓ, u on the edges ofG.
Similar content being viewed by others
References
D. Avis, “Extremal metrics induced by graphs,” in: M. Deza and I.G. Rosenberg, eds.,Combinatorics 79, Part I, Annals of Discrete Mathematics, Vol. 8 (North-Holland, Amsterdam, 1980) pp. 217–220.
D. Avis, “On the extreme rays of the metric cone,”Canadian Journal of Mathematics 32 (1) (1980) 126–144.
F. Barahona, “On cuts and matchings in planar graphs,”Mathematical Programming 60 (1) (1993) 53–68.
F. Barahona and A.R. Mahjoub, “On the cut polytope,”Mathematical Programming 36 (2) (1986) 157–173.
M. Deza, V.P. Grishukhin and M. Laurent, “The symmetries of the cut polytope and of some relatives,” in: P. Gritzman and B. Sturmfels, eds.,Applied Geometry and Discrete Mathematics—The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 4 (American Mathematical Society, Providence, RI, 1991) pp. 205–220.
M. Deza, M. Laurent and S. Poljak, “The cut cone III: on the role of triangle facets,”Graphs and Combinatorics 8 (1992) 125–142; (updated version:Graphs and Combinatorics 9 (1993) 135–152).
A.M.H. Gerards and M. Laurent, “A characterization of box 1/d-integral binary clutters,”Journal of Combinatorial Theory B 65 (1995).
M.X. Goemans and D.P. Williamson, “0.878-approximation algorithms for MAX CUT and MAX 2SAT,” in:Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Association for Computing Machinery, New York, 1994) pp. 422–431.
V.P. Grishukhin, “Computing extreme rays of the metric cone for seven points,”European Journal of Combinatorics 13 (1992) 153–165.
M. Iri, “On an extension of the maximum-flow minimum-cut theorem to multicommodity flows,”Journal of the Operations Research Society of Japan 13 (1970–1971) 129–135.
M. Laurent, “Graphic vertices of the metric polytope,”Discrete Mathematics, to appear.
M. Laurent and S. Poljak, “The metric polytope,” in: E. Balas, G. Cornuejols and R. Kannan, eds.,Integer Programming and Combinatorial Optimization (GSIA, Carnegie-Mellon University, Pittsburgh, PA, 1992) pp. 274–286.
M. Laurent and S. Poljak, “On a positive semidefinite relaxation of the cut polytope,”Linear Algebra and its Applications 223–224 (1995) 439–461.
M.V. Lomonosov, “Combinatorial approaches to multiflow problems,”Discrete Applied Mathematics 11 (1) (1985) 1–93.
S. Poljak, “Polyhedral and eigenvalue approximations of the max-cut problem,” in:Sets, Graphs and Numbers, Budapest, 1991, Colloquia Mathematica Societatis János Bolyai, Vol. 60 (North-Holland, Amsterdam, 1992) pp. 569–581.
S. Poljak and Zs. Tuza, “The expected error of the polyhedral approximation of the max-cut problem,”Operations Research Letters 16 (1994) 191–198.
N. Robertson and P.D. Seymour, “Graph minors XX. Wagner's conjecture,” Preprint (1988).
W. Schwärzler and A. Sebő, “A generalized cut-condition for multiflows in matroids,”Discrete Mathematics 113 (1993) 207–221.
P.D. Seymour, “The matroids with the max-flow min-cut property,”Journal of Combinatorial Theory B 23 (1977) 189–222.
P.D. Seymour, “Matroids and multicommodity flows,”European Journal of Combinatorics 2 (1981) 257–290.
Author information
Authors and Affiliations
Additional information
Research by this author was partially done at CWI in Amsterdam.
Research by this author was done at the Institut für Diskrete Mathematik of Bonn, supported by the A. von Humboldt Foundation.
Deceased on April 2nd, 1995.
Rights and permissions
About this article
Cite this article
Laurent, M., Poljak, S. One-third-integrality in the max-cut problem. Mathematical Programming 71, 29–50 (1995). https://doi.org/10.1007/BF01592243
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01592243