New Lower Bounds on the Stability Number of a Graph

E. Alper YILDIRIM(yildirimbilkent.edu.tr)

Abstract: Given a simple, undirected graph $G$, Motzkin and Straus [Canadian Journal of Mathematics, 17 (1965), 533--540] established that the reciprocal of the stability number of $G$ (the size of the maximum stable set of $G$) is given by the minimum value of a certain quadratic function over the unit simplex. We propose two new lower bounds on the stability number of $G$ based on this formulation. The first lower bound is obtained by minimizing the same objective function over the largest inscribed ball in the unit simplex. Using the fact that quadratic optimization over a full-dimensional ball admits a tight semidefinite programming relaxation, our lower bound can be computed to within any arbitrary precision in polynomial time. For regular graphs, we establish that this lower bound has a closed form solution and that it is tighter than some other existing lower bounds. The second lower bound improves upon the first lower bound and is obtained by a further refinement of the optimal solution that yields the first bound. We evaluate the new bounds and compare them with several other known lower bounds on the DIMACS collection of clique problems. Our computational results reveal that especially the improved lower bound is tighter than all other lower bounds on the majority of the instances.

Keywords: Maximum stable set, maximum clique, stability number, clique number, semidefinite programming

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical Report, Department of Industrial Engineering, Bilkent University, 06800 Bilkent, Ankara, Turkey. June 2007.

Download: [PDF]

Entry Submitted: 06/27/2007
Entry Accepted: 06/27/2007
Entry Last Modified: 06/27/2007

Modify/Update this entry