DIMACS TR: 96-09

Continuous Characterizations of the Maximum Clique Problem

Authors: Luana E. Gibbons, Donald W. Hearn, Panos M. Pardalos, Motakuri V. Ramana


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\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: 1) first order optimality 2) second order optimality 3) local optimality 4) strict local. 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 and this is used to derive a maximin characterization of perfect graphs.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-09.ps.gz
DIMACS Home Page