Русская Википедия:Задача о клике
Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.[1]
Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.
NP-полнота
NP-полнота задачи о клике следует из NP-полноты задачи о независимом множестве вершин. Легко показать, что необходимым и достаточным условием для существования клики размера k является наличие независимого множества размера не менее k в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».[2]
Алгоритмы
Как и для других NP-полных задач, эффективного алгоритма для поиска клики заданного размера на данный момент не найдено. Полный перебор всех возможных подграфов размера k с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с v вершинами равно биномиальному коэффициенту <math>{v \choose k} = \frac{v!}{k!(v-k)!}.</math>
Другой алгоритм работает так: две клики размера n и m «склеиваются» в большую клику размера n+m, причём кликой размера 1 полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.
Доказано, что, при условии неравенства классов P и NP, не существует полиномиального аппроксимационного алгоритма с абсолютной ошибкой равной произвольному <math>k \in \mathbb{N}</math>. Рассмотрим граф <math>G</math> и <math>G^k = G \times C_k</math> - прямое произведение графа <math>G</math> и клики <math>C_k</math> размера <math>k</math>. Очевидно, что кликовое число графа <math>G^k</math> будет равно <math>\omega(G^k) = \omega(G) \cdot k</math>. Предположим, что существует аппроксимационный алгоритм <math>A</math> с абсолютной ошибкой равной <math>k \in \mathbb{N}</math>. Тогда подадим на вход <math>A</math> граф <math>G^{k+1}</math> и при условии <math>OPT \leqslant A(I) + k</math> получим <math>\omega(G^{k+1}) - A(G^{k+1}) = (k+1) \cdot \omega(G) - A(G^{k+1}) \leqslant k</math>. Пусть <math>C_i</math> - клики графов вида <math>G^i</math>, где <math>1 \leqslant i \leqslant k + 1</math>. Заметим справедливость неравенства <math>C_i \leqslant \omega(G)</math> и подставим его в вышеописанное неравенство следующим образом: <math>(k + 1) \cdot \omega(G) - \sum_{i=1}^{k+1} |C_i| \leqslant k</math>. После преобразования получим <math>\sum_{i=1}^{k+1} \omega(G) - |C_i| \leqslant k</math>, а значит, существует <math>i</math> такое, что <math>C_i = \omega(G)</math> и, следовательно, задача о клике разрешима за полиномиальное время, что противоречит условию о неравенстве классов P и NP.
См. также
- Алгоритм Брона — Кербоша — быстрое нахождение всех клик
Примечания
Литература
- Шаблон:Cite conference Шаблон:Wayback
- Шаблон:Citation A1.2: GT19, pg.194.
Ссылки
