Задача о клике

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

Граф с кликой размера 3.

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

NP-полнота

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

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

Алгоритмы

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

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

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

См. также

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

Литература

• Шаблон:Cite conference Шаблон:Wayback
• Шаблон:Citation A1.2: GT19, pg.194.

Ссылки

• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring