Изменения

В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> реберрёбер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.