Проблема клики - Clique problem

В алгоритм грубой силы находит 4-клику в этом 7-вершинном графе (дополнение к 7-вершинному граф путей ) путем систематической проверки всех C (7,4) = 35 4-вершинных подграфов для полноты.

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

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

Большинство версий проблемы клики сложны. Проблема решения клики НП-полный (один из 21 NP-полная задача Карпа ). Проблема поиска максимальной клики заключается в том, что трудноразрешимый с фиксированными параметрами и трудно приблизиться. И для перечисления всех максимальных клик может потребоваться экспоненциальное время поскольку существуют графы с экспоненциально большим числом максимальных клик. Следовательно, большая часть теории проблемы клики посвящена определению особых типов графов, допускающих более эффективные алгоритмы, или установлению вычислительной сложности общей проблемы в различных моделях вычислений.

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

История и приложения

Изучение полных подграфов в математике предшествовало терминологии «клика». Например, полные подграфы впервые появляются в математической литературе при теоретико-графической переформулировке Теория Рамсея к Эрдеш и Секереш (1935). Но термин «клика» и проблема алгоритмического перечисления клик пришли из социальных наук, где полные подграфы используются для моделирования социальные клики, группы людей, которые все знают друг друга. Люс и Перри (1949) использовал графы для моделирования социальных сетей и адаптировал терминологию социальных наук к теории графов. Они первыми назвали полные подграфы «кликами». Первый алгоритм решения проблемы клики - это алгоритм Харари и Росс (1957),[1] исследователи социальных наук также определили различные другие типы клик и максимальных клик в социальной сети, «сплоченные подгруппы» людей или субъектов в сети, все из которых имеют один из нескольких различных видов взаимосвязи. Многие из этих обобщенных понятий клик также можно найти, построив неориентированный граф, ребра которого представляют связанные пары акторов из социальной сети, а затем применив алгоритм для проблемы клик к этому графу.[2]

Со времен работы Харари и Росс многие другие разработали алгоритмы для различных версий проблемы клики.[1] В 1970-х годах исследователи начали изучать эти алгоритмы с точки зрения анализ наихудшего случая. См., Например, Тарьян и Трояновский (1977), ранняя работа над наихудшим случаем сложности задачи о максимальной клике. Также в 1970-е годы, начиная с работ Повар (1971) и Карп (1972) исследователи начали использовать теорию NP-полнота и связанные результаты о неразрешимости, чтобы дать математическое объяснение воспринимаемой сложности проблемы клики. В 90-е годы появилась серия революционных работ, начиная с Feige et al. (1991) и сообщается в Нью-Йорк Таймс,[3] показал, что (при условии P ≠ NP ) даже невозможно приблизительный проблема точно и качественно.

Алгоритмы поиска кликов использовались в химия, чтобы найти химические вещества, соответствующие целевой структуре[4] и моделировать молекулярный док и места связывания химических реакций.[5] Их также можно использовать для поиска похожих структур в разных молекулах.[6]В этих приложениях формируется граф, в котором каждая вершина представляет собой согласованную пару атомов, по одному от каждой из двух молекул. Две вершины соединяются ребром, если совпадения, которые они представляют, совместимы друг с другом. Совместимость может означать, например, что расстояния между атомами в двух молекулах приблизительно равны с точностью до некоторого заданного допуска. Клика на этом графике представляет собой набор совпадающих пар атомов, в которых все совпадения совместимы друг с другом.[7] Частным случаем этого метода является использование модульное произведение графов чтобы уменьшить проблему поиска максимальный общий индуцированный подграф двух графов к задаче поиска максимальной клики в их произведении.[8]

В автоматическая генерация тестовой таблицы, поиск кликов может помочь ограничить размер тестового набора.[9] В биоинформатика, алгоритмы поиска кликов использовались для вывода эволюционные деревья,[10] предсказывать белковые структуры,[11] и найти тесно взаимодействующие кластеры белков.[12] Перечисление клик в граф зависимостей является важным шагом в анализе определенных случайных процессов.[13] В математике Гипотеза Келлера на облицовке плиткой гиперкубы был опровергнут Лагариас и Шор (1992), который использовал алгоритм поиска кликов на связанном графе, чтобы найти контрпример.[14]

Определения

Основная статья: Клика (теория графов)
Показанный граф имеет одну максимальную клику, треугольник {1,2,5} и еще четыре максимальных клики, пары {2,3}, {3,4}, {4,5} и {4,6} .

An неориентированный граф формируется конечный набор из вершины и набор неупорядоченные пары вершин, которые называются края. По соглашению, при анализе алгоритмов количество вершин графа обозначается как п а количество ребер обозначено м. А клика в графике грамм это полный подграф из грамм. То есть это подмножество K таких вершин, что каждые две вершины в K две конечные точки ребра в грамм. А максимальная клика - это клика, в которую больше нельзя добавлять вершины. Для каждой вершины v не является частью максимальной клики, должна быть другая вершина ш находящийся в клике и несмежный с v, предотвращая v от добавления в клику. А максимальная клика - клика, включающая максимально возможное количество вершин. Кликовое число ω(грамм) - количество вершин в максимальной клике из грамм.[1]

Были изучены несколько тесно связанных задач поиска клик.[15]

  • В задаче о максимальной клике входом является неориентированный граф, а выходом - максимальная клика в графе. Если имеется несколько максимальных клик, одна из них может быть выбрана произвольно.[15]
  • В задаче взвешенной максимальной клики входом является неориентированный граф с весами на его вершинах (или, реже, ребрами), а на выходе - клика с максимальным общим весом. Задача максимальной клики - это частный случай, когда все веса равны.[16] Помимо проблемы оптимизации суммы весов, изучались и другие более сложные задачи бикритериальной оптимизации.[17]
  • В задаче перечисления максимальных клик входом является неориентированный граф, а выходом - список всех его максимальных клик. Проблема максимальной клики может быть решена с использованием в качестве подпрограммы алгоритма для задачи перечисления максимальной клики, поскольку максимальная клика должна быть включена среди всех максимальных клик.[18]
  • в k-clique, вход - неориентированный граф и число k. На выходе получается клика с k вершины, если таковые существуют, или специальное значение, указывающее, что нет k-clique иначе. В некоторых вариантах этой задачи в выводе должны быть перечислены все клики размера k.[19]
  • В задаче решения о клике входом является неориентированный граф и число k, а на выходе Логическое значение: истина, если график содержит k-clique и false в противном случае.[20]

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

Проблема клики и проблема независимого множества дополняют друг друга: клика в грамм является независимым множеством в дополнительный граф из грамм наоборот.[21] Таким образом, многие результаты вычислений могут быть одинаково хорошо применены к любой проблеме, а в некоторых исследовательских работах не проводится четкого различия между этими двумя проблемами. Однако две проблемы имеют разные свойства при применении к ограниченным семействам графов. Например, проблема клики может быть решена за полиномиальное время для планарные графы[22] в то время как проблема независимого множества остается NP-трудной на планарных графах.[23]

Алгоритмы

Нахождение единственной максимальной клики

А максимальный клика, иногда называемая максимальной по включению, - это клика, не входящая в большую клику. Следовательно, каждая клика содержится в максимальной клике.[24]Максимальные клики могут быть очень маленькими. Граф может содержать немаксимальную клику с множеством вершин и отдельную клику размера 2, которая является максимальной. Хотя максимальная (т. Е. Наибольшая) клика обязательно максимальна, обратное неверно. Есть несколько типов графов, в которых каждая максимальная клика максимальна; эти дополняет из хорошо покрытые графики, в котором каждый максимальный независимый набор максимален.[25]Однако другие графы имеют максимальные клики, которые не являются максимальными.

Единственная максимальная клика может быть найдена простым жадный алгоритм. Начиная с произвольной клики (например, любой отдельной вершины или даже пустого множества), увеличивайте текущую клику по одной вершине за раз, перебирая оставшиеся вершины графа. Для каждой вершины v что этот цикл исследует, добавьте v к клике, если она смежна с каждой вершиной, которая уже находится в клике, и отбросить v иначе. Этот алгоритм работает в линейное время.[26] Из-за простоты поиска максимальных клик и их потенциально небольшого размера гораздо больше внимания было уделено гораздо более сложной алгоритмической проблеме поиска максимальной или иной большой клики, чем проблеме поиска одной максимальной клики. некоторые исследования в параллельные алгоритмы изучил проблему поиска максимальной клики. В частности, проблема поиска лексикографически первый максимальная клика (найденная вышеописанным алгоритмом) оказалась полный за класс функций с полиномиальным временем. Этот результат означает, что проблема вряд ли будет разрешима в рамках параллельного класса сложности. NC.[27]

Клики фиксированного размера

Можно проверить, грамм содержит k-вершинная клика, и найдите любую такую ​​клику, которую она содержит, используя алгоритм грубой силы. Этот алгоритм исследует каждый подграф с k вершины и проверяет, образует ли он клику. Это требует времени О(пk k2), как выражено с помощью нотация большой O.Это потому, что есть О(пk) подграфы для проверки, каждый из которых имеет О(k2) края, наличие которых в грамм нужно проверить. Таким образом, проблема может быть решена в полиномиальное время в любое время k фиксированная константа. Однако когда k не имеет фиксированного значения, но вместо этого может меняться как часть входных данных для задачи, время экспоненциально.[28]

Простейшим нетривиальным случаем задачи поиска клики является поиск треугольника в графе или эквивалентное определение того, является ли граф без треугольников.На графике грамм с м краев, может быть не более Θ (м3/2) треугольники (используя большая тета-запись чтобы указать, что эта граница жесткая). Худший случай для этой формулы возникает, когда грамм сама по себе клика. Следовательно, алгоритмы перечисления всех треугольников должны занимать не менее Ω (м3/2) время в худшем случае (используя большое обозначение омега ), и известны алгоритмы, соответствующие этому временному интервалу.[29] Например, Тиба и Нишизеки (1985) описать алгоритм, который сортирует вершины в порядке от наивысшей степени к самой низкой, а затем выполняет итерацию по каждой вершине v в отсортированном списке, ища треугольники, которые включают v и не включать в список никакую предыдущую вершину. Для этого алгоритм помечает всех соседей v, перебирает все ребра, инцидентные соседу v вывод треугольника для каждого ребра, имеющего две отмеченные конечные точки, а затем удаляет отметки и удаляет v из графика. Как показывают авторы, время выполнения этого алгоритма пропорционально родословие графа (обозначается а(грамм)), умноженное на количество ребер, которое О(м а(грамм)). Так как древовидность не более О(м1/2), этот алгоритм работает во времени О(м3/2). В общем, все k-вершинные клики могут быть перечислены с помощью аналогичного алгоритма, который требует времени, пропорционального количеству ребер, умноженному на древовидность в степени (k − 2). Для графов постоянной древовидности, таких как планарные графы (или вообще графы из любых нетривиальных семейство минорных замкнутых графов ) этот алгоритм принимает О(м) время, которое является оптимальным, поскольку оно линейно зависит от размера входных данных.[19]

Если кому-то нужен только один треугольник или гарантия того, что график не содержит треугольников, возможны более быстрые алгоритмы. В качестве Итаи и Родех (1978) заметим, граф содержит треугольник тогда и только тогда, когда его матрица смежности и квадрат матрицы смежности содержат ненулевые элементы в одной и той же ячейке. Поэтому методы быстрого матричного умножения, такие как Алгоритм Копперсмита – Винограда может применяться для поиска треугольников во времени О(п2.376). Алон, Юстер и Цвик (1994) использовали быстрое матричное умножение для улучшения О(м3/2) алгоритм поиска треугольников для О(м1.41). Эти алгоритмы, основанные на быстром умножении матриц, также были распространены на задачи поиска k-клика для больших значений k.[30]

Список всех максимальных клик

В результате Луна и Мозер (1965), каждый п-вершинный граф имеет не более 3п/3 максимальные клики. Их можно перечислить по Алгоритм Брона – Кербоша, рекурсивный возврат процедура Брон и Кербош (1973). Основная рекурсивная подпрограмма этой процедуры имеет три аргумента: частично построенную (не максимальную) клику, набор вершин-кандидатов, которые могут быть добавлены в клику, и другой набор вершин, которые не следует добавлять (потому что это приведет к в уже найденную клику). Алгоритм пытается добавить вершины-кандидаты одну за другой в частичную клику, выполняя рекурсивный вызов для каждой из них. После проверки каждой из этих вершин он перемещает ее в набор вершин, которые больше не нужно добавлять. Можно показать, что варианты этого алгоритма имеют наихудшее время работы. О(3п/3), соответствующее количеству кликов, которые могут быть перечислены.[31] Следовательно, это обеспечивает наихудшее оптимальное решение проблемы перечисления всех максимальных клик. Кроме того, широко сообщалось, что алгоритм Брона – Кербоша на практике работает быстрее, чем его альтернативы.[32]

Однако, когда количество клик значительно меньше, чем в худшем случае, другие алгоритмы могут быть предпочтительнее. В качестве Цукияма и др. (1977) Как показано, также можно перечислить все максимальные клики в графе за время, полиномиальное на сгенерированную клику. Такой алгоритм, как их, в котором время работы зависит от размера вывода, известен как алгоритм, чувствительный к выходу. Их алгоритм основан на следующих двух наблюдениях, связывающих максимальные клики данного графа. грамм максимальным кликам графа грамм \ v образованный удалением произвольной вершины v из грамм:

  • Для каждой максимальной клики K из грамм \ v, либо K продолжает образовывать максимальную клику в грамм, или же K ⋃ {v} образует максимальную клику в грамм. Следовательно, грамм имеет как минимум столько же максимальных клик, сколько грамм \ v делает.
  • Каждая максимальная клика в грамм что не содержит v является максимальной кликой в грамм \ v, и каждая максимальная клика в грамм что действительно содержит v может быть сформирован из максимальной клики K в грамм \ v добавляя v и удаление не-соседей v из K.

Используя эти наблюдения, они могут генерировать все максимальные клики в грамм рекурсивным алгоритмом, который выбирает вершину v произвольно и тогда для каждой максимальной клики K в грамм \ v, выводит как K и клика, образованная добавлением v к K и удаление несоседей v. Однако некоторые клики грамм могут быть сгенерированы таким образом из более чем одной родительской клики грамм \ v, поэтому они удаляют дубликаты, выводя клику в грамм только когда его родитель в грамм \ v является лексикографически максимальным среди всех возможных родительских клик. На основе этого принципа они показывают, что все максимальные клики в грамм могут быть созданы со временем О(млн) за клику, где м количество ребер в грамм и п количество вершин. Чиба и Нишизеки (1985) улучшить это до O (ма) за клику, где а - древовидность данного графа. Макино и Уно (2004) предоставить альтернативный алгоритм, чувствительный к выходу, основанный на быстром умножении матриц. Джонсон и Яннакакис (1988) показать, что можно даже перечислить все максимальные клики в лексикографический порядок с полиномиальная задержка за клику. Однако выбор порядка важен для эффективности этого алгоритма: для обратного этого порядка не существует алгоритма полиномиальной задержки, если только P = NP.

На основе этого результата можно перечислить все максимальные клики за полиномиальное время для семейств графов, в которых количество клик полиномиально ограничено. Эти семьи включают хордовые графы, полные графики, графы без треугольников, интервальные графики, графы ограниченных коробочка, и планарные графы.[33] В частности, планарные графы имеют О(п) клики, не более постоянного размера, которые могут быть перечислены за линейное время. То же самое верно для любого семейства графов, которое одновременно редкий (с числом ребер, не превышающим константу, умноженную на число вершин) и закрыто при операции взятия подграфов.[19][34]

Нахождение максимальных клик в произвольных графах

Можно найти максимальную клику или кликовое число произвольного п-вершинный график во времени О(3п/3) = О(1.4422п) используя один из описанных выше алгоритмов, чтобы перечислить все максимальные клики в графе и вернуть самую большую. Однако для этого варианта проблемы клики возможны лучшие временные рамки для наихудшего случая. Алгоритм Тарьян и Трояновский (1977) решает эту проблему вовремя О(2п/3) = О(1.2599п). Это рекурсивная схема обратного отслеживания, аналогичная схеме Алгоритм Брона – Кербоша, но может исключить некоторые рекурсивные вызовы, когда можно показать, что найденные в вызове клики будут неоптимальными. Цзянь (1986) улучшил время О(20.304п) = О(1.2346п), и Робсон (1986) улучшил это до О(20.276п) = О(1.2108п) время за счет большего использования пространства. Алгоритм Робсона сочетает в себе аналогичную схему поиска с возвратом (с более сложным анализом случая) и динамическое программирование метод, в котором оптимальное решение предварительно вычисляется для всех малых связных подграфов дополнительный граф. Эти частичные решения используются для сокращения рекурсии с возвратом. Самый быстрый алгоритм, известный сегодня, - это усовершенствованная версия этого метода, разработанная Робсон (2001) который бежит во времени О(20.249п) = О(1.1888п).[35]

Также было проведено обширное исследование эвристические алгоритмы для решения проблем с максимальным количеством кликов без гарантий выполнения наихудшего случая, на основе методов, включая ветвь и переплет,[36] местный поиск,[37] жадные алгоритмы,[38] и программирование в ограничениях.[39] Нестандартные вычислительные методологии, предложенные для поиска клик, включают: ДНК-вычисления[40] и адиабатические квантовые вычисления.[41] Проблема максимальной клики была предметом проблемы реализации, спонсируемой DIMACS в 1992–1993 гг.,[42] а также общедоступный сборник графиков, используемых в качестве ориентиров для решения задачи.[43]

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

В этом граф перестановок, максимальные клики соответствуют самые длинные убывающие подпоследовательности (4,3,1) и (4,3,2) определяющей перестановки.

Планарные графики и другие семейства разреженных графов обсуждались выше: они имеют линейно много максимальных клик ограниченного размера, которые могут быть перечислены за линейное время.[19] В частности, для плоских графов любая клика может иметь не более четырех вершин, по Теорема Куратовского.[22]

Совершенные графики определяются тем, что их кликовое число равно их хроматическое число, и что это равенство выполняется также в каждом из их индуцированные подграфы. Для идеальных графов можно найти максимальную клику за полиномиальное время, используя алгоритм, основанный на полуопределенное программирование.[44]Однако этот метод является сложным и некомбинаторным, и для многих подклассов совершенных графов были разработаны специальные алгоритмы поиска клик.[45] в дополнить графы из двудольные графы, Теорема Кёнига позволяет решить проблему максимальной клики, используя методы соответствие. В другом классе совершенных графов графы перестановок, максимальная клика - это самая длинная убывающая подпоследовательность перестановки, определяющей граф, и может быть найдена с использованием известных алгоритмов для самой длинной убывающей задачи подпоследовательности. И наоборот, каждый экземпляр проблемы самой длинной убывающей подпоследовательности можно эквивалентно описать как задачу поиска максимальной клики в графе перестановок.[46] Эвен, Пнуэли и Лемпель (1972) предоставить альтернативный алгоритм квадратичного времени для максимальных клик в графики сопоставимости, более широкий класс совершенных графов, который включает графы перестановок как частный случай.[47] В хордовые графы максимальные клики можно найти, перечислив вершины в порядке исключения и проверив клику окрестности каждой вершины в этом порядке.[48]

В некоторых случаях эти алгоритмы могут быть расширены и на другие, несовершенные классы графов. Например, в круговой график, окрестность каждой вершины является графом перестановок, поэтому максимальную клику в круговом графе можно найти, применив алгоритм графа перестановок к каждой окрестности.[49] Точно так же в граф единичного диска (с известным геометрическим представлением), существует алгоритм полиномиального времени для максимальных клик, основанный на применении алгоритма дополнений двудольных графов к общим окрестностям пар вершин.[50]

Алгоритмическая задача поиска максимальной клики в случайный граф взяты из Модель Эрдеша – Реньи (в котором каждое ребро появляется с вероятностью 1/2, независимо от других ребер) было предложено Карп (1976). Поскольку максимальная клика в случайном графе имеет логарифмический размер с высокой вероятностью, ее можно найти путем перебора за ожидаемое время. 2О(бревно2п). Это квазиполиномиальная оценка времени.[51] Хотя кликовое число таких графов обычно очень близко к 2 журнала2п, просто жадные алгоритмы а также более сложные методы рандомизированного приближения находят только клики с размером бревно2п, вдвое меньше. Количество максимальных клик в таких графах с большой вероятностью экспоненциально по бревно2п, что предотвращает запуск методов, перечисляющих все максимальные клики, за полиномиальное время.[52] Из-за сложности этой проблемы несколько авторов исследовали посаженная клика проблема клик на случайных графах, которые были увеличены за счет добавления больших клик.[53] Пока спектральные методы[54] и полуопределенное программирование[55] может обнаруживать скрытые клики размера Ω (√п), в настоящее время неизвестны полиномиальные алгоритмы для обнаружения алгоритмов размера о(√п) (выражено с использованием маленькая нотация ).[56]

Алгоритмы приближения

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

Файги (2004) описывает алгоритм с полиномиальным временем, который находит клику размера Ω ((журналп/ журнал журналп)2) в любом графе с кликовым числом Ω (п/бревноkп) для любой постоянной k. Используя этот алгоритм, когда кликовое число данного входного графа находится между п/бревноп и п/бревно3п, переходя на другой алгоритм Боппана и Халльдорссон (1992) для графов с более высокими числами кликов и выбор клики с двумя вершинами, если оба алгоритма ничего не находят, Feige предоставляет алгоритм аппроксимации, который находит клику с числом вершин с коэффициентом O (п(журнал журналап)2/бревно3п) от максимума. Хотя коэффициент аппроксимации этого алгоритма слабый, он самый известный на сегодняшний день.[58] Результаты на твердость приближения описанные ниже предполагают, что не может быть алгоритма аппроксимации с коэффициентом аппроксимации, значительно меньшим, чем линейный.

Нижние границы

NP-полнота

Экземпляр 3-CNF Satisfiability (x ∨ x ∨ y) ∧ (~ x ∨ ~ y ∨ ~ y) ∧ (~ x ∨ y ∨ y) сведен к Clique. Зеленые вершины образуют 3-клику и соответствуют удовлетворительному назначению.[59]

Проблема решения клики НП-полный. Это был один из Оригинальная 21 задача Ричарда Карпа показал NP-полную в своей статье 1972 г. «Сводимость среди комбинаторных проблем».[60] Эта проблема также упоминалась в Стивен Кук Статья, вводящая теорию NP-полных задач.[61] Из-за сложности проблемы решения проблема поиска максимальной клики также является NP-сложной.Если бы можно было ее решить, можно было бы также решить проблему принятия решения, сравнивая размер максимальной клики с параметром размера, заданным в качестве входных данных в задаче решения.

Доказательство NP-полноты Карпа - это много-одно сокращение от Проблема логической выполнимости.Он описывает, как переводить логические формулы в конъюнктивная нормальная форма (CNF) в эквивалентные экземпляры задачи о максимальной клике.[62]Выполнимость, в свою очередь, была доказана NP-полнотой в Теорема Кука – Левина. Из заданной формулы CNF Карп формирует граф, у которого есть вершина для каждой пары (v,c), куда v переменная или ее отрицание и c это предложение в формуле, которое содержит v. Две из этих вершин соединены ребром, если они представляют совместимые присвоения переменных для разных предложений. То есть есть преимущество от (v,c) к (ты,d) в любое время c ≠ d и ты и v не отрицания друг друга. Если k обозначает количество пунктов в формуле CNF, тогда k-вершинные клики в этом графе представляют последовательные способы присвоения ценности истины к некоторым его переменным, чтобы удовлетворить формулу. Следовательно, формула выполнима тогда и только тогда, когда a k-вершинная клика существует.[60]

Некоторые NP-полные задачи (например, задача коммивояжера в планарные графы ) может быть решена за время, которое экспоненциально в сублинейной функции входного параметра размера п, значительно быстрее, чем поиск методом перебора.[63]Однако маловероятно, что такая субэкспоненциальная граница времени возможна для проблемы клики в произвольных графах, поскольку она подразумевает аналогичные субэкспоненциальные границы для многих других стандартных NP-полных задач.[64]

Сложность схемы

Монотонная схема для обнаружения k-клик в п-вершинный граф для k = 3 и п = 4. Каждый вход в схему кодирует наличие или отсутствие определенного (красного) ребра в графе. В схеме используется один внутренний логический элемент и для обнаружения каждого потенциала. k-клика.

Вычислительная сложность проблемы клики привела к тому, что ее использовали для доказательства нескольких нижних оценок в сложность схемы. Существование клики данного размера является свойство монотонного графа, что означает, что если клика существует в данном графе, она будет существовать в любом суперграф. Поскольку это свойство монотонное, должна существовать монотонная схема, использующая только и ворота и или ворота, чтобы решить проблему выбора клики для заданного фиксированного размера клики. Однако можно доказать, что размер этих схем является суперполиномиальной функцией количества вершин и размера клики, экспоненциальной от кубического корня из числа вершин.[65] Даже если небольшое количество НЕ ворота допустимы, сложность остается суперполиномиальной.[66] Кроме того, глубина монотонной схемы для задачи клики с использованием вентилей ограниченного фан-ин должен быть не меньше полинома размера клики.[67]

Сложность дерева решений

Простое дерево решений для обнаружения наличия 3-клики в 4-вершинном графе. В нем используется до 6 вопросов типа «Существует ли красный край?», Соответствующих оптимальной оценке. п(п − 1)/2.

(Детерминированный) сложность дерева решений определения свойство графа - количество вопросов вида "Есть ли ребро между вершиной ты и вершина v? ", на которые нужно ответить в худшем случае, чтобы определить, обладает ли граф определенным свойством. То есть это минимальная высота логического Древо решений для проблемы. Есть п(п − 1)/2 возможные вопросы, которые нужно задать. Следовательно, любое свойство графа может быть определено не более чем с п(п − 1)/2 вопросов. Также можно определить сложность случайного и квантового дерева решений свойства, ожидаемое количество вопросов (для входных данных наихудшего случая), на которые должен ответить рандомизированный или квантовый алгоритм, чтобы правильно определить, имеет ли данный граф свойство .[68]

Поскольку свойство содержать клику монотонно, оно покрывается Гипотеза Андераа – Карпа – Розенберга, который утверждает, что сложность детерминированного дерева решений для определения любого нетривиального свойства монотонного графа в точности равна п(п − 1)/2. Для произвольных свойств монотонного графа эта гипотеза остается недоказанной. Однако для детерминированных деревьев решений и для любых k В диапазоне 2 ≤ k ≤ п, свойство содержать k-clique точно имеет сложность дерева решений п(п − 1)/2 к Боллобаш (1976). Детерминированные деревья решений также требуют экспоненциального размера для обнаружения клик или большого полиномиального размера для обнаружения клик ограниченного размера.[69]

Гипотеза Андераа – Карпа – Розенберга также утверждает, что сложность рандомизированного дерева решений для нетривиальных монотонных функций равна Θ (п2). Гипотеза снова остается недоказанной, но была разрешена из-за свойства содержать k клика для 2 ≤ k ≤ п. Известно, что это свойство имеет рандомизированную сложность дерева решений. Θ (п2).[70] Для квантовых деревьев решений наиболее известной нижней оценкой является Ω (п), но алгоритм сопоставления неизвестен для случая k ≥ 3.[71]

Сложность с фиксированными параметрами

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

Для поиска k-vertex cliques, алгоритм поиска грубой силы имеет время выполнения O (пkk2). Поскольку показатель степени п зависит от k, этот алгоритм не является управляемым с фиксированными параметрами. Хотя он может быть улучшен путем быстрого умножения матриц, время выполнения все еще имеет экспоненту, линейную по k Таким образом, хотя время работы известных алгоритмов задачи клики полиномиально для любого фиксированного k, этих алгоритмов недостаточно для управляемости с фиксированными параметрами. Дауни и товарищи (1995) определили иерархию параметризованных задач, иерархию W, которая, по их предположениям, не имела управляемых алгоритмов с фиксированными параметрами. Они доказали, что независимое множество (или, что то же самое, клика) сложно для первого уровня этой иерархии, W [1]. Таким образом, согласно их гипотезе, у clique нет управляемого алгоритма с фиксированными параметрами. Более того, этот результат служит основой для доказательства W [1] -твердости многих других задач и, таким образом, служит аналогом Теорема Кука – Левина для параметризованной сложности.[73]

Chen et al. (2006) показал это открытие k-верхние клики не могут быть выполнены вовремя по(k) если только гипотеза экспоненциального времени терпит неудачу. Опять же, это свидетельствует о том, что никакой управляемый алгоритм с фиксированными параметрами невозможен.[74]

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

Твердость приближения

График отношений совместимости между 2-битными выборками 3-битных строк доказательства. Каждая максимальная клика (треугольник) на этом графике представляет все способы выборки одной 3-битной строки. Доказательство несовместимости проблемы клики включает индуцированные подграфы аналогичным образом определенных графиков для большего числа битов.

Слабые результаты, намекающие на то, что проблему клики может быть трудно аппроксимировать, были известны давно. Гэри и Джонсон (1978) заметил, что из-за того, что кликовое число принимает небольшие целые значения и NP-сложно вычислить, оно не может иметь полностью полиномиальная схема аппроксимации. Если бы было доступно слишком точное приближение, округление его значения до целого числа дало бы точное число клики. Однако мало что было известно до начала 1990-х годов, когда несколько авторов начали устанавливать связи между приближением максимальных клик и вероятностно проверяемые доказательства. Они использовали эти связи, чтобы доказать твердость приближения результаты для задачи о максимальной клике.[75]После многих улучшений этих результатов теперь известно, что для каждого настоящий номер ε > 0, не может быть алгоритма полиномиального времени, который аппроксимирует максимальную клику с точностью до множителя лучше, чем О(п1 − ε), пока не P = NP.[76]

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

Чтобы преобразовать вероятностно проверяемую систему доказательств этого типа в задачу о клике, нужно сформировать граф с вершиной для каждого возможного принимающего прогона средства проверки. То есть вершина определяется одним из возможных случайных выборов наборов позиций для проверки и битовыми значениями для тех позиций, которые заставят контролер принять доказательство. Его можно представить в виде частичное слово с 0 или 1 в каждой исследуемой позиции и подстановочный знак на каждой оставшейся позиции. В этом графе две вершины являются смежными, если соответствующие две принимающие серии видят одинаковые битовые значения в каждой позиции, которую они оба исследуют. Каждая (действительная или недействительная) строка доказательства соответствует клике, набору принимающих прогонов, которые видят эту строку доказательства, и все максимальные клики возникают таким образом. Одна из этих клик велика тогда и только тогда, когда она соответствует строке доказательства, которую принимают многие средства проверки. Если исходный экземпляр выполнимости является выполнимым, он будет иметь действительную строку доказательства, которая будет принята всеми запусками средства проверки, и эта строка будет соответствовать большой клике в графе. Однако, если исходный экземпляр не является выполнимым, тогда все строки доказательства недействительны, каждая строка доказательства имеет только небольшое количество запусков программы проверки, которые ошибочно принимают ее, и все клики небольшие. Следовательно, если бы можно было проводить полиномиальное различие между графами, имеющими большие клики, и графами, в которых все клики малы, или если бы можно было точно аппроксимировать проблему кликов, то применение этого приближения к графам, созданным из экземпляров выполнимости, позволило бы выполнимым экземплярам отличать от неудовлетворительных случаев. Однако это невозможно, если P = NP.[77]

Примечания

  1. ^ а б c Bomze et al. (1999); Гутин (2004).
  2. ^ Вассерман и Фауст (1994).
  3. ^ Колата (1990).
  4. ^ Rhodes et al. (2003).
  5. ^ Куль, Криппен и Фризен (1983).
  6. ^ Комитет Национального исследовательского совета по математическим проблемам вычислительной химии (1995). См. В частности стр. 35–36.
  7. ^ Мегге и Рэри (2001). См. В частности стр. 6–7.
  8. ^ Барроу и Берстолл (1976).
  9. ^ Хамзаоглу и Пател (1998).
  10. ^ Дэй и Санкофф (1986).
  11. ^ Самудрала и линька (1998).
  12. ^ Спирин и Мирный (2003).
  13. ^ Франк и Штраус (1986).
  14. ^ Граф Келлера, используемый Лагариас и Шор (1992) имеет 1048576 вершин и размер клики 1024. Они описали синтетическую конструкцию клики, но также использовали алгоритмы поиска клик на меньших графах, чтобы облегчить поиск. Макки (2002) упростил доказательство, найдя клику размера 256 в графе Келлера с 65536 вершинами.
  15. ^ а б Валиенте (2002); Пелилло (2009).
  16. ^ Пелилло (2009).
  17. ^ Сетураман и Бутенко (2015).
  18. ^ Валиенте (2002).
  19. ^ а б c d Чиба и Нишизеки (1985).
  20. ^ а б Cormen et al. (2001).
  21. ^ Cormen et al. (2001), Упражнение 34-1, стр. 1018.
  22. ^ а б Пападимитриу и Яннакакис (1981); Чиба и Нишизеки (1985).
  23. ^ Гэри, Джонсон и Стокмейер (1976).
  24. ^ См., Например, Франк и Штраус (1986).
  25. ^ Пламмер (1993).
  26. ^ Скиена (2009), п. 526.
  27. ^ Повар (1985).
  28. ^ Например, см. Дауни и товарищи (1995).
  29. ^ Итаи и Родех (1978) предоставить алгоритм с О(м3/2) время выполнения, которое находит треугольник, если он существует, но не перечисляет все треугольники; Чиба и Нишизеки (1985) перечислить все треугольники во времени О(м3/2).
  30. ^ Эйзенбранд и Грандони (2004); Клокс, Крач и Мюллер (2000); Нешетржил и Поляк (1985); Василевская и Уильямс (2009); Юстер (2006).
  31. ^ Томита, Танака и Такахаши (2006).
  32. ^ Казальс и Каранда (2008); Эппштейн, Лёффлер и Страш (2013).
  33. ^ Росген и Стюарт (2007).
  34. ^ а б Эппштейн, Лёффлер и Страш (2013).
  35. ^ Робсон (2001).
  36. ^ Балас и Ю (1986); Карраган и Пардалос (1990); Пардалос и Роджерс (1992); Эстергард (2002); Фахле (2002); Томита и Секи (2003); Томита и Камеда (2007); Конц и Янежич (2007).
  37. ^ Баттити и Протаси (2001); Катаяма, Хамамото и Нарихиса (2005).
  38. ^ Абелло, Пардалос и Ресенде (1999); Гроссо, Локателли и Делла Кроче (2004).
  39. ^ Реген (2003).
  40. ^ Ouyang et al. (1997). Хотя название относится к максимальным кликам, проблема, которую решает эта статья, на самом деле является проблемой максимальной клики.
  41. ^ Чайлдс и др. (2002).
  42. ^ Джонсон и Трик (1996).
  43. ^ Графики вызовов DIMACS для задачи клики В архиве 2018-03-30 в Wayback Machine, дата обращения 17 декабря 2009 г.
  44. ^ Грётшель, Ловас и Шрайвер (1988).
  45. ^ Голумбик (1980).
  46. ^ Голумбик (1980), п. 159.
  47. ^ Эвен, Пнуэли и Лемпель (1972).
  48. ^ Блэр и Пейтон (1993), Лемма 4.5, с. 19.
  49. ^ Гаврил (1973); Голумбик (1980), п. 247.
  50. ^ Кларк, Колборн и Джонсон (1990).
  51. ^ Песня (2015).
  52. ^ Джеррам (1992).
  53. ^ Арора и Барак (2009), Пример 18.2, стр. 362–363.
  54. ^ Алон, Кривелевич и Судаков (1998).
  55. ^ Файги и Краутгеймер (2000).
  56. ^ Мека, Потечин и Вигдерсон (2015).
  57. ^ Боппана и Халльдорссон (1992); Файги (2004); Халльдорссон (2000).
  58. ^ Лю и др. (2015): «Что касается числа вершин в графах, Файги показывает известное на данный момент наилучшее отношение приближения». Лю и др. пишут о максимальный независимый набор но в целях приближения разницы между двумя задачами нет.
  59. ^ Адаптирован из Сипсер (1996)
  60. ^ а б Карп (1972).
  61. ^ Повар (1971).
  62. ^ Повар (1971) дает по существу такое же сокращение от 3-СБ вместо удовлетворенности, чтобы показать, что изоморфизм подграфов является NP-полным.
  63. ^ Липтон и Тарьян (1980).
  64. ^ Импальяццо, Патури и Зейн (2001).
  65. ^ Алон и Боппана (1987). Более ранние и более слабые оценки монотонных схем для проблемы клики см. Доблестный (1983) и Разборов (1985).
  66. ^ Амано и Маруока (2005).
  67. ^ Гольдманн и Хостад (1992) использовал сложность коммуникации чтобы доказать этот результат.
  68. ^ Видеть Арора и Барак (2009), Глава 12, «Деревья решений», стр. 259–269.
  69. ^ Вегенер (1988).
  70. ^ Например, это следует из Грёгер (1992).
  71. ^ Чайлдс и Айзенберг (2005); Магнез, Санта и Сегеди (2007).
  72. ^ Дауни и товарищи (1999). Технически обычно существует дополнительное требование: ж быть вычислимая функция.
  73. ^ Дауни и товарищи (1995).
  74. ^ Chen et al. (2006).
  75. ^ Колата (1990); Feige et al. (1991); Арора и Сафра (1998); Arora et al. (1998).
  76. ^ Хостад (1999) показал неприближаемость для этого отношения, используя более сильное предположение теории сложности, неравенство НП и ЗПП. Хот (2001) описал более точно коэффициент неприближаемости, но с еще более сильным предположением. Цукерман (2006) дерандомизированный конструкция, ослабляющая ее предположение до P ≠ NP.
  77. ^ а б Это сокращение изначально связано с Feige et al. (1991) и используется во всех последующих доказательствах несовместимости; Доказательства различаются по силе и деталям вероятностно проверяемых систем доказательств, на которые они опираются.

Рекомендации

Обзоры и учебники

Популярная пресса

Исследовательские статьи