Fast Local Search for the Maximum Independent Set Problem

Diogo V. Andrade(diogogoogle.com)
Mauricio G. C. Resende(mgcrresearch.att.com)
Renato F. Werneck(renatowmicrosoft.com)

Abstract: Given a graph G = (V,E), the independent set problem is that of finding a maximum-cardinality subset S of V such that no two vertices in S are adjacent. We present a fast local search routine for this problem. Our algorithm can determine in linear time if a maximal solution can be improved by replacing a single vertex with two others. We also show that an incremental version of this method can be useful within more elaborate heuristics. We test our algorithms on instances from the literature as well as on new ones proposed in this paper.

Keywords: Maximum independent set, local search, iterated local search, algorithm engineering.

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Global Optimization (Stochastic Approaches )

Citation: AT&T Labs Research Technical Report TD-7BBST2, AT&T Labs Research, Florham Park, NJ 07932 USA, 2008.

Download: [PDF]

Entry Submitted: 01/29/2008
Entry Accepted: 02/01/2008
Entry Last Modified: 01/29/2008

Modify/Update this entry