Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

An independent set Jc of a graph G is called critical if \[ | J_c | - | N ( J_c ) | = max \{ | J | - | N ( J ) |:J\,is an independent set of G \}, \] and a vertex subset Uc is called critical if \[ | U_c | - | N ( U_c ) | = max \{ | U | - | N ( U ) |:U\,is a vertex subset of G \} . \] In this paper, it will be shown that finding a critical independent set and a critical vertex subset of a graph are solvable in polynomial time.