Проблема клики
-
Определение и свойства клик
- Клика — это подмножество вершин графа, в котором любые две вершины соединены ребром.
- Число клик в графе равно числу его совершенных паросочетаний.
- Задача о клике — это задача нахождения максимальной клики в заданном графе.
-
История и сложность задачи
- Задача о клике была сформулирована в 1930 году и является одной из 21 NP-полных задач, определенных Карпом в 1972 году.
- Сложность задачи о клике связана с NP-полнотой и не имеет полиномиального алгоритма для решения за полиномиальное время.
-
Алгоритмы перечисления клик
- Алгоритм Брона-Кербоша находит все максимальные клики за полиномиальное время.
- Алгоритм Джонсона и Яннакакиса перечисляет все максимальные клики в лексикографическом порядке.
- Существуют специальные алгоритмы для семейств графов с ограниченным числом клик.
-
Алгоритмы нахождения максимальной клики
- Алгоритм Тарьяна и Трояновского находит максимальную клику за время O(2n/3).
- Алгоритм Робсона улучшает время выполнения до O(20,249n).
- Существуют эвристические алгоритмы для решения задачи без гарантии наихудшего времени выполнения.
-
Специальные классы графов и аппроксимация
- Плоские графы и другие разреженные графы имеют ограниченное число клик, которые можно перечислить за линейное время.
- В совершенных графах можно найти максимальную клику за полиномиальное время с помощью специализированных алгоритмов.
- Алгоритмы аппроксимации пытаются найти клику, близкую к максимальной, за полиномиальное время.
-
Нижние границы и NP-полнота
- Задача о клике является NP-полной, что означает невозможность полиномиального алгоритма для ее решения.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.
Полный текст статьи: