Проблема клики

• Определение и свойства клик

  • Клика — это подмножество вершин графа, в котором любые две вершины соединены ребром. 
  • Число клик в графе равно числу его совершенных паросочетаний. 
  • Задача о клике — это задача нахождения максимальной клики в заданном графе. 

• История и сложность задачи

  • Задача о клике была сформулирована в 1930 году и является одной из 21 NP-полных задач, определенных Карпом в 1972 году. 
  • Сложность задачи о клике связана с NP-полнотой и не имеет полиномиального алгоритма для решения за полиномиальное время. 

• Алгоритмы перечисления клик

  • Алгоритм Брона-Кербоша находит все максимальные клики за полиномиальное время. 
  • Алгоритм Джонсона и Яннакакиса перечисляет все максимальные клики в лексикографическом порядке. 
  • Существуют специальные алгоритмы для семейств графов с ограниченным числом клик. 

• Алгоритмы нахождения максимальной клики

  • Алгоритм Тарьяна и Трояновского находит максимальную клику за время O(2n/3). 
  • Алгоритм Робсона улучшает время выполнения до O(20,249n). 
  • Существуют эвристические алгоритмы для решения задачи без гарантии наихудшего времени выполнения. 

• Специальные классы графов и аппроксимация

  • Плоские графы и другие разреженные графы имеют ограниченное число клик, которые можно перечислить за линейное время. 
  • В совершенных графах можно найти максимальную клику за полиномиальное время с помощью специализированных алгоритмов. 
  • Алгоритмы аппроксимации пытаются найти клику, близкую к максимальной, за полиномиальное время. 

• Нижние границы и NP-полнота

  • Задача о клике является NP-полной, что означает невозможность полиномиального алгоритма для ее решения. 
  • Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.