Задача про кліку

Задача про кліку належить до класу NP-повних задач в області теорії графів. Вперше її сформулював 1972 року Річард Карп.

Граф з клікою розміру 3.

Клікою в неорієнтованому графі називається підмножина вершин, кожні дві з яких з'єднані ребром графу. Іншими словами, це повний підграф первісного графа. Розмір кліки визначається як число вершин в ній. Задача про кліку існує у двох варіантах: у задачі розпізнавання потрібно визначити, чи існує в заданому графі G кліка розміру k, тоді як в обчислювальному варіанті потрібно знайти в заданому графі G кліку максимального розміру або всі максимальні кліки (такі, що не можна збільшити).

Історія

Хоча повні підграфи довгий час вивчалися в математиці, термін «кліка» і задача алгоритмічно оголошеного кліка обидва походять із соціальних наук, де повні підграфи використовувались як модель соціальних кліків, груп людей, які всі знають один одного. Термінологія «кліка» походить від Люса та Перрі (1949), та перший алгоритм розв'язання задачі про кліку винайшли Харарі та Росс (1957), для соціологічних досліджень.

Після роботи Харарі і Росса, багато інших авторів розробили алгоритми для розв'язання різних версій задачі про кліку. У 1970-х, дослідники почали вивчати ці алгоритми з точки зору найгіршого аналізу; див., наприклад, Тарьян та Трояновськи (1977), перші роботи про вирішення найгіршого максимального кліку. Крім того, у 1970-х роках, починаючи з роботи Кука (1971) і Карпа (1972), дослідники почали знаходити математичне обґрунтування для сприйманої складності кліку проблеми в теорії NP-повноти і пов'язаних незговірливих результатів. У 1990-ті роки, був написаний цикл робіт, починаючи з Фейга і співавт. (1991) і повідомив у той час пресі про те, що неможливо розв'язати цю задачу максимально точно та ефективно.

NP-Повнота

NP-повнота задачі про кліку випливає з NP-повноти задача про незалежну множину (вершин). Легко показати, що необхідною і достатньою умовою для існування кліки розміру k є наявність незалежної множини розміру не менше k в доповненні графу. Це очевидно, оскільки повнота підграфу означає, що його доповнення не містить жодного ребра.

Інший доказ NP-повноти можна знайти в книзі «Алгоритми: побудова й аналіз».

Алгоритми

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

Інший алгоритм працює так: дві кліки розміру n і m «склеюються» у велику кліку розміру (n + m), причому клікою розміру 1 покладається окрема вершина графу. Алгоритм завершується, як тільки жодного злиття більше здійснити не можна. Час роботи даного алгоритму є лінійним, проте він є евристичним, оскільки не завжди призводить до знаходження кліки максимального розміру. Як приклад невдалого завершення можна навести випадок, коли вершини, що належать максимальній кліці, виявляються розділені й перебувають у кліках меншого розміру, причому останні вже не можуть бути «склеєними» між собою.

Див. також

• Алгоритм Брона-Кербоша — швидкий пошук клік
• Соціальний граф
• Словник термінів теорії графів

Література

• Cook, Stephen A. (1971). The Complexity of Theorem-Proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. Shaker Heights, Ohio. с. 151—158. Архів оригіналу за 3 травня 2006. Процитовано 11 червня 2007.
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.2: GT19, pg.194.
• Cook, S. A. (1971), The complexity of theorem-proving procedures, [[Symposium on Theory of Computing|Proc. 3rd ACM Symposium on Theory of Computing]], с. 151—158, doi:10.1145/800157.805047, архів оригіналу за 30 жовтня 2019, процитовано 29 травня 2014 {{citation}}: Назва URL містить вбудоване вікіпосилання (довідка).
• Downey, R. G.; Fellows, M. R. (1995), Fixed-parameter tractability and completeness. II. On completeness for W[1], Theoretical Computer Science, 141 (1–2): 109—131, doi:10.1016/0304-3975(94)00097-3
• Downey, R. G.; Fellows, M. R. (1999), Parameterized complexity, Springer-Verlag, ISBN 0-387-94883-X.
• Eisenbrand, F.; Grandoni, F. (2004), On the complexity of fixed parameter clique and dominating set, Theoretical Computer Science, 326 (1–3): 57—67, doi:10.1016/j.tcs.2004.05.009
• Eppstein, David; Löffler, Maarten; Strash, Darren (2010), Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time, у Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (ред.), 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, Lecture Notes in Computer Science, т. 6506, Springer-Verlag, с. 403—414, arXiv:1006.5440, doi:10.1007/978-3-642-17517-6_36, ISBN 978-3-642-17516-9
• Eppstein, David; Strash, Darren (2011), Listing all maximal cliques in large sparse real-world graphs, 10th International Symposium on Experimental Algorithms, arXiv:1103.0318.
• Erdős, Paul; Szekeres, George (1935), A combinatorial problem in geometry (PDF), Compositio Mathematica, 2: 463—470, архів оригіналу (PDF) за 22 травня 2020, процитовано 29 травня 2014.