Удалите вершины, пока не останется ребер

Question

Для неориентированного графа G (V, E) найдите минимальное количество вершин, которые нужно удалить, чтобы набор ребер графа стал пустым.

Другими словами: если мы удаляем одну вершину, мы удаляем эту вершину вместе со всеми ребрами, соединенными с этой вершиной. Найдите минимальное количество вершин, которые нужно удалить, чтобы в G не осталось ребер после их удаления.

Answer 1

Похоже, вы сами нашли ответ, вы описываете Vertex Cover , который во многом очень похож на Independent Set, обе задачи NP-полны .

Отношение к независимому множеству таково, что в графе $G = (V,E)$, множество $S$ является минимальным вершинным покрытием тогда и только тогда, когда $V \setminus S$ - максимальное независимое множество.

Если вы знаете, что независимое множество является NP-полным, то отсюда следует, что вершинное покрытие также является NP-полным.

Другими словами, вы также ищете максимально независимый набор.

Крышка вершины . Учитывая график$G = (V,E)$ и целое число $k$, существует ли набор $S \subseteq V$ по размеру не более $k$ так что все ребра в $G$ инцидентны вершине в $S$?

Независимый набор . Учитывая график$G = (V,E)$ и целое число $k$, существует ли набор $S \subseteq V$ размером не менее $k$такой, что индуцированный граф $G[S]$ не имеет краев?