On Finding Critical Independent and Vertex Sets
Alexander A. Ageev · SIAM Journal on Discrete Mathematics · 1994
An independent set $I_c $ of a undirected graph G is called critical if \[|I_c | - |N( I_c )| = \max \{ |I| - |N( I )|:I\,{\text{is an independent set of }}G \},\] where $N( I )$ is the set of all vertices of G adjacent to some vertex of I. It has been proved by Cun-Quan Zhang [SIAM J. Discrete Math., 3 (1990), pp. 431–438] that the problem of finding a critical independent set is polynomially solvable. This paper shows that the problem can be solved in $O( |V ( G )|^{1/2} |E ( G )| )$ time and its weighted version in $O( |V ( G )|^2 |E ( G )|^{1/2} )$ time.