DIMACS TR: 96-09
Continuous Characterizations of the Maximum Clique Problem
Authors: Luana E. Gibbons, Donald W. Hearn, Panos M. Pardalos, Motakuri V. Ramana
ABSTRACT
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