Polynomially solvable cases for the maximum stable set problem (Q1894362): Difference between revisions

A set \(S\) of vertices in a graph \(G= (V, E)\) is stable if no two vertices in \(S\) are linked by an edge. The size of a maximum stable set in \(G\) is denoted \(\alpha(G)\) and is called the stability number of \(G\). The author describes two classes of graphs for which the stability number can be computed in polynomial time. For one class, an iterative procedure can be used. At each step, the iteration builds from a graph \(G\) a new graph \(G'\) which has fewer vertices and has the property that \(\alpha(G')= \alpha(G)- 1\). For the other class, the existence of a stable set of given size \(k\) can be determined in polynomial time.