Augmenting graphs for independent sets Original Research Article

We consider a general approach to solve the maximum independent set problem based on finding augmenting graphs. For some special classes of graphs, the approach provides polynomial solutions. In this paper we survey classical and recent results on the topic, and describe a new one that generalizes two previously known algorithms. We also discuss some open questions related to the notion of augmenting graphs.