Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
Cun‐Quan Zhang · SIAM Journal on Discrete Mathematics · 1990
An independent set $J_c $ of a graph G is called critical if \[ | J_c | - | N ( J_c ) | = \max \{ | J | - | N ( J ) |:J\,\text{is an independent set of }G \}, \] and a vertex subset $U_c $ is called critical if \[ | U_c | - | N ( U_c ) | = \max \{ | U | - | N ( U ) |:U\,\text{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.