Проблема с щелчком

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

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

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

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

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

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

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

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

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

При автоматической генерации тестовых шаблонов поиск клик может помочь ограничить размер тестового набора. В биоинформатике алгоритмы поиска клик использовались для построения эволюционных деревьев . предсказывать белковые структуры , и найти тесно взаимодействующие кластеры белков. Составление списка клик на графе зависимостей — важный шаг в анализе некоторых случайных процессов. В математике гипотеза Келлера лицом к лицу о мозаике гиперкубов была опровергнута Лагариасом и Шором (1992) , которые использовали алгоритм поиска клик на связанном графе, чтобы найти контрпример.

Определения

Основная статья: Клика (теория графов)

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

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

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

• В задаче о максимальной клике входными данными является неориентированный граф, а выходными данными — максимальная клика в графе. Если существует несколько максимальных клик, одна из них может быть выбрана произвольно.
• В задаче о взвешенной максимальной клике входными данными является неориентированный граф с весами на вершинах (или, реже, ребрах), а выходными данными является клика с максимальным общим весом. Задача о максимальной клике — это частный случай, когда все веса равны. Помимо задачи оптимизации суммы весов, изучались и другие, более сложные задачи бикритериальной оптимизации.
• В задаче о перечислении максимальных клик входными данными является неориентированный граф, а выходными данными — список всех его максимальных клик. Задачу о максимальной клике можно решить, используя в качестве подпрограммы алгоритм задачи о перечислении максимальной клики, поскольку максимальная клика должна быть включена среди всех максимальных клик.
• В задаче k -клики входными данными являются неориентированный граф и число k . Результатом является клика с k -клики не существует вершинами, если таковая существует, или специальное значение, указывающее, что в противном случае k . В некоторых вариантах этой задачи в выходных данных должны быть перечислены все клики размера k .
• В задаче решения клики входными данными являются неориентированный граф и число k , а выходными данными является логическое значение : true, если граф содержит k -клику, и false в противном случае.

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

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

Алгоритмы

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

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

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

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

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

Самый простой нетривиальный случай задачи поиска клики — это поиск треугольника в графе или, что то же самое, определение того, является ли граф свободным от треугольников .В графе G с m ребрами может быть не более Θ( m ^3/2 ) треугольники (с использованием обозначения большой тета, чтобы указать, что эта граница точна). Наихудший случай для этой формулы возникает, когда G сама является кликой. Следовательно, алгоритмы перечисления всех треугольников должны брать не менее Ω( m ^3/2 ) время в худшем случае (с использованием обозначения большой омеги ), и известны алгоритмы, соответствующие этому времени. Например, Чиба и Нишизеки (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 ) , что является оптимальным, поскольку он линейен по размеру входных данных.

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

Перечисление всех максимальных клик

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

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

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

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

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

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

Можно найти максимальную клику или число кликов произвольного графа из n вершин за время O (3 ^{н /3} ) = О (1,4422 ^н ), используя один из описанных выше алгоритмов для перечисления всех максимальных клик в графе и возврата самой большой из них. Однако для этого варианта задачи о клике возможны лучшие временные рамки для наихудшего случая. Алгоритм Тарьяна и Трояновского (1977) решает эту проблему за время O (2 ^{н /3} ) = О (1,2599 ^н ) . Это рекурсивная схема поиска с возвратом, аналогичная схеме алгоритма Брона-Кербоша , но способная исключить некоторые рекурсивные вызовы, когда можно показать, что клики, найденные в вызове, будут неоптимальными. Цзянь (1986) улучшил время до О (2 ^{0,304 н} ) = О (1,2346 ^н ) , а Робсон (1986) улучшил его до O (2 ^{0,276 н} ) = О (1,2108 ^н ) времени за счет большего использования пространства. Алгоритм Робсона сочетает в себе аналогичную схему обратного отслеживания (с более сложным анализом случаев) и технику динамического программирования , в которой оптимальное решение предварительно вычисляется для всех небольших связных подграфов графа дополнения . Эти частичные решения используются для сокращения рекурсии обратного отслеживания. Самый быстрый алгоритм, известный сегодня, — это усовершенствованная версия этого метода Робсона (2001), которая работает за время O (2 ^{0,249 н} ) = О (1,1888 ^н ) .

Также были проведены обширные исследования эвристических алгоритмов для решения задач с максимальной кликой без гарантий времени выполнения наихудшего случая, основанные на методах, включая ветвления и границы . локальный поиск , жадные алгоритмы , и программирование ограничений . Нестандартные вычислительные методы, предложенные для поиска клик, включают вычисления на ДНК. и адиабатические квантовые вычисления . Проблема максимальной клики была предметом задачи по реализации, спонсируемой DIMACS в 1992–1993 годах. и общедоступный набор графиков, используемых в качестве ориентиров для решения задачи.

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

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

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

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

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

Случайный граф с посаженной кликой

Алгоритмическая задача поиска максимальной клики в случайном графе, построенном на основе модели Эрдеша-Реньи (в которой каждое ребро появляется с вероятностью 1/2 независимо от других ребер), была предложена Карпом (1976) . Поскольку максимальная клика в случайном графе с высокой вероятностью имеет логарифмический размер, онаможно найти методом перебора за ожидаемое время 2 ^{О (лог. 2 п )} . Это квазиполиномиальное ограничение по времени. Хотя число клик в таких графах обычно очень близко к 2 log ₂ n , простые жадные алгоритмы , а также более сложные методы рандомизированной аппроксимации находят только клики с размером log ₂ n , что вдвое меньше. Число максимальных клик в таких графах с высокой вероятностью экспоненциально в log ² n , что предотвращает выполнение методов, перечисляющих все максимальные клики, за полиномиальное время. Из-за сложности этой проблемы несколько авторов исследовали проблему установленной клики , проблему клики на случайных графах, которые были дополнены добавлением больших клик. Хотя спектральные методы и полуопределенное программирование могут обнаруживать скрытые клики размера Ω( √ n ) , в настоящее время не известны алгоритмы с полиномиальным временем для обнаружения клик размера o ( √ n ) (выраженные с использованием обозначения Little-o ).

Алгоритмы аппроксимации

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

Файги (2004) описывает алгоритм с полиномиальным временем, который находит клику размера Ω((log n /log log n ) ² ) в любом графе, имеющем кликовое число Ω( n /log ^к n ) для любой константы k . Используя этот алгоритм, когда число клик данного входного графа находится между n /log n и n /log ³ n , переключаясь на другой алгоритм Боппаны и Халлдорссона (1992) для графов с более высоким числом клик и выбирая клику с двумя вершинами, если оба алгоритма ничего не могут найти, Файги предлагает аппроксимационный алгоритм, который находит клику с большим количеством вершин. в пределах O( n (log log n ) ² /бревно ³ n ) максимума. Хотя степень аппроксимации этого алгоритма слабая, на сегодняшний день он является наиболее известным. Описанные ниже результаты по твердости аппроксимации позволяют предположить, что не может быть алгоритма аппроксимации со степенью аппроксимации, значительно меньшей линейной.

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

NP-полнота

Пример выполнимости 3-КНФ (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y), сведенный к клике. Зеленые вершины образуют 3-клику и соответствуют удовлетворяющему заданию.

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

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

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

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

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

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

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

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

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

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

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

Неразрешимость с фиксированными параметрами

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

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

Чен и др. (2006) показали, что найти клики с k -вершинами невозможно за время n ^{хорошо ​ ) ​} если только гипотеза экспоненциального времени не подтвердится. Опять же, это доказывает, что никакой управляемый алгоритм с фиксированными параметрами невозможен.

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

Твердость аппроксимации

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

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

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

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

Ссылки

Опросы и учебники

• Арора, Санджив ; Барак, Боаз (2009), Сложность вычислений: современный подход , Издательство Кембриджского университета, ISBN  978-0-521-42426-4 .
• Блэр, Джин Р.С.; Пейтон, Барри (1993), «Введение в хордальные графы и деревья клик», Теория графов и вычисление разреженных матриц , IMA Vol. Математика. Приложение, вып. 56, Спрингер, Нью-Йорк, стр. 1–29, номер номера : 10.1007/978-1-4613-8369-7_1 , MR   1320296 .
• Бомзе, ИМ; Будинич, М.; Пардалос, премьер-министр; Пелилло, М. (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-Х .
• Голумбик, MC (1980), Алгоритмическая теория графов и совершенные графы , информатика и прикладная математика, Academic Press , ISBN  0-444-51530-5 .
• Гретшель, М .; Ловас, Л. ; Шрийвер, А. (1988), «9.4 Раскраска совершенных графов», Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2, Springer-Verlag , стр. 296–298, ISBN.  0-387-13624-Х .
• Гутин Г. (2004), «5.3 Независимые множества и клики», Гросс, Дж. Л.; Йеллен Дж. (ред.), Справочник по теории графов , Дискретная математика и ее приложения, CRC Press, стр. 389–402, ISBN  978-1-58488-090-5 .
• Мюгге, Инго; Рэри, Матиас (2001), «Стыковка и оценка малых молекул», Обзоры по вычислительной химии , 17 : 1–60, doi : 10.1002/0471224413.ch1 , ISBN  9780471398455 .
• Комитет Национального исследовательского совета по математическим задачам вычислительной химии (1995), Математические задачи теоретической/вычислительной химии , National Academies Press, 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 , заархивировано из оригинала 27 мая, 2012 .
• Сипсер, М. (1996), Введение в теорию вычислений , International Thompson Publishing , ISBN  0-534-94728-Х .
• Скиена, Стивен С. (2009), Руководство по разработке алгоритмов (2-е изд.), Springer, ISBN  978-1-84800-070-4 .
• Валиенте, Габриэль (2002), «Глава 6: Клика, независимый набор и вершинное покрытие», Алгоритмы на деревьях и графах , Springer, стр. 299–350, doi : 10.1007/978-3-662-04921-1_6 , S2CID   118777692 .
• Вассерман, Стэнли ; Фауст, Кэтрин (1994), Анализ социальных сетей: методы и приложения , Структурный анализ в социальных науках, том. 8, Издательство Кембриджского университета, с. 276, ISBN  978-0-521-38707-1 .

Научные статьи

• Абелло, Дж.; Пардалос, премьер-министр; Ресенде, MGC (1999), «О задачах максимальной клики в очень больших графах» (PDF) , в Абелло, Дж.; Виттер Дж. (ред.), Алгоритмы внешней памяти , Серия DIMACS по дискретной математике и теоретической информатике, том. 50, Американское математическое общество , стр. 119–130, ISBN.  0-8218-1184-3 , заархивировано из оригинала (PDF) 16 января 2017 г. , получено 13 января 2017 г.
• Алон, Н. ; Боппана, Р. (1987), «Монотонная сложность схемы булевых функций», Combinatorica , 7 (1): 1–22, doi : 10.1007/BF02579196 , S2CID   17397273 .
• Алон, Н. ; Кривелевич, М.; Судаков, Б. (1998), «Нахождение большой скрытой клики в случайном графе», Random Structures & Algorithms , 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 .
• Арора, Санджив ; Лунд, Карстен ; Мотвани, Раджив ; Судан, Мадху ; Сегеди, Марио (1998), «Проверка доказательств и сложность задач аппроксимации», Журнал ACM , 45 (3): 501–555, doi : 10.1145/278298.278306 , S2CID   8561542 , ECCC   TR98-008 . Первоначально представлено на Симпозиуме по основам информатики в 1992 году . дои : 10.1109/SFCS.1992.267823 .
• Арора, С. ; Сафра, С. (1998), «Вероятностная проверка доказательств: новая характеристика NP», Журнал ACM , 45 (1): 70–122, doi : 10.1145/273865.273901 , S2CID   751563 . Первоначально представлено на Симпозиуме по основам информатики в 1992 году . дои : 10.1109/SFCS.1992.267824 .
• Балас, Э.; Ю, К.С. (1986), «Нахождение максимальной клики в произвольном графе», SIAM Journal on Computing , 15 (4): 1054–1068, doi : 10.1137/0215075 .
• Барроу, Х.; Берстолл, Р. (1976), «Изоморфизм подграфов, сопоставление реляционных структур и максимальных клик», Information Processing Letters , 4 (4): 83–84, doi : 10.1016/0020-0190(76)90049-1 .
• Баттити, Р.; Протаси, М. (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 .
• Боппана, Р.; Халлдорссон, М.М. (1992), «Аппроксимация максимальных независимых наборов путем исключения подграфов», BIT Numerical Mathematics , 32 (2): 180–196, doi : 10.1007/BF01994876 , S2CID   123335474 .
• Брон, К.; Кербош, Дж. (1973), «Алгоритм 457: поиск всех клик неориентированного графа», Communications of the ACM , 16 (9): 575–577, doi : 10.1145/362342.362367 , S2CID   13886709 .
• Карраган, Р.; Пардалос, П.М. (1990), «Точный алгоритм для задачи максимальной клики», Operations Research Letters , 9 (6): 375–382, doi : 10.1016/0167-6377(90)90057-C .
• Казальс, Ф.; Каранде, К. (2008), «Заметка о проблеме сообщения о максимальных кликах», Theoretical Computer Science , 407 (1): 564–568, doi : 10.1016/j.tcs.2008.05.010 .
• Чен, Цзянер; Хуан, Сючжэнь; Кандж, Ияд А.; Ся, Ге (2006), «Сильные вычислительные нижние границы посредством параметризованной сложности», Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
• Чиба, Н.; Нишизеки, Т. (1985), «Древовидность и алгоритмы перечисления подграфов», SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017 , S2CID   207051803 .
• Чайлдс, AM; Фархи, Э.; Голдстоун, Дж .; Гутманн, С. (2002), «Нахождение клик с помощью квантовой адиабатической эволюции», Quantum Information and Computation , 2 (3): 181–191, arXiv : quant-ph/0012104 , Bibcode : 2000quant.ph.12104C , doi : 10.26421 /QIC2.3 , S2CID   33643794 .
• Чайлдс, AM; Айзенберг, Дж. М. (2005), «Квантовые алгоритмы для поиска подмножества», Quantum Information and Computation , 5 (7): 593–604, arXiv : quant-ph/0311038 , Bibcode : 2003quant.ph.11038C , doi : 10.26421/QIC5 .7 , S2CID   37556989 .
• Кларк, Брент Н.; Колборн, Чарльз Дж .; Джонсон, Дэвид С. (1990), «Графы единичных дисков», Discrete Mathematics , 86 (1–3): 165–177, doi : 10.1016/0012-365X(90)90358-O
• Кук, С.А. (1971), "Сложность процедур доказательства теорем" , Proc. 3-й симпозиум ACM по теории вычислений , стр. 151–158, doi : 10.1145/800157.805047 , S2CID   7573663 .
• Кук, Стивен А. (1985), «Таксономия проблем с быстрыми параллельными алгоритмами», Information and Control , 64 (1–3): 2–22, doi : 10.1016/S0019-9958(85)80041-3 , MR   0837088 .
• Дэй, Уильям Х.Э.; Санкофф, Дэвид (1986), «Вычислительная сложность определения филогении по совместимости», Systematic Zoology , 35 (2): 224–229, doi : 10.2307/2413432 , JSTOR   2413432 .
• Дауни, Р.Г.; Fellows, MR (1995), «Управляемость и полнота с фиксированными параметрами. II. О полноте для W[1]», Theoretical Computer Science , 141 (1–2): 109–131, doi : 10.1016/0304-3975 (94 )00097-3 .
• Эйзенбранд, Ф.; Грандони, Ф. (2004), «О сложности клики с фиксированными параметрами и доминирующего множества», Theoretical Computer Science , 326 (1–3): 57–67, doi : 10.1016/j.tcs.2004.05.009 .
• Эппштейн, Дэвид ; Леффлер, Мартен; Страш, Даррен (2013), «Перечисление всех максимальных клик в больших разреженных графах реального мира за почти оптимальное время», Journal of Experimental Algorithmics , 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 .
• Фале, Т. (2002), «Просто и быстро: улучшение алгоритма ветвей и границ для максимальной клики», Proc. 10-й Европейский симпозиум по алгоритмам , Конспекты лекций по информатике, том. 2461, Springer-Verlag, стр. 47–86, номер документа : 10.1007/3-540-45749-6_44 , ISBN.  978-3-540-44180-9 .
• Файги, У. (2004), «Аппроксимация максимальной клики путем удаления подграфов», SIAM Journal on Discrete Mathematics , 18 (2): 219–225, doi : 10.1137/S089548010240415X .
• Файги, Ю. ; Гольдвассер, С .; Ловас, Л. ; Сафра, С ; Сегеди, М. (1991), «Аппроксимирующая клика почти NP-полна», [1991] Труды 32-го ежегодного симпозиума по основам информатики , стр. 2–12, doi : 10.1109/SFCS.1991.185341 , ISBN  0-8186-2445-0 , S2CID   46605913 .
• Файги, Ю. ; Краутгеймер, Р. (2000), «Обнаружение и сертификация большой скрытой клики в полуслучайном графе», Случайные структуры и алгоритмы , 16 (2): 195–208, doi : 10.1002/(SICI)1098-2418(200003)16 :2<195::AID-RSA5>3.0.CO;2-A .
• Франк, Уве; Штраус, Дэвид (1986), «Марковские графики», Журнал Американской статистической ассоциации , 81 (395): 832–842, doi : 10.2307/2289017 , JSTOR   2289017 , MR   0860518 .
• Гэри, MR ; Джонсон, Д.С. (1978), « Результаты «сильной» NP-полноты: мотивация, примеры и последствия», Journal of the ACM , 25 (3): 499–508, doi : 10.1145/322077.322090 , S2CID   18371269 .
• Гэри, MR ; Джонсон, Д.С .; Стокмейер, Л. (1976), «Некоторые упрощенные NP-полные задачи на графах», Theoretical Computer Science , 1 (3): 237–267, doi : 10.1016/0304-3975(76)90059-1 , MR   0411240 .
• Гаврил Ф. (1973), «Алгоритмы для максимальной клики и максимального независимого множества кругового графа», Networks , 3 (3): 261–273, doi : 10.1002/net.3230030305 .
• Гольдманн, М.; Хостад, Дж. (1992), «Простая нижняя граница для монотонной клики с использованием коммуникативной игры» (PDF) , Information Processing Letters , 41 (4): 221–226, CiteSeerX   10.1.1.185.3065 , doi : 10.1016/0020 -0190(92)90184-W .
• Грегер, Ханс Дитмар (1992), «О рандомизированной сложности свойств монотонных графов» (PDF) , Acta Cybernetica , 10 (3): 119–127, заархивировано из оригинала (PDF) 24 сентября 2015 г. , получено в 2009 г. -10-02
• Гроссо, А.; Локателли, М.; Делла Кроче, Ф. (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 .
• Хамзаоглу И.; Патель, Дж. Х. (1998), "Алгоритмы сжатия тестового набора для комбинационных схем", Proc. 1998 Международная конференция IEEE/ACM по автоматизированному проектированию , стр. 283–289, doi : 10.1145/288548.288615 , S2CID   12258606 .
• Харари, Ф .; Росс, IC (1957), «Процедура обнаружения клик с использованием групповой матрицы», Sociometry , 20 (3), Американская социологическая ассоциация: 205–215, doi : 10.2307/2785673 , JSTOR   2785673 , MR   0110590 .
• Хостад, Дж. (1999), «Клик трудно определить в пределах n ^{1 - е} ", Acta Mathematica , 182 (1): 105–142, doi : 10.1007/BF02392825 .
• Импальяццо, Р. ; Патури, Р.; Зейн, Ф. (2001), «Какие проблемы имеют сильно экспоненциальную сложность?», Journal of Computer and System Sciences , 63 (4): 512–530, doi : 10.1006/jcss.2001.1774 .
• Итай, А.; Роде, М. (1978), «Нахождение минимальной схемы в графе», SIAM Journal on Computing , 7 (4): 413–423, doi : 10.1137/0207033 .
• Джеррум, М. (1992), «Большие клики ускользают от процесса метрополиса», Случайные структуры и алгоритмы , 3 (4): 347–359, doi : 10.1002/rsa.3240030402 .
• Цзянь, Т (1986), «Ан О (2 ^{0,304 н} ) алгоритм решения задачи о максимальном независимом множестве», IEEE Transactions on Computers , 35 (9), IEEE Computer Society: 847–851, doi : 10.1109/TC.1986.1676847 , ISSN   0018-9340 .
• Джонсон, Д.С .; Трик, Массачусетс , ред. (1996), Клики, раскраска и выполнимость: вторая задача реализации DIMACS, 11–13 октября 1993 г. , Серия DIMACS по дискретной математике и теоретической информатике, том. 26, Американское математическое общество , ISBN.  0-8218-6609-5 .
• Джонсон, Д.С .; Яннакакис, М. (1988), «О создании всех максимальных независимых наборов», Information Processing Letters , 27 (3): 119–123, doi : 10.1016/0020-0190(88)90065-8 .
• Карп, Ричард М. (1972), «Сводимость комбинаторных задач», в Miller, RE; Тэтчер, Дж. У. (ред.), Сложность компьютерных вычислений (PDF) , Нью-Йорк: Пленум , стр. 85–103, заархивировано из оригинала (PDF) 29 июня 2011 г. , получено 17 декабря 2009 г.
• Карп, Ричард М. (1976), «Вероятностный анализ некоторых комбинаторных задач поиска», в Трауб, Дж. Ф. (редактор), « Алгоритмы и сложность: новые направления и недавние результаты» , Нью-Йорк: Academic Press , стр. 1–19 .
• Катаяма, К.; Хамамото, А.; Нарихиса, Х. (2005), «Эффективный локальный поиск проблемы максимальной клики», Information Processing Letters , 95 (5): 503–511, doi : 10.1016/j.ipl.2005.05.010 .
• Хот, С. (2001), «Улучшенные результаты неаппроксимируемости для MaxClique, хроматического числа и приблизительной раскраски графов», Труды 42-го симпозиума IEEE по основам компьютерных наук , стр. 600–609, doi : 10.1109/SFCS.2001.959936 , ISBN  0-7695-1116-3 , S2CID   11987483 .
• Клокс, Т.; Крач, Д.; Мюллер, Х. (2000), «Эффективный поиск и подсчет небольших индуцированных подграфов», Information Processing Letters , 74 (3–4): 115–121, doi : 10.1016/S0020-0190(00)00047-8 .
• Конц, Дж.; Янежич, Д. (2007), «Улучшенный алгоритм ветвей и границ для задачи максимальной клики» (PDF) , MATCH Communications in Mathematical and in Computer Chemistry , 58 (3): 569–590 . Исходный код
• Куль, Ф.С.; Криппен, генеральный менеджер; Фризен, Д.К. (1983), «Комбинаторный алгоритм расчета связывания лигандов», Журнал вычислительной химии , 5 (1): 24–34, doi : 10.1002/jcc.540050105 , S2CID   122923018 .
• Лагариас, Джеффри С .; Шор, Питер В. (1992), «Гипотеза Келлера о разбиении куба ложна в больших измерениях», Бюллетень Американского математического общества , New Series, 27 (2): 279–283, arXiv : math/9210222 , doi : 10.1090 /S0273-0979-1992-00318-X , MR   1155280 , S2CID   6390600 .
• Липтон, Р.Дж. ; Тарьян, Р.Э. (1980), «Применение теоремы о плоском сепараторе», SIAM Journal on Computing , 9 (3): 615–627, doi : 10.1137/0209046 , S2CID   12961628 .
• Лю, Ю; Лу, Цзяхэн; Ян, Хуа; Сяо, Сяокуй; Вэй, Чжевэй (2015), «К максимально независимым множествам на массивных графах», Труды 41-й Международной конференции по очень большим базам данных (VLDB 2015) (PDF) , Труды Фонда VLDB, том. 8, стр. 2122–2133, doi : 10.14778/2831360.2831366 , hdl : 10138/157292 .
• Люс, Р. Дункан ; Перри, Альберт Д. (1949), «Метод матричного анализа групповой структуры», Psychometrika , 14 (2): 95–116, doi : 10.1007/BF02289146 , hdl : 10.1007/BF02289146 , PMID   18152948 , S2CID   16186758 .
• Макки, Джон (2002), «Кубическая мозаика восьмого измерения без разделения граней», Discrete and Computational Geometry , 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) , Конспекты лекций по информатике, том. 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 .
• Мун, Дж.В.; Мозер, Л. (1965), «О кликах в графах», Израильский математический журнал , 3 : 23–28, doi : 10.1007/BF02760024 , MR   0182577 , S2CID   9855414 .
• Нешетрил, Дж .; Поляк, С. (1985), «О сложности проблемы подграфа», Математические обзоры Университета Каролины , 26 (2): 415–419 .
• Остергорд, PRJ (2002), «Быстрый алгоритм для задачи максимальной клики», Discrete Applied Mathematics , 120 (1–3): 197–207, doi : 10.1016/S0166-218X(01)00290-6 .
• Оуян, К.; Каплан, ПД; Лю, С.; Либчабер, А. (1997), «ДНК-решение проблемы максимальной клики», Science , 278 (5337): 446–449, Bibcode : 1997Sci...278..446O , doi : 10.1126/science.278.5337.446 , ПМИД   9334300 .
• Пападимитриу, Христос Х .; Яннакакис, Михалис (1981), «Проблема клики для плоских графов», Information Processing Letters , 13 (4–5): 131–133, doi : 10.1016/0020-0190(81)90041-7 , MR   0651460 .
• Пардалос, премьер-министр; Роджерс, Г. П. (1992), «Алгоритм ветвей и границ для задачи максимальной клики», Computers & Operations Research , 19 (5): 363–375, doi : 10.1016/0305-0548(92)90067-F .
• Разборов А.А. (1985), "Нижние оценки монотонной сложности некоторых булевых функций", Известия АН СССР (на русском языке), 281 : 798–801. Английский перевод на сов. Математика. Докл. 31 (1985): 354–357. {{citation}}:CS1 maint:postscript ( ссылка ) .
• Режен, Ж.-К. (2003), «Использование программирования в ограничениях для решения задачи о максимальной клике», Proc. 9-й Международный. Конф. Принципы и практика программирования с ограничениями – CP 2003 , Конспекты лекций по информатике, том. 2833, Springer-Verlag , стр. 634–648, doi : 10.1007/978-3-540-45193-8_43 .
• Родос, Николас; Уиллетт, Питер; Кальве, Ален; Данбар, Джеймс Б.; Хамблет, Кристина (2003), «CLIP: поиск по сходству в трехмерных базах данных с использованием обнаружения кликов», Journal of Chemical Information and Computer Sciences , 43 (2): 443–448, doi : 10.1021/ci025605o , PMID   12653507 .
• Робсон, Дж. М. (1986), «Алгоритмы для максимальных независимых множеств», Журнал алгоритмов , 7 (3): 425–440, doi : 10.1016/0196-6774(86)90032-5 .
• Робсон, Дж. М. (2001), Нахождение максимального независимого множества за время O (2 ^{н /4} ) .
• Росген, Б; Стюарт, Л. (2007), «Результаты по сложности на графах с небольшим количеством клик» , Discrete Mathematics and Theoretical Computer Science , 9 (1): 127–136 .
• Самудрала, Рам; Моулт, Джон (1998), «Теоретико-графовый алгоритм для сравнительного моделирования структуры белка», Journal of Molecular Biology , 279 (1): 287–302, doi : 10.1006/jmbi.1998.1689 , PMID   9636717 .
• Сетураман, Самьюкта; Бутенко, Сергей (2015), «Проблема клики с максимальным соотношением», Computational Management Science , 12 (1): 197–218, doi : 10.1007/s10287-013-0197-z , MR   3296231 , S2CID   46153055 .
• Сонг, Ю. (2015), «О проблеме независимого множества в случайных графах» , Международный журнал компьютерной математики , 92 (11): 2233–2242, doi : 10.1080/00207160.2014.976210 , S2CID   6713201 .
• Спирин, Виктор; Мирный, Леонид А. (2003), «Белковые комплексы и функциональные модули в молекулярных сетях», Труды Национальной академии наук , 100 (21): 12123–12128, Бибкод : 2003PNAS..10012123S , doi : 10.1073/pnas. 2032324100 , ПМК   218723 , ПМИД   14517352 .
• Тарьян, RE ; Трояновский, А.Е. (1977), «Нахождение максимального независимого набора» (PDF) , SIAM Journal on Computing , 6 (3): 537–546, doi : 10.1137/0206038 .
• Томита, Э.; Камеда, Т. (2007), «Эффективный алгоритм ветвей и границ для поиска максимальной клики с помощью вычислительных экспериментов», Journal of Global Optimization , 37 (1): 95–111, doi : 10.1007/s10898-006-9039 -7 , S2CID   21436014 .
• Томита, Э.; Секи, Т. (2003), «Эффективный алгоритм ветвей и границ для поиска максимальной клики» , Дискретная математика и теоретическая информатика , Конспекты лекций по информатике, том. 2731, Springer-Verlag, стр. 278–289 , номер документа : 10.1007/3-540-45066-1_22 , ISBN.  978-3-540-40505-4 , S2CID   21436014 .
• Томита, Э.; Танака, А.; Такахаши, Х. (2006), «Временная сложность в наихудшем случае для генерации всех максимальных клик и вычислительных экспериментов», Theoretical Computer Science , 363 (1): 28–42, doi : 10.1016/j.tcs.2006.06.015 .
• Цукияма, С.; Иде, М.; Ариеси, И.; Сиракава, И. (1977), «Новый алгоритм генерации всех максимальных независимых наборов», SIAM Journal on Computing , 6 (3): 505–517, doi : 10.1137/0206036 .
• Валиант, Л.Г. (1983), "Экспоненциальные нижние оценки для ограниченных монотонных схем", Proc. 15-й симпозиум ACM по теории вычислений , стр. 110–117, doi : 10.1145/800061.808739 , ISBN  0-89791-099-0 , S2CID   6326587 .
• Василевская, В. ; Уильямс, Р. (2009), «Поиск, минимизация и подсчет взвешенных подграфов», Proc. 41-й симпозиум ACM по теории вычислений , стр. 455–464, CiteSeerX   10.1.1.156.345 , doi : 10.1145/1536414.1536477 , ISBN  978-1-60558-506-2 , S2CID   224579 .
• Вегенер, И. (1988), «О сложности ветвящихся программ и деревьев решений для кликовых функций», Journal of the ACM , 35 (2): 461–472, doi : 10.1145/42282.46161 , S2CID   11967153 .
• Юстер, Р. (2006), «Поиск и подсчет клик и независимых множеств в r -однородных гиперграфах», Information Processing Letters , 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 .