Это хорошая статья. Для получения дополнительной информации нажмите здесь.
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

История и приложения [ править ]

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

Со времен работы Харари и Росс многие другие разработали алгоритмы для различных версий проблемы клики. [1] В 1970-х годах исследователи начали изучать эти алгоритмы с точки зрения анализа наихудшего случая . См., Например, Tarjan & Trojanowski (1977) , раннюю работу о наихудшем случае сложности задачи о максимальной клике. Также в 1970-х годах, начиная с работ Кука (1971) и Карпа (1972) , исследователи начали использовать теорию NP-полноты и связанные с ней результаты о неразрешимости, чтобы дать математическое объяснение кажущейся сложности проблемы клики. В 90-е годы появилась серия революционных работ, начиная сFeige et al. (1991) и сообщается в The New York Times , [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} .

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

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

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

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

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

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

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

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

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

Клики фиксированного размера [ править ]

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

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

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

Список всех максимальных клик [ править ]

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

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

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

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

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

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

Можно найти максимальную клику или кликовое число произвольного n -вершинного графа за время O (3 n / 3 ) = O (1.4422 n ) , используя один из описанных выше алгоритмов для перечисления всех максимальных клик в график и возвращение самого большого. Однако для этого варианта проблемы клики возможны лучшие временные границы наихудшего случая. Алгоритм Tarjan & Trojanowski (1977) решает эту проблему за время O (2 n / 3 ) = O (1,2599 n ) . Это рекурсивная схема обратного отслеживания, аналогичная алгоритму Брона – Кербоша., но может исключить некоторые рекурсивные вызовы, когда можно показать, что найденные в вызове клики будут неоптимальными. Цзянь (1986) улучшил время до O (2 0,304 n ) = O (1,2346 n ) , а Робсон (1986) улучшил его до O (2 0,276 n ) = O (1,2108 n ) времени за счет большего использования пространства. . Алгоритм Робсона сочетает в себе аналогичную схему поиска с возвратом (с более сложным анализом случаев) и технику динамического программирования , в которой оптимальное решение предварительно вычисляется для всех малых связных подграфов графа.дополнительный граф . Эти частичные решения используются для сокращения рекурсии с возвратом. Самый быстрый алгоритм, известный сегодня, - это усовершенствованная версия этого метода Робсона (2001), работающая за время O (2 0,249 n ) = O (1,1888 n ) . [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 O (log 2 n ) . Это квазиполиномиальная оценка времени . [51] Хотя кликовое число таких графов обычно очень близко к 2 log 2 n , простые жадные алгоритмыа также более сложные методы рандомизированной аппроксимации находят только клики с размером log 2 n , что вдвое меньше. Число максимальных клик в таких графах с высокой вероятностью экспоненциально в log 2 n , что предотвращает выполнение методов, перечисляющих все максимальные клики, за полиномиальное время. [52] Из-за сложности этой проблемы несколько авторов исследовали проблему с установленной кликой, проблему клики на случайных графах, которые были увеличены за счет добавления больших клик. [53] В то время как спектральные методы [54] и полуопределенное программирование [55] могут обнаруживать скрытые клики размераΩ ( √ n ) , в настоящее время не известно ни одного полиномиального алгоритма для обнаружения алгоритмов размера o ( √ n ) (выраженных с использованием маленькой нотации ). [56]

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

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

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

Нижние границы [ править ]

NP-полнота [ править ]

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

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

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

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

Сложность схемы [ править ]

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

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

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

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

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

Поскольку свойство содержать клику является монотонным, оно покрывается гипотезой Андераа – Карпа – Розенберга , которая утверждает, что сложность детерминированного дерева решений для определения любого нетривиального свойства монотонного графа в точности равна n ( n  - 1) / 2 . Для произвольных свойств монотонного графа эта гипотеза остается недоказанной. Тем не менее, для детерминированных деревьев решений, и для любого к в интервале 2 ≤ K ≤ N , свойство , содержащее K -clique было показано, что сложность дерева решений в точности п ( п  - 1) / 2 от Bollobás (1976). Детерминированные деревья решений также требуют экспоненциального размера для обнаружения клик или большого полиномиального размера для обнаружения клик ограниченного размера. [69]

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

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

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

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

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

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

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

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

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

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

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

Заметки [ править ]

  1. ^ а б в Бомзе и др. (1999) ; Гутин (2004) .
  2. ^ Вассерман и Фауст (1994) .
  3. ^ Колата (1990) .
  4. ^ Rhodes et al. (2003) .
  5. ^ Кул, Crippen и Фризен (1983) .
  6. ^ Комитет Национального исследовательского совета по математическим проблемам вычислительной химии (1995) . См., В частности, стр. 35–36 .
  7. ^ Muegge & Rarey (2001) . См., В частности, стр. 6–7 .
  8. ^ Барроу и Берстолл (1976) .
  9. ^ Hamzaoğlu & Patel (1998) .
  10. ^ Дэй и Санкофф (1986) .
  11. ^ Samudrala & Moult (1998) .
  12. ^ Спирин и Мирный (2003) .
  13. ^ Франк и Штраус (1986) .
  14. ^ Граф Келлера, используемый Лагариасом и Шором (1992), имеет 1048576 вершин и размер клики 1024. Они описали синтетическую конструкцию клики, но также использовали алгоритмы поиска клик на меньших графах, чтобы облегчить поиск. Mackey (2002) упростил доказательство, найдя клику размера 256 в графе Келлера с 65536 вершинами.
  15. ^ a b Valiente (2002) ; Пелилло (2009) .
  16. ^ Pelillo (2009) .
  17. ^ Sethuraman и Бутенко (2015) .
  18. ^ Валиент (2002) .
  19. ^ а б в г Chiba & Nishizeki (1985) .
  20. ^ а б Кормен и др. (2001) .
  21. ^ Кормен и др. (2001) , упражнение 34-1, стр. 1018.
  22. ^ a b Пападимитриу и Яннакакис (1981) ; Чиба и Нишизеки (1985) .
  23. ^ Garey, Johnson & Stockmeyer (1976) .
  24. ^ См., Например, Frank & Strauss (1986) .
  25. ^ Пламмер (1993) .
  26. ^ Скиена (2009) , стр. 526 .
  27. ^ Кук (1985) .
  28. ^ Например, см. Downey & Fellows (1995) .
  29. ^ Итаи и Родех (1978) предоставляют алгоритм свременем работы O ( м 3/2 ), который находит треугольник, если он существует, но не перечисляет все треугольники; Chiba & Nishizeki (1985) перечисляют все треугольники во времени O ( м 3/2 ) .
  30. ^ Эйзенбранд и Грандони (2004) ; Kloks, Kratsch & Müller (2000) ; Нешетржил и Поляк (1985) ; Василевская и Вильямс (2009) ; Юстер (2006) .
  31. Перейти ↑ Tomita, Tanaka & Takahashi (2006) .
  32. ^ Cazals & Karande (2008) ; Эппштейн, Лёффлер и Страш (2013) .
  33. ^ Росген и Стюарт (2007) .
  34. ^ а б Эппштейн, Лёффлер и Страш (2013) .
  35. ^ Робсон (2001) .
  36. ^ Балас и Ю (1986) ; Карраган и Пардалос (1990) ; Пардалос и Роджерс (1992) ; Östergård (2002) ; Фахле (2002) ; Томита и Секи (2003) ; Томита и Камеда (2007) ; Конц и Янежич (2007) .
  37. ^ Battiti & Protasi (2001) ; Катаяма, Хамамото и Нарихиса (2005) .
  38. ^ Абелло, Pardalos & Ресенд (1999) ; Гроссо, Локателли и Делла Кроче (2004) .
  39. ^ Регин (2003) .
  40. ^ Ouyang et al. (1997) . Хотя название относится к максимальным кликам, проблема, которую решает эта статья, на самом деле является проблемой максимальной клики.
  41. ^ Чайлдс и др. (2002) .
  42. Перейти ↑ Johnson & Trick (1996) .
  43. ^ Графики вызовов DIMACS для задачи клики Архивировано 30 марта 2018 г. на Wayback Machine ,дата обращения 17 декабря 2009 г.
  44. ^ Grötschel, Ловас & Шриджвер (1988) .
  45. ^ Golumbic (1980) .
  46. ^ Golumbic (1980) , стр. 159.
  47. ↑ Even, Pnueli & Lempel (1972) .
  48. Перейти ↑ Blair & Peyton (1993) , Lemma 4.5, p. 19.
  49. ↑ Гаврил (1973) ; Голумбик (1980) , стр. 247.
  50. ^ Кларк, Колборн и Джонсон (1990) .
  51. ^ Песня (2015) .
  52. ^ Джеррам (1992) .
  53. ↑ Arora & Barak (2009) , Пример 18.2, стр. 362–363.
  54. ↑ Алон, Кривелевич и Судаков (1998) .
  55. ^ Feige & Krauthgamer (2000) .
  56. ^ Мек, Potechin & Wigderson (2015) .
  57. ^ Boppana & Halldórsson (1992) ; Файги (2004) ; Халлдорссон (2000) .
  58. ^ Лю и др. (2015) : «Что касается числа вершин в графах, Файги показывает известное на данный момент наилучшее отношение приближения». Лю и др. пишут о максимальном независимом множестве, но в целях приближения разницы между двумя задачами нет.
  59. ^ Адаптировано из Sipser (1996)
  60. ^ а б Карп (1972) .
  61. ^ Кук (1971) .
  62. ^ Кук (1971) дает по существу такую ​​же редукцию, от 3-SAT вместо Satisfiability, чтобы показать, что изоморфизм подграфов является NP-полным.
  63. ^ Lipton & Тарьян (1980) .
  64. ^ Импальяццо, Патури и Зейн (2001) .
  65. ^ Алон & Boppana (1987) . Более ранние и более слабые оценки монотонных схем для проблемы клики см. В Valiant (1983) и Razborov (1985) .
  66. ↑ Амано и Маруока (2005) .
  67. ^ Goldmann & Håstad (1992) использовали коммуникационную сложность, чтобы доказать этот результат.
  68. ↑ См. Arora & Barak (2009) , глава 12, «Деревья решений», стр. 259–269.
  69. ^ Вегенер (1988) .
  70. ^ Например, это следует из Gröger (1992) .
  71. ^ Чайлдс и Айзенберг (2005) ; Магнез, Санта и Сегеди (2007) .
  72. Перейти ↑ Downey & Fellows (1999) . Технически обычно существует дополнительное требование, чтобы функция f была вычислимой .
  73. Перейти ↑ Downey & Fellows (1995) .
  74. ^ Чен и др. (2006) .
  75. ^ Колата (1990) ; Feige et al. (1991) ; Арора и Сафра (1998) ; Arora et al. (1998) .
  76. ^ Håstad (1999) показал несовместимость этого отношения, используя более сильное теоретическое предположение сложности, неравенство NP и ZPP . Хот ( Khot, 2001) более точно описал коэффициент несовместимости, но с еще более сильным предположением. Цукерман (2006) дерандомизировал конструкцию, ослабив ее предположение до P ≠ NP.
  77. ^ a b Это сокращение первоначально связано с Feige et al. (1991) и использовался во всех последующих доказательствах несовместимости; доказательства различаются по силе и деталям вероятностно проверяемых систем доказательства, на которые они опираются.

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

Обзоры и учебники [ править ]

  • Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Cambridge University Press, ISBN 978-0-521-42426-4.
  • Блэр, Жан Р.С.; Пейтон, Барри (1993), «Введение в хордовые графы и деревья клик», Теория графов и вычисление разреженных матриц , IMA Vol. Математика. . , Appl, 56 ., Springer, Нью - Йорк, стр 1-29, DOI : 10.1007 / 978-1-4613-8369-7_1 , МР  1320296.
  • Бомзе, И.М. Будинич, М .; Пардалос, PM; Пелилло, М. (1999), "Проблема максимальной клики", Справочник по комбинаторной оптимизации , 4 , Kluwer Academic Publishers, стр. 1–74, CiteSeerX  10.1.1.48.4074.
  • Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «34.5.1 Проблема клики», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 1003–1006, ISBN 0-262-03293-7.
  • Дауни, Р.Г.; Стипендиаты, MR (1999), параметризованная сложность , Springer-Verlag , ISBN 0-387-94883-X.
  • Голумбик, MC (1980), алгоритмическая теория графов и совершенные графы , информатика и прикладная математика, Academic Press , ISBN 0-444-51530-5.
  • Grötschel, M .; Ловас, Л .; Schrijver, A. (1988), «9.4 Раскраска идеальных графов», геометрические алгоритмы и комбинаторная оптимизация , алгоритмы и комбинаторика, 2 , Springer-Verlag , стр. 296–298, ISBN 0-387-13624-X.
  • Гутин, Г. (2004), «5.3 Независимые множества и клики», в Gross, JL; Йеллен Дж. (Ред.), Справочник по теории графов , дискретной математике и ее приложениям, CRC Press, стр. 389–402, ISBN 978-1-58488-090-5.
  • Muegge, Ingo; Рэри, Маттиас (2001), «Стыковка и оценка малых молекул», Reviews in Computational Chemistry , 17 : 1–60, doi : 10.1002 / 0471224413.ch1 , ISBN 9780471398455.
  • Комитет Национального исследовательского совета по Математическим вызовам от вычислительной химии (1995), Математические проблемы с теоретического / вычислительной химия , Национальная академия Пресс, DOI : 10,17226 / 4886 , ISBN 978-0-309-05097-5.
  • Пелилло, Марчелло (2009), «Эвристика для максимальной клики и независимого множества», Энциклопедия оптимизации , Springer, стр. 1508–1520, DOI : 10.1007 / 978-0-387-74759-0_264.
  • Пламмер, Майкл Д. (1993), "хорошо укрытые графы: обзор" , Quaestiones Mathematicae , 16 (3): 253-287, DOI : 10,1080 / 16073606.1993.9631737 , MR  1254158.
  • Сипсер, М. (1996), Введение в теорию вычислений , International Thompson Publishing , ISBN 0-534-94728-X.
  • Скиена, Стивен С. (2009), Руководство по разработке алгоритмов (2-е изд.), Springer, ISBN 978-1-84800-070-4.
  • Валиенте, Габриэль (2002), "Глава 6: Clique, независимый набор, и Vertex Cover", Алгоритмы на деревьях и графах , Springer, С. 299-350,. Дои : 10.1007 / 978-3-662-04921-1_6.
  • Вассерман, Стэнли ; Фауст, Кэтрин (1994), Анализ социальных сетей: методы и приложения , структурный анализ в социальных науках, 8 , Cambridge University Press, стр. 276, ISBN 978-0-521-38707-1.

Популярная пресса [ править ]

  • Колата, Джина (26 июня 1990 г.), «В безумии математика входит в эру электронной почты» , The New York Times.

Исследовательские статьи [ править ]

  • Abello, J .; Пардалос, PM; Resende, MGC (1999), "О задачах максимальной клики в очень больших графах" (PDF) , в Abello, J .; Виттер, Дж. (Ред.), Алгоритмы внешней памяти , Серия DIMACS по дискретной математике и теоретической информатике, 50 , Американское математическое общество , стр. 119–130, ISBN 0-8218-1184-3.
  • Алон, Н .; Boppana, Р. (1987), "О монотонной схеме сложности булевых функций", Combinatorica , 7 (1): 1-22, DOI : 10.1007 / BF02579196 , S2CID  17397273.
  • Алон, Н .; Кривелевич, М .; Судаков, В. (1998), "Нахождение большой скрытой верхушку в случайном графе", Случайные структуры и алгоритмы , 13 (3-4): 457-466, DOI : 10.1002 / (SICI) 1098-2418 (199810/12 ) 13: 3/4 <457 :: AID-RSA14> 3.0.CO; 2-W.
  • Алон, Н .; Юстер, Р .; Цвик, У. (1994), "Поиск и подсчет циклов заданной длины", Труды 2-го Европейского симпозиума по алгоритмам, Утрехт, Нидерланды , стр. 354–364..
  • Амано, Казуюки; Маруока, Акира (2005), «Суперполиномиальная нижняя граница для схемы, вычисляющей функцию клики с не более чем (1/6) log log N воротами отрицания», SIAM Journal on Computing , 35 (1): 201–216, doi : 10.1137 / S0097539701396959 , Руководство по ремонту  2178806.
  • Арора, Санджив ; Лунд, Карстен ; Мотвани, Раджив ; Судан, Мадху ; Szegedy, Марио (1998), "Доказательство проверка и твердость задач аппроксимации", Журнал ACM , 45 (3): 501-555, DOI : 10,1145 / 278298,278306 , S2CID  8561542 , ECCC  TR98-008. Первоначально представлен на Симпозиуме по основам компьютерных наук 1992 г. , DOI : 10.1109 / SFCS.1992.267823 .
  • Arora, S .; Сафра, S. (1998), "Вероятностная проверка доказательств: Новая характеристика НП", Журнал ACM , 45 (1): 70-122, DOI : 10,1145 / 273865,273901 , S2CID  751563. Первоначально представлен на Симпозиуме по основам компьютерных наук 1992 г. , DOI : 10.1109 / SFCS.1992.267824 .
  • Balas, E .; Ю, CS (1986), "Нахождение максимальной клики в произвольном графе", SIAM журнал по вычислениям , 15 (4): 1054-1068, DOI : 10,1137 / 0215075.
  • Barrow, H .; Берстолл, Р. (1976), «Изоморфизм подграфов, соответствующие реляционные структуры и максимальные клики», Письма об обработке информации , 4 (4): 83–84, DOI : 10.1016 / 0020-0190 (76) 90049-1.
  • Battiti, R .; Protasi, М. (2001), "Реактивный локальный поиск для максимальной проблемы кликовым", Algorithmica , 29 (4): 610-637, DOI : 10.1007 / s004530010074 , S2CID  1800512.
  • Боллобас, Бела (1976), «Полные подграфы неуловимы», Журнал комбинаторной теории , серия B, 21 (1): 1–7, DOI : 10.1016 / 0095-8956 (76) 90021-6 , ISSN  0095-8956.
  • Boppana, R .; Halldórsson, М. (1992), "Аппроксимация максимальных независимых множеств, исключая подграфы", БИТ вычислительной математики , 32 (2): 180-196, DOI : 10.1007 / BF01994876 , S2CID  123335474.
  • Bron, C .; Kerbosch, J. (1973), "Алгоритм 457: найти все кликами неориентированного графа", коммуникаций ACM , 16 (9): 575-577, DOI : 10,1145 / 362342,362367 , S2CID  13886709.
  • Carraghan, R .; Pardalos, PM (1990), "Точный алгоритм максимальной задачи кликовым", Operations Research Letters , 9 (6): 375-382, DOI : 10.1016 / 0167-6377 (90) 90057-С.
  • Cazals, F .; Karande, C. (2008), "Замечание о проблеме отчетности максимальных клик", теоретическая информатика , 407 (1): 564-568, DOI : 10.1016 / j.tcs.2008.05.010.
  • Чен, Цзианэр; Хуанг, Сючжэнь; Kanj, Iyad A .; Ся, Ге (2006), "Сильные нижние оценки вычислений с помощью параметризованной сложности", Журнал компьютерных и системных наук , 72 (8): 1346–1367, DOI : 10.1016 / j.jcss.2006.04.007
  • Chiba, N .; Nishizeki, Т. (1985), "Arboricity и алгоритмы подграф листинга", SIAM журнал по вычислениям , 14 (1): 210-223, DOI : 10,1137 / 0214017.
  • Чайлдс, AM; Farhi, E .; Голдстоун, Дж . ; Гутманн, С. (2002), «Поиск клик с помощью квантовой адиабатической эволюции», Quantum Information and Computing , 2 (3): 181–191, arXiv : Quant-ph / 0012104 , Bibcode : 2000quant.ph.12104C , doi : 10.26421 /QIC2.3 , S2CID  33643794.
  • Чайлдс, AM; Айзенберг, Дж. М. (2005), «Квантовые алгоритмы для поиска подмножеств», Квантовая информация и вычисления , 5 (7): 593–604, arXiv : Quant-ph / 0311038 , Bibcode : 2003quant.ph.11038C , doi : 10.26421 / QIC5 .7 , S2CID  37556989.
  • Кларк, Брент Н .; Колборн, Чарльз Дж .; Джонсон, Дэвид С. (1990), «Графы единичного диска», Дискретная математика , 86 (1–3): 165–177, DOI : 10.1016 / 0012-365X (90) 90358-O
  • Cook, SA (1971), "Сложность процедур доказательства теорем" , Proc. Третий ACM симпозиум по теории вычислений ., Стр 151-158, DOI : 10,1145 / 800157,805047 , S2CID  7573663.
  • Кук, Стивен А. (1985), «Таксономия проблем с быстрыми параллельными алгоритмами», Информация и управление , 64 (1–3): 2–22, DOI : 10.1016 / S0019-9958 (85) 80041-3 , MR  0837088.
  • День, Уильям HE; Sankoff, Дэвид (1986), "Вычислительная сложность выводя филогенез по совместимости", Систематическая Зоология , 35 (2): 224-229, DOI : 10,2307 / 2413432 , JSTOR  2413432.
  • Дауни, Р.Г.; Стипендиаты, MR (1995), «Последовательность и полнота с фиксированными параметрами. II. О полноте для W [1]», Теоретическая информатика , 141 (1-2): 109-131, DOI : 10.1016 / 0304-3975 (94 ) 00097-3.
  • Eisenbrand, F .; Грандони, Ф. (2004), "О сложности клики с фиксированным параметром и доминирующего множества", Теоретическая информатика , 326 (1–3): 57–67, DOI : 10.1016 / j.tcs.2004.05.009.
  • Эпштейн, Дэвид ; Лёффлер, Маартен; Страш, Даррен (2013), «Перечисление всех максимальных клик в больших разреженных графах реального мира в почти оптимальное время», Журнал экспериментальной алгоритмики , 18 (3): 3.1, arXiv : 1103.0318 , doi : 10.1145 / 2543629 , S2CID  47515491.
  • Эрдеш, Пол ; Секерес, Джордж (1935), "Комбинаторная задача в геометрии" (PDF) , Compositio Mathematica , 2 : 463–470.
  • Даже, С .; Пнуэли, А .; Зива, А. (1972), "Перестановка графики и переходные графики", Журнал ACM , 19 (3): 400-410, DOI : 10,1145 / 321707,321710 , S2CID  9501737.
  • Fahle, T. (2002), "Просто и быстро: улучшение алгоритма ветвей и границ для максимальной клики", Proc. 10-й Европейский симпозиум по алгоритмам , конспект лекций по информатике, 2461 , Springer-Verlag, стр. 47–86, doi : 10.1007 / 3-540-45749-6_44 , ISBN 978-3-540-44180-9.
  • Фейга, У. (2004), "Аппроксимация максимальной клики пути удаления подграфов", SIAM журнал по дискретной математике , 18 (2): 219-225, DOI : 10,1137 / S089548010240415X.
  • Feige, U .; Goldwasser, S .; Ловас, Л .; Safra, S ; Сегеди, М. (1991), "Приближающая клика почти NP-полна", Proc. 32-й симпозиум IEEE. по основам информатики , стр. 2–12, DOI : 10.1109 / SFCS.1991.185341 , ISBN 0-8186-2445-0, S2CID  46605913.
  • 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.
  • Фрэнк, Уве; Strauss, Дэвид (1986), "Марковские графы", журнал Американской ассоциации по статистике , 81 (395): 832-842, DOI : 10,2307 / 2289017 , JSTOR  2289017 , MR  0860518.
  • Garey, MR ; Джонсон, DS (1978), " " Сильные "NP-полнота результатов: мотивация, примеры и последствия", Журнал ACM , 25 (3): 499-508, DOI : 10,1145 / 322077,322090 , S2CID  18371269.
  • Garey, MR ; Джонсон, DS ; Стокмайер, Л. (1976), "Некоторые упрощенные NP-полные задачи графа", Теоретическая информатика , 1 (3): 237-267, DOI : 10,1016 / 0304-3975 (76) 90059-1 , МР  0411240.
  • Гаврил, Ф. (1973), «Алгоритмы для максимальной клики и максимального независимого набора кругового графа», Сети , 3 (3): 261–273, DOI : 10.1002 / net.3230030305.
  • Goldmann, M .; Хастад, Дж. (1992), «Простая нижняя оценка монотонной клики с использованием коммуникационной игры» (PDF) , Письма об обработке информации , 41 (4): 221–226, CiteSeerX  10.1.1.185.3065 , doi : 10.1016 / 0020 -0190 (92) 90184-В.
  • Groger, Ханс Дитмар (1992), "О рандомизированной сложности свойств графа монотонных" (PDF) , Acta Cybernetica , 10 (3): 119-127 , извлекаются 2009-10-02
  • Grosso, A .; Locatelli, M .; Делла Кроче, Ф. (2004 г.), «Объединение свопов и весов узлов в адаптивном жадном подходе к проблеме максимальной клики», Journal of Heuristics , 10 (2): 135–152, doi : 10.1023 / B: HEUR.0000026264.51747. 7f , S2CID  40764225.
  • Халлдорссон, М.М. (2000), «Аппроксимация взвешенных независимых множеств и проблем наследственного подмножества», Журнал графовых алгоритмов и приложений , 4 (1): 1–16, doi : 10.7155 / jgaa.00020.
  • Hamzaoglu, I .; Патель, Дж. Х. (1998), "Алгоритмы уплотнения тестового набора для комбинационных схем", Proc. 1998 IEEE / ACM Международная конференция по Computer-Aided Design , стр 283-289,. DOI : 10.1145 / 288548.288615 , S2CID  12258606.
  • Harary, F .; Росс, ИК (1957), "Процедура для обнаружения кликовым с использованием матрицы группы", Социометрия , Американская социологическая ассоциация, 20 (3): 205-215, DOI : 10,2307 / 2785673 , JSTOR  2785673 , МР  0110590.
  • Håstad, J. (1999), "Клика трудно аппроксимировать в пределах п 1 - е ", Acta Mathematica , 182 (1): 105-142, DOI : 10.1007 / BF02392825.
  • Impagliazzo, R .; Paturi, R .; Зейн, F. (2001), "Какие проблемы имеют сильно экспоненциальную сложность?", Журнал компьютерных и системных наук , 63 (4): 512-530, DOI : 10,1006 / jcss.2001.1774.
  • Itai, A .; Rodeh, М. (1978), "Нахождение минимальной цепи в графе", SIAM журнал по вычислениям , 7 (4): 413-423, DOI : 10,1137 / 0207033.
  • Jerrum, М. (1992), "Большие клики ускользать от процесса Метрополис", случайных структур и алгоритмов , 3 (4): 347-359, DOI : 10.1002 / rsa.3240030402.
  • Цзянь, Т. (1986), « Алгоритм O (2 0,304 n ) для решения задачи о максимальном независимом множестве», IEEE Transactions on Computers , IEEE Computer Society, 35 (9): 847–851, doi : 10.1109 / TC.1986.1676847 , ISSN  0018-9340.
  • Джонсон, DS ; Уловка, Массачусетс , ред. (1996), Клики, раскраска и выполнимость: вторая задача реализации DIMACS, 11–13 октября 1993 г. , Серия DIMACS по дискретной математике и теоретической информатике, 26 , Американское математическое общество , ISBN 0-8218-6609-5.
  • Джонсон, DS ; Яннакакис, М. (1988), «О создании всех максимальных независимых множеств», Письма об обработке информации , 27 (3): 119–123, DOI : 10.1016 / 0020-0190 (88) 90065-8.
  • Карп, Ричард М. (1972), «Сводимость комбинаторных задач», Миллер, RE; Тэтчер, Дж. У. (ред.), Сложность компьютерных вычислений (PDF) , Нью-Йорк: Пленум , стр. 85–103..
  • Карп, Ричард М. (1976), «Вероятностный анализ некоторых комбинаторных задач поиска», в Траубе, Дж. Ф. (ред.), Алгоритмы и сложность: новые направления и недавние результаты , Нью-Йорк: Academic Press , стр. 1–19..
  • Katayama, K .; Хамамото, А .; Narihisa, H. (2005), "Эффективный локальный поиск для максимальной проблемы клики", Information Processing Letters , 95 (5): 503-511, DOI : 10.1016 / j.ipl.2005.05.010.
  • Khot, S. (2001), "Улучшенные результаты неапроксимируемости для MaxClique, хроматического числа и приближенной окраски графа", Proc. 42-й симпозиум IEEE. Основы компьютерных наук , стр. 600–609, DOI : 10.1109 / SFCS.2001.959936 , ISBN 0-7695-1116-3, S2CID  11987483.
  • Клокс, Т .; Kratsch, D .; Мюллер, Х. (2000), «Эффективный поиск и подсчет малых индуцированных подграфов», Письма об обработке информации , 74 (3–4): 115–121, DOI : 10.1016 / S0020-0190 (00) 00047-8.
  • Konc, J .; Янежич, Д. (2007), "Улучшенный алгоритм ветвей и границ для задачи о максимальной клике" (PDF) , MATCH Communications in Mathematical and Computer Chemistry , 58 (3): 569–590. Исходный код
  • Kuhl, FS; Криппен, GM; Фризен, ДК (1983), "Комбинаторный алгоритм вычисления связывания лиганда", Журнал вычислительной химии , 5 (1): 24-34, DOI : 10.1002 / jcc.540050105.
  • Лагариас, Джеффри К .; Шор, Питер У. (1992), «Гипотеза Келлера о разбиении куба неверна в больших измерениях», Бюллетень Американского математического общества , Новая серия, 27 (2): 279–283, arXiv : math / 9210222 , doi : 10.1090 / S0273-0979-1992-00318-X , Руководство по ремонту  1155280 , S2CID  6390600.
  • Lipton, RJ ; Тарьян, RE (1980), "Применение плоский разделитель теорема", SIAM журнал по вычислениям , 9 (3): 615-627, DOI : 10,1137 / 0209046 , S2CID  12961628.
  • Лю, Ю; Лу, Цзяхэн; Ян, Хуа; Сяо, Сяокуй; Wei, Zhewei (2015), «К максимальным независимым множествам на массивных графах», Труды 41-й Международной конференции по очень большим базам данных (VLDB 2015) , Proceedings of the VLDB Endowment, 8 , pp. 2122–2133, doi : 10.14778 /2831360.2831366 , ЛВП : 10138/157292.
  • Люс, Р. Дункан ; Перри, Альберт Д. (1949), "Метод матричного анализа структуры группы", Psychometrika , 14 (2): 95-116, DOI : 10.1007 / BF02289146 , ЛВП : 10.1007 / BF02289146 , PMID  18152948 , S2CID  16186758.
  • Макки, Джон (2002), "Куб черепицей размерности восемь, без facesharing", Дискретная и вычислительная геометрия , 28 (2): 275-279, DOI : 10.1007 / s00454-002-2801-9 , MR  1920144.
  • Магнье, Фредерик; Сантха, Миклош; Сегеди, Марио (2007), «Квантовые алгоритмы для проблемы треугольника», SIAM Journal on Computing , 37 (2): 413–424, arXiv : Quant-ph / 0310134 , doi : 10,1137 / 050643684 , S2CID  594494.
  • Макино, К .; Уно, Т. (2004), «Новые алгоритмы для перечисления всех максимальных клик», Теория алгоритмов: SWAT 2004 (PDF) , Lecture Notes in Computer Science, 3111 , Springer-Verlag , стр. 260–272, CiteSeerX  10.1.1.138. 705 , DOI : 10.1007 / 978-3-540-27810-8_23.
  • Мека, Рагху; Потечин, Аарон; Вигдерсон, Ави (2015), «Нижние границы суммы квадратов для установленной клики», Труды сорок седьмого ежегодного симпозиума ACM по теории вычислений (STOC '15) , Нью-Йорк, Нью-Йорк, США: ACM, стр. . 87-96, Arxiv : 1503,06447 , DOI : 10,1145 / 2746539,2746600 , ISBN 978-1-4503-3536-2, S2CID  2754095.
  • Луна, JW; Мозер, Л. (1965), «О кликах в графах», Израильский математический журнал , 3 : 23–28, DOI : 10.1007 / BF02760024 , MR  0182577 , S2CID  9855414.
  • Nešetřil, J .; Поляк, С. (1985), "О сложности проблемы подграфа", Commentationes Mathematicae Universitatis Carolinae , 26 (2): 415–419.
  • Östergård, PRJ (2002), "Быстрый алгоритм для максимальной задачи клики", Discrete Applied Mathematics , 120 (1-3): 197-207, DOI : 10.1016 / S0166-218X (01) 00290-6.
  • Ouyang, Q .; Каплан, PD; Liu, S .; Libchaber, A. (1997), "ДНК решение задачи кликовым максимальной", Science , 278 (5337): 446-449, Bibcode : 1997Sci ... 278..446O , DOI : 10.1126 / science.278.5337.446 , PMID  9334300.
  • Пападимитриу, Христос Х .; Яннакакис, Михалис (1981), "Проблема клики для плоских графов", Письма об обработке информации , 13 (4–5): 131–133, DOI : 10.1016 / 0020-0190 (81) 90041-7 , MR  0651460.
  • Пардалос, PM; Роджерс, Г. П. (1992), "Ветка и связанный алгоритм для задачи максимальной клики", Компьютеры и исследование операций , 19 (5): 363-375, DOI : 10,1016 / 0305-0548 (92) 90067-F.
  • Разборов А.А. (1985), "Нижние оценки монотонной сложности некоторых булевых функций", Труды АН СССР , 281 : 798–801. Английский перевод в сов. Математика. Докл. 31 (1985): 354–357..
  • Реген, Ж.-К. (2003), "Использование программирования с ограничениями для решения задачи о максимальной клике", Proc. 9-е межд. Конф. Принципы и практика программирования с ограничениями - CP 2003 , Lecture Notes in Computer Science, 2833 , Springer-Verlag , pp. 634–648, doi : 10.1007 / 978-3-540-45193-8_43.
  • Родос, Николас; Уиллетт, Питер; Кальве, Ален; Данбар, Джеймс Б.; Humblet, Christine (2003), "CLIP: сходство поиск 3D - баз данных с использованием функции обнаружения клике", Журнал химической информации и компьютерных наук , 43 (2): 443-448, DOI : 10.1021 / ci025605o , PMID  12653507.
  • Robson, JM (1986), "Алгоритмы для максимальных независимых множеств", журнал алгоритмов , 7 (3): 425-440, DOI : 10,1016 / 0196-6774 (86) 90032-5.
  • Робсон, Дж. М. (2001), Нахождение максимального независимого множества за время O (2 n / 4 ).
  • Росген, Б; Стюарт, Л. (2007), «Результаты о сложности на графах с несколькими кликами» , Дискретная математика и теоретическая информатика , 9 (1): 127–136.
  • Самудрала, Рам; Линька, Джон (1998), "Граф теоретико-алгоритм для сравнительного моделирования структуры белка", Журнал молекулярной биологии , 279 (1): 287-302, DOI : 10,1006 / jmbi.1998.1689 , PMID  9636717.
  • Сетураман, Самьюкта; Бутенко, Сергий (2015), "Максимальное отношение проблема клики", Вычислительная Наука управления , 12 (1): 197-218, DOI : 10.1007 / s10287-013-0197-г , МР  3296231 , S2CID  46153055.
  • Песня, Y. (2015), "О независимом множестве в случайных графов" , Международный журнал вычислительной математики , 92 (11): 2233-2242, DOI : 10,1080 / 00207160.2014.976210 , S2CID  6713201.
  • Спирин, Виктор; Мирный, Леонид А. (2003), «Белковые комплексы и функциональные модули в молекулярных сетях», Труды Национальной академии наук , 100 (21): 12123–12128, Bibcode : 2003PNAS..10012123S , doi : 10.1073 / pnas. 2032324100 , PMC  218723 , PMID  14517352.
  • Tarjan, RE ; Трояновский, AE (1977), "Нахождение максимального независимого множества" (PDF) , SIAM журнал по вычислениям , 6 (3): 537-546, DOI : 10,1137 / 0206038.
  • Tomita, E .; Kameda, Т. (2007), «Эффективные ветви и границ алгоритм нахождения максимальной верхушки с вычислительными экспериментами», журнал глобальной оптимизации , 37 (1): 95-111, DOI : 10.1007 / s10898-006-9039 -7 , S2CID  21436014.
  • Tomita, E .; Секи, Т. (2003), «Эффективный алгоритм ветвей и границ для поиска максимальной клики» , Дискретная математика и теоретическая информатика , Lecture Notes in Computer Science, 2731 , Springer-Verlag, pp.  278–289 , doi : 10.1007 / 3-540-45066-1_22 , ISBN 978-3-540-40505-4.
  • Tomita, E .; Tanaka, A .; Такахаши, Х. (2006), «Наихудшая временная сложность для генерации всех максимальных клик и вычислительных экспериментов», Теоретическая информатика , 363 (1): 28–42, doi : 10.1016 / j.tcs.2006.06.015.
  • Tsukiyama, S .; Ide, M .; Ariyoshi, I .; Сиракава, И. (1977), «Новый алгоритм для генерации всех максимальных независимых множеств», SIAM Journal on Computing , 6 (3): 505–517, doi : 10,1137 / 0206036.
  • Valiant, LG (1983), "Экспоненциальные нижние оценки для ограниченных монотонных схем", Proc. Пятнадцатый ACM симпозиум по теории вычислений ., Стр 110-117, DOI : 10,1145 / 800061,808739 , ISBN 0-89791-099-0, S2CID  6326587.
  • Василевская, В .; Уильямс, Р. (2009), "Поиск, минимизация и подсчет взвешенных подграфов", Proc. Сорок первый ACM симпозиум по теории вычислений ., С. 455-464, CiteSeerX  10.1.1.156.345 , DOI : 10,1145 / 1536414,1536477 , ISBN 978-1-60558-506-2, S2CID  224579.
  • Вегенера, И. (1988), "О сложности ветвящихся программ и дерева решений для функций клики", Журнал ACM , 35 (2): 461-472, DOI : 10,1145 / 42282,46161 , S2CID  11967153.
  • Юстер, Р. (2006), "Поиск и подсчет клик и независимых множеств в r -однородных гиперграфах", Письма об обработке информации , 99 (4): 130–134, DOI : 10.1016 / j.ipl.2006.04.005.
  • Цукерман, Д. (2006), "Линейные экстракторы степени и непроксимируемость максимальной клики и хроматического числа", Proc. 38-й симпозиум ACM. Теория вычислений . С. 681-690, DOI : 10,1145 / 1132516,1132612 , ISBN 1-59593-134-1, S2CID  5713815 , ECCC  TR05-100.