Optimization Online


An (n-2)-dimensional Quadratic Surface Determining All Cliques and a Least Square Formulation for the Maximum Clique Problem

Stanislav Busygin (busygin***at***a-teleport.com)

Abstract: Arranging an n-vertex graph as the standard simplex in R^n, we identify graph cliques with simplex faces formed by clique vertices. An unstrict quadratic inequality holds for all points of the simplex; it turns to equality if and only if the point is on a face corresponding to a clique. This way this equality determines a quadratic surface in R^n characterizing all graph cliques. Since the standard simplex is a polyhedron located within the hyperplane e'x=1, we may decrease the dimensionality by 1 considering the intersection of this surface with the hyperplane. Therefore, we obtain a quadratic surface of dimensionality n-2 determining all graph cliques. We call it the clique wrapper. The higher the dimensionality of a standard simplex face, the less the distance from it to the geometric center of the simplex. Therefore, the maximum clique problem is equivalent to finding a point of the clique wrapper closest to the geometric center of the simplex and lying not outside the simplex. When the latter is relaxed, all stationary points of such a least square program can be found via roots of one univariate rational equation. If the adjacency matrix of the graph does not have multiple eigenvalues, the number of the stationary points is not above 2(n-1). If a clique is such that any vertex outside it has the same number of adjacent vertices in the clique, the geometric center of the clique face is such a stationary point.

Keywords: maximum clique problem, NP-hard, continuous approach, least squares problem

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation: Stas Busygin's NP-Completeness Page (http://www.busygin.dp.ua/npc.html), 2002.

Download: [Postscript][Compressed Postscript]

Entry Submitted: 08/30/2002
Entry Accepted: 08/30/2002
Entry Last Modified: 09/10/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society