Посаженная клика
В теории сложности вычислений или установленная клика скрытая клика в неориентированном графе — это клика, сформированная из другого графа путем выбора подмножества вершин и добавления ребер между каждой парой вершин в подмножестве. Проблема установленной клики — это алгоритмическая проблема отличия случайных графов от графов, в которых есть установленная клика. Это разновидность проблемы клики ; ее можно решить за квазиполиномиальное время , но предполагается, что она не разрешима за полиномиальное время для промежуточных значений размера клики. Гипотеза о том, что полиномиальное решение не существует, называется гипотезой посаженной клики ; оно использовалось в качестве предположения о вычислительной сложности .
Определение
[ редактировать ]Клика в графе — это подмножество вершин, все из которых смежны друг с другом. Посаженная клика — это клика, созданная из другого графа путем добавления ребер между всеми парами выбранного подмножества вершин.
Проблему установленной клики можно формализовать как задачу принятия решения по случайному распределению на графах, параметризованную двумя числами: n (количество вершин) и k (размер клики).Эти параметры можно использовать для создания графика с помощью следующего случайного процесса: [1]
- Создайте случайный граф Эрдеша – Реньи на n вершинах, выбрав независимо для каждой пары вершин, включать ли ребро, соединяющее эту пару, с вероятностью 1/2 для каждой пары.
- Решать, добавлять клику в граф или нет, с вероятностью 1/2; если нет, верните график, сформированный на шаге 1.
- Выберите случайным образом подмножество из k из n вершин и добавьте ребро (если оно еще не существует) между каждой парой выбранных вершин.
Тогда задача состоит в том, чтобы алгоритмически определить, содержит ли один из графов, полученных в результате этого процесса, клику, состоящую как минимум из k вершин.
Верхняя и нижняя границы
[ редактировать ]Существует функция такая, что асимптотически почти наверняка размер наибольшей клики в n -вершинном случайном графе либо равен или , [2] и существует некоторая константа такое, что ожидаемое количество клик размером сходится к бесконечности. Следовательно, следует ожидать, что насаждение клики размером не может быть обнаружен с высокой вероятностью.
По центральной предельной теореме степени вершин случайного графа будут распределены близко к стандартному нормальному распределению со средним значением и стандартное отклонение . Следовательно, когда находится в порядке это привело бы к заметным изменениям в форме распределения. А именно, если вы построите график распределения степеней вершин, оно будет выглядеть как деформированная колоколообразная кривая. Поэтому наиболее интересный диапазон значений параметра k находится между этими двумя значениями: [1]
Алгоритмы
[ редактировать ]Большие клики
[ редактировать ]При достаточно больших значениях параметра k задача о посаженной клике может быть решена (с высокой вероятностью) за полиномиальное время. [1]
Кучера (1995) отмечает, что, когда тогда почти наверняка все вершины посаженной клики имеют более высокую степень, чем все вершины вне клики, что упрощает поиск клики. Он описывает модификацию случайного процесса генерации экземпляров установленной клики, которая делает степени вершин более однородными даже для больших значений k , но показывает, что, несмотря на эту модификацию, установленную клику все равно можно быстро найти. [3]
Алон, Кривелевич и Судаков (1998) доказывают Посаженную клику можно обнаружить с большой вероятностью следующим методом:
- Вычислите собственный вектор матрицы смежности, соответствующий ее второму самому высокому собственному значению .
- Выберите k вершин, координаты которых в этом собственном векторе имеют наибольшие абсолютные значения .
- Возвращает набор вершин, которые смежны как минимум с 3/4 выбранных вершин.
Они показывают, как изменить эту технику, чтобы она продолжала работать всякий раз, когда k по крайней мере пропорционально некоторому кратному квадратному корню из числа вершин. [4] Крупные установленные клики также можно обнаружить с помощью полуопределенного программирования . [5] Комбинаторный метод, основанный на случайной выборке вершин, может достичь той же границы для k и работает за линейное время . [6]
Квазиполиномиальное время
[ редактировать ]Также возможно решить задачу посаженной клики, независимо от выбора k , за квазиполиномиальное время . [7] Поскольку самая большая клика в случайном графе обычно имеет размер около 2 log 2 n , [8] установленную клику размера k (если она существует) можно с высокой вероятностью найти следующим методом:
- Перебрать все наборы S из вершины.
- Для каждого выбора S проверьте, является ли S кликой. Если это так, и вернуть С. , В противном случае найдите множество T вершин, смежных со всеми вершинами в S . Если , Т. верните
Время работы этого алгоритма является квазиполиномиальным, поскольку существует квазиполиномиальное количество вариантов S для обхода цикла. Этот метод гарантированно проверяет набор S , который является подмножеством посаженной клики; с большой вероятностью множество T будет состоять только из остальных членов посаженной клики.
В качестве предположения о твердости
[ редактировать ]Существует две версии гипотезы о установленной клике: одна основана на обнаружении клики (поиск), а другая — на определении существования клики (решение). Гипотеза поиска утверждает, что ни один алгоритм с полиномиальным временем не может найти (с высокой вероятностью) скрытую клику размера << в случайном графе с узлы. [9]
Гипотеза о решении более тонкая. Предположим, нам даны два случайные графы узлов, ровно в одном из которых есть посаженная клика, но мы не знаем, какая именно. В среднем случайный граф с установленной кликой будет иметь больше ребер, чем чисто случайный граф, поскольку процесс установки клики размером ожидается добавление края. Следовательно, мы можем с вероятностью правильно определить, в каком из двух графов находится посаженная клика просто подсчитав количество ребер в каждом графе. Гипотеза о клике, основанной на решениях, утверждает, что это по существу оптимально: она постулирует, что ни один алгоритм с полиномиальным временем не может различить два графа с вероятностью выше, чем . [9] [10]
Хазан и Краутгеймер (2011) использовали предположение о том, что найти установленные клики сложно, в качестве предположения о вычислительной сложности, чтобы доказать, что, если это так, также трудно аппроксимировать лучшее равновесие Нэша в игре с двумя игроками. [7] Гипотеза о посеваемой клике также использовалась в качестве предположения о жесткости, чтобы показать сложность проверки свойств k - независимости случайных распределений: [11] поиск кластеров в социальных сетях, [12] и машинное обучение . [13]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с Арора, Санджив ; Барак, Боаз (2009), Сложность вычислений: современный подход , Cambridge University Press, стр. 362–363, ISBN 9780521424264 .
- ^ Боллобас, Б.; Эрдеш, П. (ноябрь 1976 г.), «Клики в случайных графах» , Mathematical Proceedings of the Cambridge Philosophical Society , 80 (3): 419–427, Бибкод : 1976MPCPS..80..419B , doi : 10.1017/S0305004100053056 , ISSN 1469-8064 , S2CID 16619643
- ^ Кучера, Людек (1995), «Ожидаемая сложность задач разделения графов», Discrete Applied Mathematics , 57 (2–3): 193–212, doi : 10.1016/0166-218X(94)00103-K , hdl : 11858/00 -001М-0000-0014-B73F-2 , МР 1327775 .
- ^ Алон, Нога ; Кривелевич Михаил ; Судаков, Бенни (1998), «Нахождение большой скрытой клики в случайном графе», Случайные структуры и алгоритмы , 13 (3–4): 457–466, CiteSeerX 10.1.1.24.6419 , doi : 10.1002/(SICI)1098 -2418(199810/12)13:3/4<457::AID-RSA14>3.3.CO;2-K , MR 1662795
- ^ Файги, Ю. ; Краутгеймер, Р. (2000), «Обнаружение и сертификация большой скрытой клики в полуслучайном графе», Случайные структуры и алгоритмы , 16 (2): 195–208, doi : 10.1002/(SICI)1098-2418(200003)16 :2<195::AID-RSA5>3.0.CO;2-A .
- ^ Декель, Яэль; Гюрель-Гуревич, Ори; Перес, Юваль (2014), «Нахождение скрытых клик в линейном времени с высокой вероятностью», Combinatorics, Probability and Computing , 23 (1): 29–49, arXiv : 1010.2997 , doi : 10.1017/S096354831300045X , MR 3197965 , S2CID 143 56678 .
- ^ Jump up to: Перейти обратно: а б Хазан, Элад; Краутгеймер, Роберт (2011), «Насколько сложно аппроксимировать лучшее равновесие Нэша?», SIAM Journal on Computing , 40 (1): 79–91, CiteSeerX 10.1.1.511.4422 , doi : 10.1137/090766991 , MR 2765712 .
- ^ Гриметт, Греция ; МакДиармид, CJH (1975), «О раскраске случайных графов», Mathematical Proceedings of the Cambridge Philosophical Society , 77 (2): 313–324, Bibcode : 1975MPCPS..77..313G , doi : 10.1017/S0305004100051124 , MR 0369129 , S2CID 3421302 .
- ^ Jump up to: Перейти обратно: а б Хирахара, Шуичи; Симидзу, Нобутака (2024), «Гипотезы плантационной клики эквивалентны» , Труды 56-го ежегодного симпозиума ACM по теории вычислений : 358–366, doi : 10.1145/3618260.3649751
- ^ Браверман, Марк; Ко, Янг Кун; Рубинштейн, Авиад; Вайнштейн, Омри (2015), Твердость ETH для плотнейшего k -подграфа с идеальной полнотой , arXiv : 1504.08352 , Bibcode : 2015arXiv150408352B .
- ^ Алон, Нога ; Андони, Александр; Кауфман, Тали ; Матулеф, Кевин; Рубинфельд, Ронитт ; Се, Нин (2007), «Тестирование независимости по k и почти по k », STOC'07 — Труды 39-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM, стр. 496–505, doi : 10.1145 /1250790.1250863 , ISBN 9781595936318 , МР 2402475 , S2CID 5050980 .
- ^ Балкан, Мария-Флорина ; Боргс, Кристиан; Браверман, Марк; Чейс, Дженнифер ; Тенг, Шан-Хуа (2013), «Обнаружение эндогенно сформированных сообществ» , Труды двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '13) , SIAM, стр. 767–783, ISBN 978-1-611972-51-1 .
- ^ Берте, Квентин; Риголле, Филипп (2013), «Нижние границы теории сложности для обнаружения разреженных главных компонентов» , Конференция по теории обучения, Журнал исследований машинного обучения , 30 : 1046–1066 .