zbMATH — the first resource for mathematics

Continuous characterizations of the maximum clique problem. (English) Zbl 0883.90098
Summary: Given a graph \(G\) whose adjacency matrix is \(A\), the Motzkin-Strauss formulation of the maximum-clique problem is the quadratic program \(\max\{x^TAx\mid x^Te=1,\;x\geq 0\}\). It is well-known that the global optimum value of this QP is \((1-1/\omega(G))\), where \(\omega(G)\) is the clique number of \(G\). Here, we characterize the following properties pertaining to the above QP: (1) first-order optimality, (2) second-order optimality, (3) local optimality, (4) strict local optimality. These characterizations reveal interesting underlying discrete structures, and are polynomial time verifiable. A parametrization of the Motzkin-Strauss QP is then introduced and its properties are investigated. Finally, an extension of the Motzkin-Strauss formulation is provided for the weighted clique number of a graph.

90C20 Quadratic programming
90C35 Programming involving graphs or networks
PDF BibTeX Cite
Full Text: DOI