Fast Local Search for the Maximum Independent Set Problem

  • Diogo V. Andrade
  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Combinatorial Optimization, Meta Heuristics, Stochastic Approaches Tags , , , Short URL: https://optimization-online.org/?p=10343

    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.

    Citation

    AT&T Labs Research Technical Report, AT&T Labs Research, Florham Park, NJ 07932 USA, 2010.

    Article

    Download

    View Fast Local Search for the Maximum Independent Set Problem