Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Fast Local Search for the Maximum Independent Set Problem

Diogo V. Andrade, Mauricio G. C. Resende, and Renato F. Werneck

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(m Delta) time (where Delta 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.

Details

Publication typeArticle
Published inJournal of Heuristics
URLhttp://rd.springer.com/article/10.1007/s10732-012-9196-4
Pages525-547
Volume18
Number4
PublisherSpringer
> Publications > Fast Local Search for the Maximum Independent Set Problem