В информатике проблема клики — это вычислительная задача поиска клик (подмножеств вершин, смежных друг с другом, также называемых полными подграфами ) в графе . Он имеет несколько различных формулировок в зависимости от того, какие клики и какую информацию о кликах следует найти. Общие формулировки проблемы клики включают поиск максимальной клики (клики с максимально возможным числом вершин), поиск клики максимального веса во взвешенном графе, составление списка всех максимальных клик (клик, которые невозможно увеличить) и решение проблемы принятия решений. проверки того, содержит ли граф клику большего размера, чем заданный.
Проблема клики возникает в следующей реальной ситуации. Рассмотрим социальную сеть , где вершины графа представляют людей, а ребра графа представляют собой взаимное знакомство. Тогда клика представляет собой подмножество людей, которые все знают друг друга, и алгоритмы поиска клик могут быть использованы для обнаружения этих групп общих друзей. Помимо приложений в социальных сетях, проблема клики также имеет множество приложений в биоинформатике и вычислительной химии .
Большинство вариантов проблемы клики сложны. Проблема решения клики является NP-полной (одна из 21 NP-полной задачи Карпа ). Проблема нахождения максимальной клики при фиксированных параметрах является трудноразрешимой и трудно аппроксимируемой . А перечисление всех максимальных клик может потребовать экспоненциального времени , поскольку существуют графы с экспоненциально большим количеством максимальных клик. Поэтому большая часть теории проблемы клики посвящена выявлению особых типов графов, которые допускают более эффективные алгоритмы, или установлению вычислительной сложности общей проблемы в различных моделях вычислений.
Чтобы найти максимальную клику, можно систематически проверять все подмножества, но такой метод поиска методом перебора отнимает слишком много времени, чтобы быть практичным для сетей, содержащих более нескольких десятков вершин. Хотя для этой задачи не известен алгоритм с полиномиальным временем , известны более эффективные алгоритмы , чем поиск методом грубой силы. Например, алгоритм Брона-Кербоша можно использовать для перечисления всех максимальных клик за оптимальное время в наихудшем случае, а также можно составить их список за полиномиальное время на клику.
Изучение полных подграфов в математике предшествовало терминологии «клики». Например, полные подграфы впервые появились в математической литературе в теоретико-графовой переформулировке теории Рамсея Эрдешем и Секересом (1935). Но термин «клика» и проблема алгоритмического составления списка клик пришли из социальных наук, где полные подграфы используются для моделирования социальных клик — групп людей, которые все знают друг друга. Люс и Перри (1949) использовали графики для моделирования социальных сетей и адаптировали терминологию социальных наук к теории графов. Они были первыми, кто назвал полные подграфы «кликами». Первый алгоритм решения проблемы клики принадлежит Харари и Россу (1957), [1] , которые руководствовались социологическими применениями. Исследователи социальных наук также определили различные другие типы клик и максимальных клик в социальной сети, «сплоченные подгруппы» людей или актеров в сети, каждый из которых разделяет один из нескольких различных типов отношений связи. Многие из этих обобщенных понятий клик можно также найти, построив неориентированный граф, ребра которого представляют собой связанные пары актеров из социальной сети, а затем применив к этому графу алгоритм решения проблемы клики. [2]
После работы Харари и Росс многие другие разработали алгоритмы для различных версий проблемы клики. [1] В 1970-х годах исследователи начали изучать эти алгоритмы с точки зрения анализа наихудшего случая . См., например, раннюю работу Тарьяна и Трояновски (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 ( nkk2 ) , что выражается с использованием обозначения «большое О » . Это связано с тем, что необходимо проверить O (nk) подграфов, каждый из которых имеет O ( k2 ) ребер , наличие которых в 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 и удалением ненужных клик. -соседи В. _ Однако некоторые клики G могут быть сгенерированы таким образом из более чем одной родительской клики G \ v , поэтому они устраняют дубликаты, выводя клику в G только тогда, когда ее родительский элемент в G \ v является лексикографически максимальным среди всех возможных родительских клик. На основе этого принципа они показывают, что все максимальные клики в G могут быть созданы за время O ( mn ) на клику, где m — количество ребер в G , а n — количество вершин. Чиба и Нишизеки (1985) улучшают это значение до O( ma ) на клику, где a — древесность данного графа. Макино и Уно (2004) предлагают альтернативный чувствительный к выходу алгоритм, основанный на быстром умножении матриц. Джонсон и Яннакакис (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 ) . Это рекурсивная схема поиска с возвратом, аналогичная схеме алгоритма Брона-Кербоша , но способная исключить некоторые рекурсивные вызовы, когда можно показать, что клики, найденные внутри вызова, будут неоптимальными. Цзян (1986) улучшил время до O (2 0,304 n ) = O (1,2346 n ) , а Робсон (1986) улучшил его до O (2 0,276 n ) = O (1,2108 n ) за счет большего использования пространства. . Алгоритм Робсона сочетает в себе аналогичную схему обратного отслеживания (с более сложным анализом случаев) и технику динамического программирования , в которой оптимальное решение предварительно вычисляется для всех небольших связных подграфов графа дополнения . Эти частичные решения используются для сокращения рекурсии с возвратом. Самый быстрый алгоритм, известный сегодня, — это усовершенствованная версия этого метода Робсона (2001), которая работает за время O (2 0,249 n ) = O (1,1888 n ) . [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 ) (выраженные с помощью мало- о обозначение ). [55]
Некоторые авторы рассматривали алгоритмы аппроксимации , которые пытаются найти клику или независимое множество, которое хотя и не является максимальным, но имеет размер, максимально близкий к максимальному, который может быть найден за полиномиальное время. Хотя большая часть этой работы была сосредоточена на независимых множествах в разреженных графах, что не имеет смысла для задачи дополнительной клики, также проводились работы над алгоритмами аппроксимации, которые не используют такие предположения о разреженности. [56]
Файги (2004) описывает алгоритм с полиномиальным временем, который находит клику размера Ω((log n /log log n ) 2 ) в любом графе, который имеет число клик Ω( n /log k n ) для любой константы k . Используя этот алгоритм, когда число клик данного входного графа находится между n /log n и n /log 3 n , переключившись на другой алгоритм Боппаны и Халлдорссона (1992) для графов с более высокими числами клик и выбрав двух- вершинную клику, если оба алгоритма ничего не могут найти, Файги предлагает аппроксимационный алгоритм, который находит клику с количеством вершин в пределах коэффициента O( n (log log n ) 2 /log 3 n ) от максимума. Хотя степень аппроксимации этого алгоритма слабая, на сегодняшний день он является наиболее известным. [57] Результаты по твердости аппроксимации, описанные ниже, показывают, что не может быть алгоритма аппроксимации со степенью аппроксимации, значительно меньшей линейной.
Задача решения клики является NP-полной . Это была одна из первых 21 задач Ричарда Карпа, показанная NP-полной в его статье 1972 года «Сводимость среди комбинаторных задач». [59] Эта проблема также упоминалась в статье Стивена Кука , представляющей теорию NP-полных задач. [60] Из-за сложности решения проблемы, проблема нахождения максимальной клики также является NP-трудной. Если бы можно было решить эту проблему, можно было бы также решить проблему принятия решения, сравнив размер максимальной клики с параметром размера, заданным в качестве входных данных в задаче принятия решения.
Доказательство NP-полноты Карпа представляет собой сокращение проблемы булевой выполнимости по принципу «многие единицы» . В нем описывается, как перевести булевы формулы в конъюнктивной нормальной форме (КНФ) в эквивалентные примеры задачи о максимальной клике. [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 -клики имеет сложность дерева решений ровно n ( n - 1)/2 Боллобасом (1976). Детерминированные деревья решений также требуют экспоненциального размера для обнаружения клик или большого полиномиального размера для обнаружения клик ограниченного размера. [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-трудно вычислить, оно не может иметь полностью полиномиальную схему аппроксимации . Если бы было доступно слишком точное приближение, округление его значения до целого числа дало бы точное число клик. Однако мало что было известно до начала 1990-х годов, когда несколько авторов начали проводить связь между аппроксимацией максимальных клик и вероятностно проверяемыми доказательствами . Они использовали эти связи для доказательства сложности результатов аппроксимации задачи о максимальной клике. [74] После многих улучшений этих результатов теперь известно, что для каждого действительного числа ε > 0 не может быть алгоритма с полиномиальным временем, который аппроксимирует максимальную клику с точностью до коэффициента лучше, чем O ( n 1 − ε ) , если только П = НП . [75]
Грубая идея этих результатов о неаппроксимируемости состоит в том, чтобы сформировать граф, который представляет собой вероятностно проверяемую систему доказательств для NP-полной проблемы, такой как проблема булевой выполнимости. В вероятностно проверяемой системе доказательств доказательство представляется в виде последовательности битов. Экземпляр проблемы выполнимости должен иметь валидное доказательство тогда и только тогда, когда он выполним. Доказательство проверяется с помощью алгоритма, который после вычислений за полиномиальное время на входных данных задачи выполнимости выбирает проверку небольшого количества случайно выбранных позиций строки доказательства. В зависимости от того, какие значения найдены в этой выборке битов, программа проверки либо примет, либо отклонит доказательство, не обращая внимания на остальные биты. Ложноотрицательные результаты не допускаются: всегда необходимо принимать действительное доказательство. Однако иногда недействительное доказательство может быть ошибочно принято. Для каждого недействительного доказательства вероятность того, что проверяющая сторона примет его, должна быть низкой. [76]
Чтобы преобразовать вероятностно проверяемую систему доказательств этого типа в задачу клики, формируют граф с вершиной для каждого возможного приемочного запуска средства проверки доказательств. То есть вершина определяется одним из возможных случайных выборов наборов позиций для проверки и значениями битов для тех позиций, которые заставят проверяющую программу принять доказательство. Оно может быть представлено частью слова с 0 или 1 в каждой исследуемой позиции и подстановочным знаком в каждой оставшейся позиции. В этом графе две вершины являются смежными, если соответствующие два принимающих запуска видят одни и те же значения битов в каждой позиции, которую они оба проверяют. Каждая (действительная или недействительная) строка доказательства соответствует клике, множеству принимающих серий, которые видят эту строку доказательства, и все максимальные клики возникают таким образом. Одна из этих клик велика тогда и только тогда, когда она соответствует строке доказательства, которую принимают многие программы проверки доказательств. Если исходный экземпляр выполнимости является выполнимым, он будет иметь действительную строку доказательства, которая принимается всеми запусками программы проверки, и эта строка будет соответствовать большой клике в графе. Однако если исходный экземпляр неудовлетворителен, то все строки доказательства недействительны, каждая строка доказательства имеет лишь небольшое количество прогонов проверки, которые ошибочно принимают ее, и все клики малы. Следовательно, если бы можно было за полиномиальное время отличить графы с большими кликами от графов, в которых все клики малы, или если бы можно было точно аппроксимировать задачу о клике, то применение этого приближения к графам, сгенерированным из экземпляров выполнимости, позволило бы выполнимым экземплярам отличать от неудовлетворительных примеров. Однако это невозможно, если P = NP. [76]
{{citation}}: CS1 maint: постскриптум ( ссылка ).