# 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.

##### MSC:
 90C20 Quadratic programming 90C35 Programming involving graphs or networks
##### Keywords:
maxmium-clique problem
Full Text: