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 introduce two fast local search routines for this problem. The first can determine in linear time whether a maximal solution can be improved by replacing a single vertex with two others. The second routine can determine in O(mD) time (where D is the highest degree in the graph) whether there are two solution vertices than can be replaced by a set of three. We also present a more elaborate heuristic that successfully applies local search to find near-optimum solutions to a wide variety of instances. 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, AT&T Labs Research, Florham Park, NJ 07932 USA, 2010.

Download: [PDF]

Entry Submitted: 01/29/2008
Entry Accepted: 02/01/2008
Entry Last Modified: 07/15/2010

Modify/Update this entry