Задача о вершинном покрытии: различия между версиями

Поскольку задача о вершинном покрытии является [[NP-полная задача|NP-полной]], то, к сожалению, неизвестны алгоритмы для её решения за полиномиальное время. Однако, существуют алгоритмы, дающие «приближённое» решение этой задачи за полиномиальное время — можно найти вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.