Finding independent sets in a graph using continuous multivariable polynomial formulations

J. Abello, S. Butenko, P.M. Pardalos, and M.G.C. Resende

J. of Global Optimization,  vol. 21, pp. 111-137,  2001


Two continuous formulations of the maximum independent set problem on a graph G = (V ,E) are considered. Both cases involve the maximization of an n-variable polynomial over the n-dimensional hypercube, where n is the number of nodes in G. Two (polynomial) objective functions F(x) and H(x) are considered. Given any solution to x0 in the hypercube, we propose two polynomial-time algorithms based on these formulations, for finding maximal independent sets with cardinality greater than or equal to F(x0) and H(x0), respectively. A relation between the two approaches is studied and a more general statement for dominating sets is proved. Results of preliminary computational experiments for some of the DIMACS clique benchmark graphs are presented.

PDF file of full paper

DjVu file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 11 March 2003

Copyright Notice