Continuous Characterizations of the Maximum Clique Problem

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 ∣ x^Te = 1, x ≥ 0}. It is well known that the global optimum value of this QP is (1 − 1/ω(G)), where ω(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.