В информатике задача о клике — это вычислительная задача поиска клик (подмножеств вершин, все из которых смежны друг с другом, также называемых полными подграфами ) в графе . Она имеет несколько различных формулировок в зависимости от того, какие клики и какая информация о кликах должны быть найдены. Общие формулировки задачи о клике включают поиск максимальной клики (клики с наибольшим возможным числом вершин), поиск клики максимального веса во взвешенном графе, перечисление всех максимальных клик (клики, которые нельзя увеличить) и решение задачи принятия решения о проверке того, содержит ли граф клику большего размера, чем заданный.
Проблема клики возникает в следующей реальной обстановке. Рассмотрим социальную сеть , где вершины графа представляют людей, а ребра графа представляют общих знакомых. Тогда клика представляет подмножество людей, которые все знают друг друга, и алгоритмы поиска клик могут быть использованы для обнаружения этих групп общих друзей. Наряду с ее приложениями в социальных сетях, проблема клики также имеет много приложений в биоинформатике и вычислительной химии .
Большинство версий проблемы клики сложны. Проблема принятия решения о клике является 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]
Неориентированный граф образован конечным набором вершин и набором неупорядоченных пар вершин, которые называются ребрами . По соглашению в анализе алгоритмов число вершин в графе обозначается как n , а число ребер обозначается как m . Клика в графе G — это полный подграф графа G. То есть это подмножество вершин K , такое что каждые две вершины из K являются двумя конечными точками ребра в G. Максимальная клика — это клика, к которой нельзя добавить больше вершин. Для каждой вершины v , которая не является частью максимальной клики, должна быть другая вершина w , которая находится в клике и не является смежной с v , что предотвращает добавление v в клику. Максимальная клика — это клика, которая включает в себя наибольшее возможное число вершин. Число клики ω ( G ) — это число вершин в максимальной клике графа G . [1]
Было изучено несколько тесно связанных задач по поиску клик. [14]
Первые четыре из этих проблем важны для практических приложений. Проблема принятия решения о клике не имеет практического значения; она сформулирована таким образом, чтобы применить теорию 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 :
Используя эти наблюдения, они могут сгенерировать все максимальные клики в 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]
Планарные графы и другие семейства разреженных графов обсуждались выше: они имеют линейно много максимальных клик ограниченного размера, которые могут быть перечислены за линейное время. [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-полной . Это была одна из 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]
Вычислительная сложность задачи клики привела к тому, что ее использовали для доказательства нескольких нижних границ сложности схемы . Существование клики заданного размера является свойством монотонного графа , что означает, что если клика существует в заданном графе, она будет существовать в любом суперграфе . Поскольку это свойство монотонно, должна существовать монотонная схема, использующая только и вентили и или вентили , для решения задачи принятия решения о клике для заданного фиксированного размера клики. Однако можно доказать, что размер этих схем является суперполиномиальной функцией числа вершин и размера клики, экспоненциальной в кубическом корне числа вершин. [64] Даже если разрешено небольшое количество вентилей НЕ , сложность остается суперполиномиальной. [65] Кроме того, глубина монотонной схемы для задачи клики, использующей вентили ограниченного веера по входу, должна быть по крайней мере полиномиальной от размера клики. [66]
(Детерминированная) сложность дерева решений для определения свойства графа — это количество вопросов вида «Есть ли ребро между вершиной 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]
Слабые результаты, намекающие на то, что задачу о клике может быть трудно аппроксимировать, были известны в течение длительного времени. Гэри и Джонсон (1978) заметили, что, поскольку число клик принимает малые целые значения и является NP-трудным для вычисления, оно не может иметь полностью полиномиальную схему аппроксимации , если только P = NP. Если бы была доступна слишком точная аппроксимация, округление ее значения до целого числа дало бы точное число клик. Однако до начала 1990-х годов было известно немного больше, когда несколько авторов начали устанавливать связи между аппроксимацией максимальных клик и вероятностно проверяемыми доказательствами . Они использовали эти связи для доказательства сложности результатов аппроксимации для задачи о максимальной клике. [74] После многочисленных улучшений этих результатов теперь известно, что для любого действительного числа ε > 0 не может быть алгоритма с полиномиальным временем, который аппроксимирует максимальную клику с точностью до фактора, лучшего, чем O ( n 1 − ε ) , если только P = NP . [75]
Грубая идея этих результатов неаппроксимируемости заключается в формировании графа, представляющего вероятностно проверяемую систему доказательств для NP-полной проблемы, такой как проблема булевой выполнимости. В вероятностно проверяемой системе доказательств доказательство представлено в виде последовательности битов. Экземпляр проблемы выполнимости должен иметь действительное доказательство тогда и только тогда, когда оно выполнимо. Доказательство проверяется алгоритмом, который после полиномиального вычисления на входе проблемы выполнимости выбирает проверку небольшого количества случайно выбранных позиций строки доказательства. В зависимости от того, какие значения найдены в этой выборке битов, проверяющий либо примет, либо отклонит доказательство, не глядя на остальные биты. Ложные отрицания не допускаются: действительное доказательство всегда должно быть принято. Однако иногда ошибочно может быть принято недействительное доказательство. Для каждого недействительного доказательства вероятность того, что проверяющий его примет, должна быть низкой. [76]
Чтобы преобразовать вероятностно проверяемую систему доказательств этого типа в задачу клики, формируется граф с вершиной для каждого возможного допускающего запуска проверяющего доказательства. То есть вершина определяется одним из возможных случайных выборов наборов позиций для проверки и битовыми значениями для тех позиций, которые заставят проверяющего принять доказательство. Его можно представить частичным словом с 0 или 1 в каждой проверенной позиции и подстановочным символом в каждой оставшейся позиции. Две вершины являются смежными в этом графе, если соответствующие два допускающих запуска видят одинаковые битовые значения в каждой позиции, которую они оба проверяют. Каждая (действительная или недействительная) строка доказательства соответствует клике, набору допускающих запусков, которые видят эту строку доказательства, и все максимальные клики возникают таким образом. Одна из этих клик является большой тогда и только тогда, когда она соответствует строке доказательства, которую принимают многие проверяющие доказательства. Если исходный экземпляр выполнимости выполним, он будет иметь допустимую строку доказательства, которая принимается всеми запусками проверяющего, и эта строка будет соответствовать большой клике в графе. Однако, если исходный экземпляр не выполним, то все строки доказательства недействительны, каждая строка доказательства имеет только небольшое количество запусков проверяющего, которые ошибочно принимают ее, и все клики малы. Следовательно, если бы можно было отличить за полиномиальное время графы с большими кликами от графов, в которых все клики малы, или если бы можно было точно аппроксимировать проблему клики, то применение этой аппроксимации к графам, сгенерированным из экземпляров выполнимости, позволило бы отличить выполнимые экземпляры от невыполнимых. Однако это невозможно, если только P = NP. [76]
{{citation}}: CS1 maint: постскриптум ( ссылка ).