Проблема клики
Задача вычисления полных подграфов

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

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

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

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

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

История и применение

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

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

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

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

Определения

На представленном графе имеется одна максимальная клика — треугольник {1,2,5} и еще четыре максимальные клики — пары {2,3}, {3,4}, {4,5} и {4,6}.

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

Однако, когда число клик значительно меньше, чем в худшем случае, другие алгоритмы могут быть предпочтительнее. Как показали Цукияма и др. (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 из 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 — древесность данного графа. Makino & Uno (2004) предлагают альтернативный алгоритм, чувствительный к выходу, основанный на быстром умножении матриц. Johnson & Yannakakis (1988) показывают, что можно даже перечислить все максимальные клики в лексикографическом порядке с полиномиальной задержкой на клику. Однако выбор порядка важен для эффективности этого алгоритма: для обратного порядка не существует алгоритма с полиномиальной задержкой, если только P = NP .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

NP-полнота

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чен и др. (2006) показали, что поиск клик k -вершин не может быть выполнен за время n o ( k ), если только гипотеза экспоненциального времени не опровергается. Опять же, это дает доказательство того, что невозможен ни один фиксированно-параметрический алгоритм, поддающийся обработке. [73]

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

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

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

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

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

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

Примечания

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

Ссылки

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

  • Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Cambridge University Press, ISBN 978-0-521-42426-4.
  • Блэр, Джин RS; Пейтон, Барри (1993), «Введение в хордовые графы и деревья клик», Теория графов и вычисления разреженных матриц, IMA Vol. Math. Appl., т. 56, Springer, Нью-Йорк, стр. 1–29, doi :10.1007/978-1-4613-8369-7_1, ISBN 978-1-4613-8371-0, МР  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.
  • Дауни, Р. Г.; Феллоуз, М. Р. (1999), Параметризованная сложность , Springer-Verlag , ISBN 0-387-94883-X.
  • Golumbic, MC (1980), Алгоритмическая теория графов и совершенные графы , Информатика и прикладная математика, Academic Press , ISBN 0-444-51530-5.
  • Грётшель, М.; Ловас , Л.; Шрайвер , А. (1988), «9.4 Раскраска совершенных графов», Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, т. 2, Springer-Verlag , стр. 296–298, ISBN 0-387-13624-X.
  • Гутин, Г. (2004), «5.3 Независимые множества и клики», в Гросс, Дж. Л.; Йеллен, Дж. (ред.), Справочник по теории графов , Дискретная математика и ее приложения, CRC Press, стр. 389–402, ISBN 978-1-58488-090-5.
  • Muegge, Ingo; Rarey, Matthias (2001), «Стыковка и подсчет малых молекул», Reviews in Computational Chemistry , 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, ISBN 978-0-387-74758-3.
  • Пламмер, Майкл Д. (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-X.
  • Скиена, Стивен С. (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, Cambridge University Press, стр. 276, ISBN 978-0-521-38707-1.

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

  • Абелло, Дж.; Пардалос, П.М.; Резенде, М.Г.С. (1999), «О задачах максимальной клики в очень больших графах» (PDF) , в Абелло, Дж.; Виттер, Дж. (ред.), Внешние алгоритмы памяти , Серия DIMACS по дискретной математике и теоретической информатике, т. 50, Американское математическое общество , стр. 119–130, ISBN 0-8218-1184-3, заархивировано из оригинала (PDF) 2017-01-16 , извлечено 2017-01-13.
  • Алон, Н.; Боппана, Р. (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, MR  2178806.
  • Арора, Санджив ; Лунд, Карстен ; Мотвани, Раджив ; Судан, Мадху ; Сегеди, Марио (1998), «Проверка доказательств и сложность задач аппроксимации», Журнал ACM , 45 (3): 501–555, doi : 10.1145/278298.278306, S2CID  8561542, ECCC  TR98-008Первоначально представлено на Симпозиуме по основам компьютерной науки 1992 года , doi :10.1109/SFCS.1992.267823.
  • Арора, С.; Сафра , С. (1998), «Вероятностная проверка доказательств: новая характеристика NP», Журнал ACM , 45 (1): 70–122, doi : 10.1145/273865.273901 , S2CID  751563Первоначально представлено на Симпозиуме по основам компьютерной науки 1992 года , doi :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), «Заметка о проблеме сообщения о максимальных кликах», Теоретическая информатика , 407 (1): 564–568, doi : 10.1016/j.tcs.2008.05.010.
  • Чэнь, Цзяньэр; Хуан, Сючжэнь; Кань, Ияд А.; Ся, Ге (2006), «Сильные нижние вычислительные границы с помощью параметризованной сложности», Журнал компьютерных и системных наук , 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; Фархи, E.; Голдстоун, J .; Гутманн, S. (2002), «Поиск клик с помощью квантовой адиабатической эволюции», Квантовая информация и вычисления , 2 (3): 181–191, arXiv : quant-ph/0012104 , Bibcode : 2000quant.ph.12104C, doi : 10.26421/QIC2.3, S2CID  33643794.
  • Чайлдс, AM; Эйзенберг, JM (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), «Графы единичных дисков», Дискретная математика , 86 (1–3): 165–177, doi : 10.1016/0012-365X(90)90358-O
  • Кук, С.А. (1971), «Сложность процедур доказательства теорем», Труды 3-го симпозиума 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.
  • Дей, Уильям Х. Э.; Санкофф, Дэвид (1986), «Вычислительная сложность вывода филогений по совместимости», Систематическая зоология , 35 (2): 224–229, doi :10.2307/2413432, JSTOR  2413432.
  • Дауни, Р. Г.; Феллоуз, М. Р. (1995), «Распознаваемость и полнота с фиксированными параметрами. II. О полноте для W[1]», Теоретическая информатика , 141 (1–2): 109–131, doi : 10.1016/0304-3975(94)00097-3.
  • Эйзенбранд, Ф.; Грандони, Ф. (2004), «О сложности фиксированных параметров клики и доминирующего множества», Теоретическая информатика , 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.
  • Even, S. ; Pnueli, A. ; Lempel, A. (1972), "Графы перестановок и транзитивные графы", Журнал ACM , 19 (3): 400–410, doi : 10.1145/321707.321710 , S2CID  9501737.
  • Fahle, T. (2002), «Просто и быстро: улучшение алгоритма ветвей и границ для максимальной клики», Proc. 10th European Symposium on Algorithms , Lecture Notes in Computer Science, т. 2461, Springer-Verlag, стр. 47–86, doi :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 ; Джонсон, DS (1978), "«Сильные» результаты NP-полноты: мотивация, примеры и последствия», Журнал ACM , 25 (3): 499–508, doi : 10.1145/322077.322090 , S2CID  18371269.
  • Гэри, М. Р.; Джонсон , Д. С .; Стокмейер, Л. (1976), «Некоторые упрощенные NP-полные задачи на графах», Теоретическая информатика , 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.
  • Goldmann, M.; Håstad, J. (1992), «Простая нижняя граница для монотонной клики с использованием коммуникационной игры» (PDF) , Information Processing Letters , 41 (4): 221–226, CiteSeerX  10.1.1.185.3065 , doi :10.1016/0020-0190(92)90184-W.
  • Gröger, Hans Dietmar (1992), «О рандомизированной сложности свойств монотонных графов» (PDF) , Acta Cybernetica , 10 (3): 119–127, архивировано из оригинала (PDF) 24.09.2015 , извлечено 02.10.2009
  • Гроссо, А.; Локателли, М.; Делла Кроче, Ф. (2004), «Объединение обменов и весов узлов в адаптивном жадном подходе для задачи максимальной клики», Журнал эвристики , 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), «Алгоритмы уплотнения тестового набора для комбинационных схем», Труды Международной конференции IEEE/ACM по автоматизированному проектированию 1998 г. , стр. 283–289, doi : 10.1145/288548.288615 , ISBN 1-58113-008-2, S2CID  12258606.
  • Харари, Ф.; Росс, И.С. (1957), «Процедура обнаружения клики с использованием групповой матрицы», Социометрия , 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), «Какие проблемы имеют строго экспоненциальную сложность?», Журнал компьютерных и системных наук , 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), « Алгоритм O (2 0,304 n ) для решения задачи максимального независимого множества», 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; Thatcher, JW (ред.), Complexity of Computer Computations (PDF) , Нью-Йорк: Plenum , стр. 85–103, архивировано из оригинала (PDF) 29-06-2011 , извлечено 17-12-2009.
  • Карп, Ричард М. (1976), «Вероятностный анализ некоторых комбинаторных задач поиска», в Traub, JF (ред.), Алгоритмы и сложность: новые направления и последние результаты , Нью-Йорк: 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.
  • Konc, J.; Janežič, D. (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.
  • Lagarias, Jeffrey C. ; Shor, Peter W. (1992), «Гипотеза Келлера о кубической мозаике ложна в больших размерностях», Bulletin of the American Mathematical Society , 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), «Метод матричного анализа групповой структуры», Психометрика , 14 (2): 95–116, doi : 10.1007/BF02289146, hdl : 10.1007/BF02289146 , PMID  18152948, S2CID  16186758.
  • Макки, Джон (2002), «Кубическая мозаика размерности восемь без общих граней», Дискретная и вычислительная геометрия , 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, ISBN 978-3-540-22339-9.
  • Мека, Рагху; Потехин, Аарон; Вигдерсон, Ави (2015), «Нижние границы суммы квадратов для посаженной клики», Труды сорок седьмого ежегодного симпозиума ACM по теории вычислений (STOC '15) , Нью-Йорк, США: ACM, стр. 87–96, arXiv : 1503.06447 , doi : 10.1145/2746539.2746600, ISBN 978-1-4503-3536-2, S2CID  2754095.
  • Moon, JW; Moser, L. (1965), «О кликах в графах», Israel Journal of Mathematics , 3 : 23–28, doi : 10.1007/BF02760024 , MR  0182577, S2CID  9855414.
  • Нешетржил, Ю. ; Поляк, С. (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.
  • Оуян, Q.; Каплан, PD; Лю, S.; Либхабер, A. (1997), «ДНК-решение задачи максимальной клики», Science , 278 (5337): 446–449, Bibcode : 1997Sci...278..446O, doi : 10.1126/science.278.5337.446, PMID  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: постскриптум ( ссылка ).
  • Регин, Ж.-К. (2003), «Использование программирования в ограничениях для решения задачи о максимальной клике», Труды 9-й Международной конференции «Принципы и практика программирования в ограничениях» – CP 2003 , Lecture Notes in Computer Science, т. 2833, Springer-Verlag , стр. 634–648, doi :10.1007/978-3-540-45193-8_43, ISBN 978-3-540-20202-8.
  • Родс, Николас; Уиллетт, Питер; Кальве, Ален; Данбар, Джеймс Б.; Хамблет, Кристин (2003), «CLIP: поиск сходства в трехмерных базах данных с использованием обнаружения клик», Журнал химической информации и компьютерных наук , 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(2n/4).
  • Росген, Б.; Стюарт, Л. (2007), «Результаты сложности на графах с небольшим количеством клик», Дискретная математика и теоретическая информатика , 9 (1): 127–136.
  • Самудрала, Рам; Молт, Джон (1998), «Теоретико-графовый алгоритм для сравнительного моделирования структуры белка», Журнал молекулярной биологии , 279 (1): 287–302, doi :10.1006/jmbi.1998.1689, PMID  9636717.
  • Sethuraman, Samyukta; Butenko, Sergiy (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, Bibcode : 2003PNAS..10012123S, doi : 10.1073/pnas.2032324100 , PMC  218723 , PMID  14517352.
  • Тарьян, RE ; Трояновский, AE (1977), «Нахождение максимального независимого множества» (PDF) , SIAM Journal on Computing , 6 (3): 537–546, doi :10.1137/0206038.
  • Томита, Э.; Камеда, Т. (2007), «Эффективный алгоритм ветвей и границ для поиска максимальной клики с помощью вычислительных экспериментов», Журнал глобальной оптимизации , 37 (1): 95–111, doi :10.1007/s10898-006-9039-7, S2CID  21436014.
  • Томита, Э.; Секи, Т. (2003), «Эффективный алгоритм ветвей и границ для поиска максимальной клики», Дискретная математика и теоретическая информатика , Конспект лекций по информатике, т. 2731, Springer-Verlag, стр. 278–289, doi :10.1007/3-540-45066-1_22, ISBN 978-3-540-40505-4, S2CID  21436014.
  • Томита, Э.; Танака, А.; Такахаши, Х. (2006), «Сложность времени в худшем случае для генерации всех максимальных клик и вычислительные эксперименты», Теоретическая информатика , 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.
  • Вэлиант, LG (1983), «Экспоненциальные нижние границы для ограниченных монотонных схем», Труды 15-го симпозиума ACM по теории вычислений , стр. 110–117, doi :10.1145/800061.808739, ISBN 0-89791-099-0, S2CID  6326587.
  • Василевска, В .; Уильямс, Р. (2009), «Поиск, минимизация и подсчет взвешенных подграфов», Труды 41-го симпозиума 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 -однородных гиперграфах», Information Processing Letters , 99 (4): 130–134, doi :10.1016/j.ipl.2006.04.005.
  • Цукерман, Д. (2006), «Линейные экстракторы степени и неаппроксимируемость максимальной клики и хроматического числа», Труды 38-го симпозиума ACM. Теория вычислений , стр. 681–690, doi :10.1145/1132516.1132612, ISBN 1-59593-134-1, S2CID  5713815, ECCC  TR05-100.
Взято с "https://en.wikipedia.org/w/index.php?title=Проблема_клики&oldid=1247287775"