The performance of an eigenvalue bound on the max-cut problem in some classes of graphs (Q686456)

Maximum cut of a graph \(G\) is the size of a maximum bipartite subgraph of \(G\). An upper bound, \(\varphi(G)\), that is defined in terms of eigenvalues of a family of matrices associted with the graph has been introduced in other works by the same authors. \(\varphi(G)\) can be expressed as a minimum of a convex function. Consequently, it is effectively computable [\textit{M. Grötschel}, \textit{L. Lovász} and \textit{A. Schrijver}, Geometric algorithms and combinatorial optimization (1988; Zbl 0634.05001)]. It is conjectured that \(\varphi(G)\) approximates the maximum cut of \(G\) within the factor 1.131. If true, this would yield the first known efficient approximation algorithm for the maximum cut problem. In this paper some additional properties of \(\varphi(G)\) are established and some computational experiments on randomly generated graphs are reported. The results speak in favor of the above conjecture.