  


An (n2)dimensional Quadratic Surface Determining All Cliques and a Least Square Formulation for the Maximum Clique Problem
Stanislav Busygin (busyginateleport.com) Abstract: Arranging an nvertex 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 n2 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(n1). 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, NPhard, continuous approach, least squares problem Category 1: Combinatorial Optimization (Graphs and Matroids ) Category 2: Combinatorial Optimization (Polyhedra ) Category 3: Nonlinear Optimization (Nonlinear Systems and LeastSquares ) Citation: Stas Busygin's NPCompleteness Page (http://www.busygin.dp.ua/npc.html), 2002. Download: [Postscript][Compressed Postscript] Entry Submitted: 08/30/2002 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  