Craig Larson
Maximum Critical Independent Sets and Applications

Abstract

A critical independence set of a graph is an independent set I , where |I|-|N(I)| ≥ |J|-|N(J)|, for any independent set J. Maximum critical independent sets can be found in polynomial-time. Examples, algorithms, and at least three applications will be discussed.

1) Critical independent sets can be used to reduce the problem of finding a maximum independent set in a graph.
2) If a maximum critical independent set is a maximum independent set then the graph is a König-Egervary graph.
3) The neighbors of a maximum critical independent set are saturated by every maximum matching - that is, these sets are related to the matching structure of the graph.