zbMATH — the first resource for mathematics

Laplacian eigenvalues and the maximum cut problem. (English) Zbl 0797.90107
Summary: We introduce and study an eigenvalue upper bound \(\varphi(G)\) on the maximum cut \(\text{mc}(G)\) of a weighted graph. The function \(\varphi(G)\) has several interesting properties that resemble the behaviour of \(\text{mc}(G)\). The following results are presented: We show that \(\varphi\) is subadditive with respect to amalgam, and additive with respect to disjoint sum and 1-sum. We prove that \(\varphi(G)\) is never worse that 1.131 \(\text{mc}(G)\) for a planar, or more generally, a weakly bipartite graph with nonnegative edge weights. We give a dual characterization of \(\varphi(G)\), and show that \(\varphi(G)\) is computable in polynomial time with an arbitrary precision.

90C35 Programming involving graphs or networks
Full Text: DOI
[1] F. Barahona, ”On the complexity of max-cut,” Rapport de Recherche 186, Mathématiques appliquées et Informatique, Université Scientifique et médicale de Grenoble (Grenoble, France, 1980).
[2] F. Barahona, ”On some weakly bipartite graphs,”Operations Research Letters 2 (1983) 239–242. · Zbl 0549.90087
[3] F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, ”An application of combinatorial optimization to statistical physics and circuit layout design,”Operations Research 36 (1988) 493–513. · Zbl 0646.90084
[4] F. Barahona, M. Jünger and G. Reinelt, ”Experiments in quadratic 0–1 programming,”Mathematical Programming 44 (1989) 127–137. · Zbl 0677.90046
[5] E.R. Barnes and A.J. Hoffman, ”On transportation problems with upper bounds on leading rectangles,”SIAM Journal on Algebraic Discrete Methods 6 (1985) 487–496. · Zbl 0589.90056
[6] R. Boppana, ”Eigenvalues and graph bisection: an average case analysis,” in:FOCS (1987) pp. 280–285.
[7] C. Delorme and S. Poljak, ”The performance of an eigenvalue bound on the max-cut problem in some classes of graphs,”Discrete Mathematics 111 (1993) 145–156. · Zbl 0786.05057
[8] C. Delorme and S. Poljak, ”Combinatorial properties and the complexity of a max-cut approximation,”European Journal of Combinatorics 14 (1993) 313–333. · Zbl 0780.05040
[9] V.F. Dem’ianov and V.N. Malozev,Introduction to Minimax (Wiley, New York, 1974).
[10] W.E. Donath and A.J. Hofmann, ”Lower bounds for the partitioning of graphs,”IBM Journal on Research and Development 17 (1973) 420–425. · Zbl 0259.05112
[11] M. Fiedler, ”Algebraic connectivity of graphs,”Czechoslovak Mathematical Journal 23 (1973) 298–305. · Zbl 0265.05119
[12] J. Fonlupt, A.R. Mahjoub and J.P. Uhry, ”Compositions in the bipartite subgraph polytope,”Discrete Mathematics 105 (1992) 73–91. · Zbl 0771.05092
[13] M.R. Garey and D.S. Johnson,Computers and Intractability: A guide to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979). · Zbl 0411.68039
[14] M. Grötschel, L. Lovász and A. Schrijver,Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics No. 2 (Springer, Berlin, 1988). · Zbl 0634.05001
[15] M. Grötschel and W.R. Pulleyblank, ”Weakly bipartite graphs and the max-cut problem,”Operations Research Letters 1 (1981) 23–27. · Zbl 0494.90078
[16] F. Juhász, ”On the spectrum of a random graph,” in: L. Lovász and V.T. Sós, eds.,Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis János Bolyai No. 25 (North-Holland, Amsterdam, 1982) pp. 313–316.
[17] P. Lancaster,Theory of Matrices (Academic Press, New York, 1969). · Zbl 0186.05301
[18] B. Mohar and S. Poljak, ”Eigenvalues and the max-cut problem,”Czechoslovak Mathematical Journal 40(115) (1990) 343–352. · Zbl 0724.05046
[19] M.L. Overton, ”On minimizing the maximum eigenvalue of a symmetric matrix,”SIAM Journal on Matrix Analysis and Applications 9 (1988) 256–268. · Zbl 0647.65044
[20] S. Poljak, ”Polyhedral and eigenvalue approximations of the max-cut problem,” to appear in:Sets, Graphs and Numbers, Colloquia Mathematica Societatis János Bolyai No. 59 (North-Holland, Amsterdam, 1991).
[21] S. Poljak and F. Rendl, ”Solving the max-cut problem using eigenvalues,” Technical Report 91735-OR, Institut für Diskrete Mathematik, Universität Bonn (Bonn, 1991). · Zbl 0838.90131
[22] S. Poljak and Zs. Tuza, ”The expected relative error of the polyhedral approximation of the max-cut problem,” Technical Report 92757, Institut für Diskrete Mathematik, Universität Bonn (Bonn, 1992).
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.