Combinatorial properties and the complexity of a max-cut approximation (Q685307)

In several combinatorial optimization problems one can effectively use eigenvalues and eigenvectors as a kind of easy solvable quadratic relaxations. This approach proved to be useful in many instances (see a recent survey by the second author and the reviewer [Eigenvalues in combinatorial optimization, in ``Combinatorial and graph-theoretic problems in linear algebra'' (1993)]). Max-cut is one of such problems. The authors investigate combinatorial properties of an eigenvalue upper bound \(\varphi(G)\) on the max-cut of graphs. It is shown that this bound behaves in a manner similar to the max-cut for several operations (switching, contraction, vertex splitting, decomposition). It is conjectured that \(\varphi(G)\) approximates the max-cut of \(G\) within the factor 1.131. This conjecture is supported by some results showing that the eigenvalue bound provides conjectured approximation for the max-cut in many interesting classes of graphs. The importance of these results lies in the fact that no efficient approximation algorithm for the max-cut problem has been found so far.