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

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

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

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

Історія

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

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

NP-Повнота

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

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

Алгоритми

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

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

Див. також

• Алгоритм Брона — Кербоша — швидкий пошук клік.

Примітки

1. ↑ Karp Richard (1972) "Reducibility among combinatorial problems"  
2. ↑ Кормен, Т., Лейзерсон, Ч., Рівест, Р., Штайн, К. Алгоритмы: побудова та аналіз = Introduction to Algorithms / Під ред. И. В. Красикова. — 2-е вид. — М.: Вільямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
3. Kolata, Gina (26.06.1990), "In a Frenzy, Math Enters Age of Electronic Mail",New York Times.

Література

• 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. Процитовано 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 {{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.