В задаче ВЕРШИННОЕ ПОКРЫТИЕ дан граф \(G=(V,E)\) и число \(l\). Требуется определить, существует ли множество \(R\subseteq V\), \(|R|\le l\), содержащее хотя бы один конец каждого ребра. Это decision problem, отличная от оптимизационной задачи поиска минимального покрытия из следующего
Задача NP-полна. В курсе NP-трудность доказывается сведением CLIQUE к VERTEX COVER через дополнение графа: \(G\) содержит клику размера \(k\) тогда и только тогда, когда \(\overline G\) имеет вершинное покрытие размера не более \(|V|-k\)
Что важно запомнить
- Вершинное покрытие должно касаться каждого ребра хотя бы одной выбранной вершиной.
- Заданное покрытие легко проверить, поэтому задача принадлежит \(NP\).
- Сведение использует дополнительный граф \(\overline G\), а параметр меняется на
- Клика в \(G\) превращается в дополнение вершинного покрытия в \(\overline G\).
Связь клики и вершинного покрытия
Пусть дан экземпляр CLIQUE: граф \(G=(V,E)\) и число \(k\). Строят дополнение \(\overline G\): две разные вершины смежны в \(\overline G\) тогда и только тогда, когда они не смежны в \(G\). Новому экземпляру VERTEX COVER задают параметр \(l=|V|-k\)
Если \(A\subseteq V\) — клика размера \(k\) в \(G\), то между вершинами \(A\) нет рёбер в \(\overline G\). Поэтому каждое ребро \(\overline G\) имеет хотя бы один конец в \(V\setminus A\). Значит \(V\setminus A\) — вершинное покрытие размера \(|V|-k\).
Обратно, пусть \(R\) — вершинное покрытие \(\overline G\) и \(|R|\le|V|-k\). Тогда множество \(A=V\setminus R\) содержит не менее \(k\) вершин. Между двумя вершинами из \(A\) не может быть ребра в \(\overline G\), иначе оно не было бы покрыто. Следовательно, любые две вершины \(A\) смежны в \(G\), то есть \(A\) содержит клику размера
Дополнение графа строится за полиномиальное время, поэтому \(CLIQUE\prec VERTEX\ COVER\). Так как VERTEX COVER принадлежит \(NP\), задача NP-полна.
Пример простыми словами
Для \(K_3\) существует клика размера \(k=3\). Дополнительный граф \(\overline{K_3}\) не имеет рёбер, поэтому ему достаточно вершинного покрытия размера \(0=3-3\). Если \(G\) — путь из трёх вершин, то в \(G\) есть клика размера \(2\); в \(\overline G\) остаётся одно ребро между концами пути, и его минимальное вершинное покрытие имеет размер \(1=3-2\).
Частые ошибки
- Доказывать NP-полноту оптимизационной задачи «найти минимальное покрытие». NP-полнота формулируется для decision problem с параметром \(l\).
- Забывать перейти к дополнительному графу. В исходном \(G\) дополнение клики не обязано покрывать все рёбра.
- Использовать параметр \(l=k\). В этом сведении требуется \(l=|V|-k\).
