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

Задача о клике — это классическая NP-полная задача комбинаторной оптимизации и теории графов, заключающаяся в поиске в заданном неориентированном графе клики (полного подграфа) максимального размера. Задача также известна как задача поиска максимальной клики. Она является одной из 21 NP-полных задач, перечисленных Ричардом Карпом в его знаменитой работе 1972 года, и имеет фундаментальное значение для теории сложности вычислений.

Формальная постановка

Пусть дан неориентированный граф \( G = (V, E) \), где \( V \) — множество вершин, а \( E \) — множество рёбер. Кликой называется подмножество вершин \( C \subseteq V \), такое, что для любых двух различных вершин \( u, v \in C \) существует ребро \( (u, v) \in E \). Иными словами, клика — это полный подграф. Размер клики определяется числом вершин в ней.

Задача о клике (в варианте разрешимости) формулируется так: существует ли в графе \( G \) клика размера не менее заданного числа \( k \)? В варианте оптимизации требуется найти клику максимального размера, который называется кликовым числом графа (обозначается \( \omega(G) \)).

История и происхождение

Задача о клике имеет глубокие корни в комбинаторике и теории графов. В 1965 году Джон Муни (John Moon) и Лео Мозер (Leo Moser) опубликовали работу, в которой определили максимальное количество клик, которое может содержать граф с заданным числом вершин (теорема Муна — Мозера). Однако решающий вклад в изучение сложности задачи внёс Ричард Карп. В 1972 году он опубликовал статью «Reducibility Among Combinatorial Problems», где доказал NP-полноту задачи о клике, сведя к ней задачу о выполнимости булевых формул (SAT). Это доказательство стало одним из краеугольных камней теории NP-полноты.

NP-полнота и сложность

Задача о клике является NP-полной, что означает, что:

1. Она принадлежит классу NP: для данного решения (подмножества вершин) можно за полиномиальное время проверить, является ли оно кликой заданного размера.
2. Любая задача из класса NP может быть сведена к ней за полиномиальное время.

Известно, что задача о клике является NP-трудной и в варианте оптимизации. Это означает, что не существует алгоритма, который решал бы её за полиномиальное время (если только \( P \neq NP \)). Более того, для задачи о клике существуют сильные результаты о неаппроксимируемости. В 1999 году Йохан Хастад (Johan Håstad) доказал, что для любого \( \epsilon > 0 \) невозможно аппроксимировать размер максимальной клики с точностью до множителя \( n^{1-\epsilon} \) за полиномиальное время, если \( P \neq NP \). Это означает, что даже приблизительное решение задачи является крайне сложным.

Связь с другими задачами

Задача о клике тесно связана с несколькими другими фундаментальными задачами:

• Задача о независимом множестве: Независимое множество в графе \( G \) — это подмножество вершин, никакие две из которых не соединены ребром. Если построить дополнение графа \( \overline{G} \) (в котором ребро есть там, где его нет в \( G \), и наоборот), то клика в \( G \) соответствует независимому множеству в \( \overline{G} \), и наоборот. Таким образом, задачи о клике и о независимом множестве полиномиально эквивалентны.
• Задача о вершинном покрытии: Вершинное покрытие — это множество вершин, которое содержит хотя бы один конец каждого ребра графа. Для любого графа \( G \) верно, что \( V \setminus C \) является вершинным покрытием тогда и только тогда, когда \( C \) является независимым множеством. Следовательно, задача о клике также тесно связана с задачей о вершинном покрытии.

Алгоритмы решения

Несмотря на NP-полноту, существуют алгоритмы, которые могут решать задачу о клике для графов умеренного размера (до нескольких сотен вершин) за приемлемое время. Эти алгоритмы обычно основаны на методах перебора с отсечениями (branch and bound).

Алгоритм Брона — Кербоша

Одним из наиболее известных и эффективных алгоритмов для перечисления всех максимальных (по включению) клик является алгоритм Брона — Кербоша, опубликованный в 1973 году. Он работает рекурсивно, поддерживая три множества вершин:

• \( R \) — множество вершин, образующих текущую (строящуюся) клику.
• \( P \) — множество вершин-кандидатов, которые могут быть добавлены к \( R \) (все они соединены со всеми вершинами из \( R \)).
• \( X \) — множество вершин, которые уже были обработаны и не должны добавляться к \( R \) (чтобы избежать повторного перечисления одной и той же клики).

Алгоритм выбирает вершину из \( P \), добавляет её в \( R \), обновляет \( P \) и \( X \) пересечением с множеством соседей этой вершины, и рекурсивно продолжает. Когда \( P \) и \( X \) пусты, текущее множество \( R \) является максимальной кликой. Существует оптимизированная версия алгоритма с pivot-вершиной, которая значительно ускоряет работу на разреженных графах.

Другие подходы

• Точные алгоритмы: Основаны на методах целочисленного линейного программирования, динамического программирования (для графов специального вида, например, хордальных) и алгоритмах с использованием ветвей и границ.
• Эвристические алгоритмы: Для очень больших графов (например, в социальных сетях) используются эвристики, такие как жадные алгоритмы, алгоритмы на основе поиска с запретами (tabu search) или генетические алгоритмы. Они не гарантируют нахождения точного решения, но часто находят клики большого размера.
• Квантовые алгоритмы: В 2023 году была опубликована работа, демонстрирующая квантовое ускорение для задачи о клике с использованием алгоритма Гровера, но практическое применение таких алгоритмов пока ограничено из-за несовершенства существующих квантовых компьютеров.

Применение

Задача о клике находит применение в различных областях, где требуется выявление плотных, сильно связанных подгрупп в данных.

• Анализ социальных сетей: Поиск сообществ (cliques) — групп людей, которые все знают друг друга. Это используется для выявления тесных кругов общения, групп по интересам или потенциальных групп влияния.
• Биоинформатика: В анализе экспрессии генов, где вершины представляют гены, а рёбра — корреляцию их активности. Поиск клик позволяет выявить группы генов, которые работают согласованно. В протеомике — для поиска групп взаимодействующих белков.
• Химия и фармакология: В задаче поиска общих подструктур в наборе химических соединений. Молекулы представляются в виде графов, а клики в графе совпадений (product graph) соответствуют общим подграфам. Это используется для поиска новых лекарственных препаратов.
• Теория кодирования: В задачах декодирования и поиска кодов с минимальным расстоянием.
• Компьютерное зрение: В задаче распознавания объектов на изображении, где клики могут соответствовать группам точек, образующих жёсткую геометрическую конфигурацию.

Интересные факты

• Теорема Турана: Даёт верхнюю оценку на количество рёбер в графе, не содержащем клику заданного размера \( k+1 \). А именно, граф с \( n \) вершинами, не содержащий \( K_{k+1} \), имеет не более \( \left(1 - \frac{1}{k}\right) \frac{n^2}{2} \) рёбер.
• Графы без треугольников: Задача о поиске клики размера 3 (треугольника) решается за полиномиальное время (например, с помощью умножения матриц). Однако задача о поиске клики размера 4 уже является NP-полной.
• Рекорды: Для некоторых специальных классов графов, таких как графы Пэли или графы Кнезера, кликовое число известно точно. Например, кликовое число графа Кнезера \( KG_{n,k} \) равно \( \lfloor n/k \rfloor \).

Критика и ограничения

Основным ограничением задачи о клике является её вычислительная сложность. Даже для графов с несколькими сотнями вершин точное решение может потребовать экспоненциального времени. Это делает её малопригодной для анализа огромных графов (например, всей сети Интернет или социальной сети с миллиардами пользователей) без использования эвристик. Кроме того, в реальных данных часто встречаются «почти клики» — подграфы, в которых отсутствует лишь несколько рёбер. Задача о поиске таких плотных подграфов (dense subgraphs) является отдельной, часто более практичной, но также сложной задачей.

Источники

1. Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85-103). Springer, Boston, MA.
2. Bron, C., & Kerbosch, J. (1973). Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16(9), 575-577.
3. Håstad, J. (1999). Clique is hard to approximate within \( n^{1-\epsilon} \). Acta Mathematica, 182(1), 105-142.
4. Moon, J. W., & Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1), 23-28.
5. Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.