Дополнением наименьшего вершинного покрытия в графе является наибольшее независимое множество. Если речь о точном решении, то это эквивалентные задачи(в общем короткий и наивный ответ да.), если о приближенном то нет. Также вопросы есть ли вершинное покрытие размера k и есть ли независимое множество размера k скорее всего вопросы различной сложности. Так первое решается за 2^k poly(n), а про второе считается что скорее всего нет.
Для тех кому интересны видео Computer Science клуба, напоминаю, что открытие нового семестра в клубе произойдет 14 февраля. Информация об открытии тут.
К примеру:
слайды по «Анализу данных» compscicenter.ru/program/course/introdatamining2011
слайды по «Компьютерной графике» compsciclub.ru/courses/computergraphics