В задаче КЛИКА дан неориентированный граф \(G\) и число \(k\). Требуется определить, содержит ли граф полный подграф на \(k\) вершинах. Задача принадлежит \(NP\), потому что заданное множество из \(k\) вершин можно проверить попарно за полиномиальное
NP-трудность в курсе доказывается сведением SAT к CLIQUE. Для каждой скобки КНФ создаются вершины, соответствующие входящим в неё литералам. Вершины из разных скобок соединяются, если соответствующие литералы не являются взаимными отрицаниями. Если в КНФ \(q\) скобок, ищется клика размера
Что важно запомнить
- Вход состоит из графа \(G\) и числа \(k\). Требуется определить, существует ли клика размера не меньше \(k\).
- Сертификат принадлежности \(NP\) — сами \(k\) вершин клики.
- В сведении SAT каждая вершина кодирует конкретное вхождение литерала в конкретную
- Рёбра соединяют только совместимые литералы из разных скобок. Пара \(x_i\), \(\neg x_i\) ребром не соединяется.
- Клика размера, равного числу скобок, выбирает по одному взаимно совместимому истинному литералу из каждой скобки.
Конструкция сведения
Пусть \(K=C_1\wedge\cdots\wedge C_q\). Для каждого вхождения литерала \(y\) в скобку \(C_i\) создают вершину \(\langle y,i\rangle\). Вершины \(\langle y,i\rangle\) и \(\langle z,j\rangle\) соединяют ребром, если \(i\ne j\) и литералы \(y,z\) не являются взаимными отрицаниями. Полагают
Если КНФ выполнима
В каждом \(C_i\) выберем один истинный литерал. Два истинных литерала не могут быть взаимными отрицаниями, поэтому соответствующие вершины попарно смежны. Получается клика из \(q\) вершин.
Если существует клика
Внутри одной скобки рёбер нет, значит клика размера \(q\) содержит ровно по одной вершине из каждой скобки. Выбранные литералы попарно непротиворечивы: среди них нет одновременно \(x_j\) и \(\neg x_j\). Им можно согласованно присвоить истинные значения, после чего каждая скобка содержит выбранный истинный литерал. Следовательно, КНФ
Граф имеет число вершин и рёбер, полиномиальное по длине формулы, и строится за полиномиальное время. Поэтому \(SAT\prec CLIQUE\). Вместе с \(CLIQUE\in NP\) это доказывает NP-полноту.
Пример простыми словами
Для КНФ \((x\vee y)\wedge(\neg x\vee z)\) строятся вершины \(\langle x,1\rangle\), \(\langle y,1\rangle\), \(\langle\neg x,2\rangle\), \(\langle z,2\rangle\). Внутри одной скобки рёбер нет, а вершины \(\langle x,1\rangle\) и \(\langle\neg x,2\rangle\) не соединяются как противоречивые. Клика размера 2, например \(\{\langle x,1\rangle,\langle z,2\rangle\}\), выбирает совместимые литералы из обеих скобок и соответствует присваиванию \(x=1,\ z=1\).
Частые ошибки
- Путать клику с независимым множеством: в клике все выбранные вершины должны быть попарно смежны.
- Соединять литералы внутри одной скобки. В конструкции сведения рёбра идут между различными скобками.
- Разрешать ребро между \(x_i\) и \(\neg x_i\). Такое ребро разрушило бы смысл совместимости выбранных литералов.
