Extending the MAX Algorithm for Maximum Independent Set

Abstract

The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.

Keywords

• maximum independent set
• stable set
• stability number
• independence number
• reduction
• graph transformation
• max algorithm
• min algorithm
• vertex order algorithm