Задача о клике относится к классу NP-полных задач в области теории графов . Впервые она была сформулирована в 1972 году Ричардом Карпом .

Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k , в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.

NP-полнота

NP-полнота задачи о клике следует из NP-полноты задачи о независимом множестве вершин. Легко показать, что необходимым и достаточным условием для существования клики размера k является наличие независимого множества размера не менее k в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.

Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».

Алгоритмы

Как и для других NP-полных задач, эффективного алгоритма для поиска клики заданного размера на данный момент не найдено. Полный перебор всех возможных подграфов размера k с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с v вершинами равно биномиальному коэффициенту ${\displaystyle {v \choose k}={\frac {v!}{k!(v-k)!}}.}$

Другой алгоритм работает так: две клики размера n и m «склеиваются» в большую клику размера n+m , причём кликой размера 1 полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим , поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.

Доказано, что, при условии неравенства классов P и NP , не существует полиномиального аппроксимационного алгоритма с абсолютной ошибкой равной произвольному ${\displaystyle k\in \mathbb {N} }$ . Рассмотрим граф ${\displaystyle G}$ и ${\displaystyle G^{k}=G\times C_{k}}$ - прямое произведение графа ${\displaystyle G}$ и клики ${\displaystyle C_{k}}$ размера ${\displaystyle k}$ . Очевидно, что кликовое число графа ${\displaystyle G^{k}}$ будет равно ${\displaystyle \omega (G^{k})=\omega (G)\cdot k}$ . Предположим, что существует аппроксимационный алгоритм ${\displaystyle A}$ с абсолютной ошибкой равной ${\displaystyle k\in \mathbb {N} }$ . Тогда подадим на вход ${\displaystyle A}$ граф ${\displaystyle G^{k+1}}$ и при условии ${\displaystyle OPT\leqslant A(I)+k}$ получим ${\displaystyle \omega (G^{k+1})-A(G^{k+1})=(k+1)\cdot \omega (G)-A(G^{k+1})\leqslant k}$ . Пусть ${\displaystyle C_{i}}$ - клики графов вида ${\displaystyle G^{i}}$ , где ${\displaystyle 1\leqslant i\leqslant k+1}$ . Заметим справедливость неравенства ${\displaystyle C_{i}\leqslant \omega (G)}$ и подставим его в вышеописанное неравенство следующим образом: ${\displaystyle (k+1)\cdot \omega (G)-\sum _{i=1}^{k+1}|C_{i}|\leqslant k}$ . После преобразования получим ${\displaystyle \sum _{i=1}^{k+1}\omega (G)-|C_{i}|\leqslant k}$ , а значит, существует ${\displaystyle i}$ такое, что ${\displaystyle C_{i}=\omega (G)}$ и, следовательно, задача о клике разрешима за полиномиальное время, что противоречит условию о неравенстве классов P и NP.

См. также

• Алгоритм Брона — Кербоша — быстрое нахождение всех клик

Примечания

Литература

• Cook, Stephen A. (1971). . Proceedings of the Third Annual ACM Symposium on Theory of Computing . Shaker Heights, Ohio. pp. 151–158. Архивировано из 3 мая 2006 . Дата обращения: 11 июня 2007 . от 3 мая 2006 на Wayback Machine
• ; (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W.H. Freeman, ISBN 0-7167-1045-5 A1.2: GT19, pg.194.

Ссылки