Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение [ править ]

Клика в графе - это подмножество вершин, все из которых смежны друг с другом. Установленная клика - это клика, созданная из другого графа путем добавления ребер между всеми парами выбранного подмножества вершин.

Проблема с установленной кликой может быть формализована как проблема решения по случайному распределению на графах, параметризованному двумя числами: n (количество вершин) и k (размер клики). Эти параметры могут использоваться для создания графика с помощью следующего случайного процесса: [1]

  1. Создайте случайный граф Эрдеша – Реньи на n вершинах, независимо выбрав для каждой пары вершин, включать ли ребро, соединяющее эту пару, с вероятностью 1/2 для каждой пары.
  2. Решите, добавлять ли клику к графу с вероятностью 1/2; в противном случае верните график, сформированный на шаге 1.
  3. Выберите случайным образом подмножество k из n вершин и добавьте ребро (если оно еще не присутствует) между каждой парой выбранных вершин.

Тогда проблема состоит в том, чтобы алгоритмически определить, содержит ли один из графов, полученных в результате этого процесса, клику из не менее k вершин.

С большой вероятностью размер наибольшей клики в случайном графе с n вершинами близок к 2 log 2 n . А когда k больше квадратного корня из n , вершины установленной клики могут быть распознаны как имеющие необычно большие степени , что упрощает поиск установленной клики. Следовательно, наиболее интересный диапазон значений параметра k находится между этими двумя значениями [1]

Алгоритмы [ править ]

Большие клики [ править ]

При достаточно больших значениях параметра k задача о насаждаемой клике может быть решена (с большой вероятностью) за полиномиальное время. [1]

Кучера (1995) замечает, что тогда почти наверняка все вершины установленной клики имеют более высокую степень, чем все вершины вне клики, что делает клику очень простой для поиска. Он описывает модификацию случайного процесса генерации экземпляров внедренной клики, которая делает степени вершин более однородными даже для больших значений  k , но показывает, что, несмотря на эту модификацию, внедренную клику все же можно найти быстро. [2]

Алон, Кривелевич и Судаков (1998) доказательство наличия насаждаемой клики может быть с большой вероятностью найдено следующим методом:

  1. Рассчитайте собственный вектор из матрицы смежности , соответствующей его вторым по величине собственного значения .
  2. Выберите k вершин, координаты которых в этом собственном векторе имеют наибольшие абсолютные значения .
  3. Возвращает набор вершин, которые примыкают как минимум к 3/4 выбранных вершин.

Они показывают, как изменить эту технику, чтобы она продолжала работать всякий раз, когда k по крайней мере пропорционально некоторому кратному квадратному корню из числа вершин. [3] Крупные клики также можно найти с помощью полуопределенного программирования . [4] Комбинаторный метод, основанный на случайной выборке вершин, позволяет достичь того же ограничения на k и работает за линейное время . [5]

Квазиполиномиальное время [ править ]

Также возможно решить проблему с установленной кликой, независимо от выбора k , за квазиполиномиальное время . [6] Поскольку наибольшая клика в случайном графе обычно имеет размер около 2 log 2 n , [7] установленная клика размера k (если она существует) может быть найдена с высокой вероятностью следующим методом:

  1. Перебор всех множеств S из вершин.
  2. Для каждого выбора S проверьте, является ли S кликой. Если она есть, и , возвращение S . В противном случае, найти множество Т вершин, смежных вершин в S . Если , вернуть T .

Время работы этого алгоритма квазиполиномиально, потому что существует квазиполиномиально много вариантов S для перебора . Этот метод гарантированно пробует набор S, который является подмножеством установленной клики; с большой вероятностью множество T будет состоять только из других членов посаженной клики.

В качестве предположения о твердости [ править ]

Гипотеза о заложенной клике - это гипотеза о том, что не существует алгоритма с полиномиальным временем, который принимает в качестве входных графов, созданных процессом насаждаемой клики, и отличает те, у которых есть установленные клики, от тех, которые не установили клики, с вероятностью, значительно большей, чем случайная вероятность. [8]

Hazan & Krauthgamer (2011) использовали предположение о том, что найти заложенные клики сложно, в качестве предположения о вычислительной сложности, чтобы доказать, что если это так, то также трудно аппроксимировать наилучшее равновесие по Нэшу в игре для двух игроков. [6] Гипотеза о заложенной клике также использовалась в качестве предположения о твердости, чтобы показать сложность проверки свойств k -независимости случайных распределений, [9] нахождения кластеров в социальных сетях [10] и машинного обучения . [11]

Ссылки [ править ]

  1. ^ a b c Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Cambridge University Press, стр. 362–363, ISBN 9780521424264.
  2. ^ Кучера, Людек (1995), "Ожидаемой сложность проблемы разделения графов", Дискретная прикладная математика , 57 (2-3): 193-212, DOI : 10.1016 / 0166-218X (94) 00103-К , ЛВП : 11858 / 00-001M-0000-0014-B73F-2 , Руководство 1327775 .
  3. ^ Алон, Нога ; Кривелевич Михаил ; Судаков, Бенни (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  
  4. ^ Feige, U .; Krauthgamer, R. (2000), "Finding и сертификации большой скрытой клике в полуслучайного графе" Случайные Структуры и алгоритмы , 16 (2): 195-208, DOI : 10.1002 / (SICI) 1098-2418 (200003) 16 : 2 <195 :: AID-RSA5> 3.0.CO; 2-A.
  5. ^ Декель, Яэль; Гурель-Гуревич, Ори; Перес, Юваль (2014), «Обнаружение скрытых клик за линейное время с высокой вероятностью», Комбинаторика, вероятность и вычисления , 23 (1): 29–49, arXiv : 1010.2997 , doi : 10.1017 / S096354831300045X , MR 3197965 .
  6. ^ а б Хазан, Эльад; Krauthgamer, Роберт (2011), "Как трудно это , чтобы приблизить лучшее равновесие Нэша?", SIAM журнал по вычислениям , 40 (1): 79-91, CiteSeerX 10.1.1.511.4422 , DOI : 10,1137 / 090766991 , MR 2765712  .
  7. ^ Гриммет, GR ; МакДирмид, CJH (1975), "О окраски случайных графов", Математическая Труды Кембриджского философского общества , 77 (2): 313-324, Bibcode : 1975MPCPS..77..313G , DOI : 10,1017 / S0305004100051124 , МР 0369129 .
  8. ^ Браверман, Марк; Ко, Ён Кун; Рубинштейн, Авиад; Вайнштейн, Омри (2015), Твердость ETH для плотного k- подграфа с идеальной полнотой , arXiv : 1504.08352 , Bibcode : 2015arXiv150408352B.
  9. ^ Алон, Нога ; Андони, Александр; Кауфман, Тали; Матулеф, Кевин; Рубинфельд, Ронитт; Се, Нины (2007), "Testing к -wise и почти K -wise независимости", STOC'07-Труды 39 - й ежегодного симпозиума ACM по теории вычислений , Нью - Йорк.: АКМ, С. 496-505, DOI : 10,1145 /1250790.1250863 , ISBN 9781595936318, Руководство по ремонту  2402475.
  10. ^ Балкан, Мария-Флорина ; Боргс, Кристиан; Браверман, Марк; Чайес, Дженнифер ; Тэн, Шан-Хуа (2013), «Поиск эндогенно сформированных сообществ» , Материалы двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '13) , SIAM, стр. 767–783, ISBN 978-1-611972-51-1.
  11. ^ Бертет, Квентин; Риголле, Филипп (2013), "Теоретические нижние оценки сложности для обнаружения разреженных главных компонент" , Конференция по теории обучения, Journal of Machine Learning Research , 30 : 1046–1066.