А если так?
Взяли граф, хотим найти независимое множество из

вершин. Взяли по переменной

для каждой вершины (будет

, если вершина не входит в множество, и

, если входит),

для каждого ребра (будет

, если одна из инцидентных ребру вершин входи в множество,

, если не входит).
Для каждого ребра

, соединяющего вершины

и

пишем

. Пишем уравнение

. Далее перебираем все варианты, сколько нулей среди значений переменных (число вариантов линейно по размеру графа).
Делаем независимое множество из решения: берем все вершины, соответствующие равным единице

. Оно независимо, т.к. если бы вершины

и

из него соединялись ребром

, то было бы

.
Делаем решение из независимого множества: говорим, что у нас число единиц равно

плюс число ребер, не соединенных ни с одной вершиной из независимого множества. Если

-я вершина принадлежит множеству, берем

, иначе

. Для ребер, не соединенных ни с одной вершиной множества, берем

, для остальных

. Все уравнения выполняются, ограничение на количество тоже.