Комбинаторная оптимизация на графах: максимальные клики и независимые множества

Математически задачи поиска максимальной клики и максимального независимого множества являются абсолютно эквивалентными (сводятся друг к другу за полиномиальное время). Ключом к этому является операция дополнения графа. Дополнение графа G — это новый граф, в котором ребра существуют только там, где их не было в исходном графе, и отсутствуют там, где они были. Алгебраическая теорема строго доказывает: любое независимое множество в исходном графе гарантированно является кликой в его дополнении (и наоборот). Третьей задачей-близнецом является задача о минимальном вершинном покрытии (Vertex Cover) — поиске минимального набора узлов, касающихся абсолютно всех ребер графа. Теорема Галлаи связывает их математическим тождеством: число независимости графа плюс число вершинного покрытия всегда в точности равно общему количеству вершин графа.

Практическое применение этих абстрактных концепций имеет колоссальное значение в радиотехнике и телекоммуникациях (задача раскраски графа и частотного планирования). Если две вышки сотовой связи находятся слишком близко друг к другу, они создают интерференцию (помехи) и не могут вещать на одной и той же частоте. В графе конфликтов вышки представляются вершинами, а конфликт — ребром. Задача мобильного оператора: найти максимальное независимое множество — наибольшую группу вышек, которым можно абсолютно безопасно выделить одну общую радиочастоту. Последовательно удаляя такие независимые множества из графа, алгоритм минимизирует общее количество закупленных у государства дорогостоящих радиочастот.

Для поиска абсолютно точного решения задачи о максимальной клике (Maximum Clique Problem) в дискретной математике используется алгоритм Брона-Кербоша (Bron-Kerbosch algorithm), разработанный в 1973 году. Это рекурсивный алгоритм ветвей и границ, работающий по принципу поиска с возвратом (Backtracking). Алгоритм поддерживает три множества вершин: R (текущая растущая клика), P (кандидаты на добавление) и X (исключенные узлы, которые уже были исследованы). Алгоритм систематически переносит вершины из P в R, углубляясь в рекурсию, и отсекает мертвые ветви, когда P и X становятся пустыми. Модификация алгоритма Брона-Кербоша с выбором опорной вершины (Pivot) радикально сокращает дерево поиска, исключая повторную генерацию изоморфных (симметричных) подграфов.

Однако для графов социальных сетей с миллионами вершин точный перебор Брона-Кербоша физически невозможен. Более того, знаменитая PCP-теорема доказала, что задачу о максимальной клике невозможно даже эффективно аппроксимировать с заданной точностью, если только P не равно NP. Поэтому на практике исследователи операций применяют стохастический локальный поиск, алгоритмы имитации отжига и Tabu Search. Эти метаэвристики быстро находят гигантские клики-кандидаты, итеративно добавляя и удаляя вершины из множества, пытаясь максимизировать плотность связей. Интеграция этих алгоритмов с методами машинного обучения позволяет выявлять скрытые террористические ячейки в сетях телекоммуникаций и находить плотно связанные функциональные модули в гигантских графах белковых взаимодействий в молекулярной биологии.