Войти
Алгоритм грубой силы находит 4-клику в 7-вершинном графе (дополнение 7 -vertex граф путей ) систематической проверки всех C (7,4) = 35 4-вершинных подграфов на полноту. В информатике задача клики - это вычислительная задача поиска клик (подмножества вершин, все смежные друг с другом, также называемые полные подграфы ) в графе. Он имеет несколько различных формулировок в зависимости от того, какие клики и какую информацию о них следует искать. Общие формулировки проблемы клики включают поиск максимальной клики (клики с максимально возможным дополнительным вершин), поиск клики максимального веса в взвешенном графе, перечисление всех максимальных клик (клики, которые не могут быть увеличены), и решение задачи принятия решения проверки того, содержит ли граф клику, превышающую заданный размер.
Проблема с кликами возникает в следующих реальных условиях. Рассмотрим социальную сеть, где вершины графа представить людей, а ребра графа представить собой общих знакомых. Затем клика представляет собой подмножество людей, которые знают друг друга. Наряду с мобильными телефонами проблема также имеет множество приложений в биоинформатике и вычислительной химии.
. Большинство версий проблемы клики сложны. Проблема решения клики - это НП-полная (одна из 21 НП-полная проблема Карпа ). Проблема поиска максимального клики является как трудноразрешимым с фиксированным параметром, так и трудно аппроксимировать. Кроме перечисления всех максимальных клик может потребовать экспоненциального времени, поскольку существуют графы с экспоненциально большим количеством максимальных клик. Следовательно, большая часть теории клики посвящена определенным проблемам типов графов, которые допускают более эффективные алгоритмы, или установлению вычислительной сложности проблемы общей сложности в различных моделях вычислений.
Чтобы найти максимальную клику, можно систематически проверять все подмножества, но такой вид перебора слишком трудоемок, чтобы быть практичным для сетей, более нескольких десятков вершин.. Хотя для этой проблемы известен алгоритм с полиномиальным временем, известны более эффективные алгоритмы , чем поиск методом перебора. Например, алгоритм Брона - Кербоша можно использовать для перечисления всех максимальных клик в наихудшее оптимальное время, а также можно перечислить их за полиномиальное время для каждой клики.
Изучение полных подграфов в математике предшествовало терминологии «клика». Например, полные подграфы появились в математической литературе в теоретико-графической переформулировке теории Рамсея, выполненной Erds Szekeres (1935). Но термин «клика» и проблема алгоритмического перечисления клик пришли из социальных наук, где полные подграфы используются для моделирования социальных клик, групп людей, которые все знают друг друга. Люс и Перри (1949) использовали графы для моделирования социальных сетей и адаптировали терминологию социальных наук к теории графов. Они первыми назвали полные подграфы «кликами». Первым алгоритмом решения проблемы клики является алгоритмом Harary Ross (1957), который руководствовался социологическим приложением. Исследователи социальных наук также определили различные типы клик и максимальных клик в социальных сетях, «сплоченные подгруппы» людей или субъектов в сети, все из разных видов взаимосвязи. Многие из этих обобщенных понятий клик также можно, построив неориентированный граф, ребра которого включают связанные пары акторов из социальной сети, а применив алгоритм для проблемы клик к этому графу.
Работа Глобальной системы, многие другие разработали алгоритмы различных версий проблемы клики. В 1970-х годах исследователи начали изучать эти алгоритмы с точки зрения анализа наихудшего случая. См. Например, Tarjan Trojanowski (1977), ранняя работа по наихудшему случаю сложности задачи о максимальной клике. Также в 1970-х годах, начиная с работ Кука (1971) и Карпа (1972), исследователи начали использовать теорию НП-полноты и изучены с ней неразрешимости. результаты, чтобы дать математическое объяснение воспринимаемой сложности проблемы клики. В 1990-х годах была опубликована серия революционных статей, начинающаяся с Feige et al. (1991) и описанные в The New York Times показали, что (при условии P ≠ NP ) невозможно даже точно приблизительно определить проблему. и качественно.
Алгоритмы поиска кликовались в химии для поиска химических веществ, которые соответствуют структуре, и для моделирования стыковки молекул и сайтов связывания химических факторов. Их также можно использовать для поиска похожих структур в разных молекулах. В приложении этих приложений формируется граф, каждая вершина которого представляет собой согласованные пару элементов, по одному от каждой из двух молекул. Две вершины соединяются ребром, если совпадения, они соответствуют, совпадают друг с другом. Совместимость может означать, например, расстояние между атомами в двух молекулах равны с точностью до некоторого заданного допуска. Клика на этом графике представляет собой набор совпадающих пар элементов, в которых все совпадения совпадают друг с другом. Частным случаем этого метода является использование модульного произведения графов для проблем поиска предельного общего общего подграфа двух графов к задаче поиска максимального клики в их продукт.
В автоматической генерации тестовой таблицы поиск кликов может помочь ограничить размер тестового набора. В биоинформатике алгоритмы поиска кликов использовались для вывода эволюционных деревьев, предсказания белковых структур и поиска связующих кластеров белков. Список клик в графе зависимостей - важный шаг в аналитических случайных процессах. Вике гипотеза Келлера о прямом разбиении гиперкубов была опровергнута Lagarias Shor (1992), которые использовали алгоритм поиска кликов на соответствующий граф, чтобы найти контрпример.
Показанный граф имеет одну максимальную клику, треугольник {1,2,5}, и еще четыре максимальных клики, пары {2,3}, {3,4}, {4,5} и {4,6}. неориентированный граф образован конечным набором из вершин и набор неупорядоченных пар вершин, которые называются ребрами. По соглашению, при анализе алгоритмов количество вершин в графе обозначается n, а количество ребер обозначается m. Клика в графе G является полным подграфом графа G. То есть это подмножество K вершин, для каждые две вершины в K являются две конечные точки ребра которых в G. Максимальная клика - это клика, к которой больше нельзя добавить вершины. Для каждой вершины v, которая предотвращает добавление v к клике, должна быть другая вершина w, которая находится в клике и не является максимальной кликой. Максимальная клика - это клика, которая включает в себя возможное возможное количество вершин. Число кликов ω (G) - это количество вершин в максимальной клике изученной группы G.
Былоено несколько совместных задач поиска клик.
Первые четыре из этих проблем важны для практических приложений. Проблема решения клики не имеет практического значения; она сформулирована таким образом, чтобы применить теорию НП-полноты к задачам поиска кликов.
Проблема независимого множества друг от друга дополняет друг: клика в G независимым множеством дополнительным графе группы G и наоборот. Следовательно, многие результаты вычислений могут быть одинаково хорошо применены к любой проблеме, а в некоторых исследовательских работах не проводится четкого различия между двумя проблемами. Однако две проблемы имеют разные свойства при применении к ограниченным семействам графов. Например, проблема может быть решена за полиномиальное время для планарных графов, в то время как проблема остается сложной NP-сложной для плоских графов.
A максимальное клика, иногда называемая максимальной по включению, - это клика, не входящая в большую клику. Следовательно, каждая клика содержит в максимальной клике. Максимальные клики могут быть очень маленькими. Граф может содержать немальную клику с множеством вершин и отдельную клику размера 2, которая является максимальной. Хотя максимальная (т. Е. На наибольшая) клика обязательно максимальна, обратное неверно. Есть несколько типов графов, в максимальной максимальной клика максимальна; это дополнения к хорошо покрытым графам, в которых каждый максимальный набор максимален. Однако другие графы имеют максимальные клики, которые не являются максимальными.
Единственная максимальная скорость может быть найдена с помощью простого клика жадного алгоритма. Начиная с произвольной клики (например, любую отдельную вершину или даже пустого множества), увеличивайте текущую клику по одной вершине за раз, перебирая оставшиеся вершины графа. Для вершины v, которая исследует этот цикл, добавляет v к каждой вершине, если она уже находится в клике, и отбросьте v в случае. Этот алгоритм работает за линейное время. Из-за простоты поиска максимальных клик и их самого небольшого размера больше внимания было уделено гораздо более сложной алгоритмической проблемы поиска максимальной или иной большой клики, чем проблема поиска одной максимальной клики. Однако в некоторых исследованиях параллельных алгоритмов изучалась проблема поиска максимальной клики. В частности, проблема поиска лексикографически первой максимальной клики (найденной с помощью алгоритма выше) оказалась полной для класса функций с полиномиальным временем. Этот результат означает, что проблема вряд ли будет разрешима в рамках параллельного класса сложности NC.
Можно проверить, содержит ли граф G клику с k вершинами, и найти любую такую клику, которая содержит, используя алгоритм грубой силы. Этот алгоритм исследует каждый подграф с k вершинами и проверяет, образует ли он клику. Это занимает время O (n k), что выражается с помощью нотации большого O. Это потому, что нужно проверить O (n) подграфов, каждый из которых имеет O (k) ребер, наличие которых в G необходимо проверить. Таким образом, проблема может быть решена за полиномиальное время всякий раз, когда k является фиксированной константой. Однако, когда k не имеет фиксированного значения, но вместо этого может изменяться как часть входных данных для задачи, время является экспоненциальным.
Простейший нетривиальный случай поиска клики - это поиск треугольника в графике или, что то же самое, определение, является ли график без треугольников. В графе G с m ребрами может быть более (m) треугольников (с использованием большой тета-записи не, чтобы указать, что эта граница жесткая). Худший случай для этой формулы имеет место, когда G сама является кликой. Следовательно, алгоритмы для перечисления всех треугольников должны занимать по крайней мере Ω (м) время в худшем случае (с использованием нотации большого омеги ), и известны алгоритмы, которые соответствуют этой временной границе. Например, Chiba Nishizeki (1985) описывают алгоритм, который сортирует вершины в порядке наивысшей степени к наименьшей, а затем выполняет итерацию по каждой вершине v в отсортированном списке, ища треугольники, которые включают v и не включают включить любую предыдущую вершину в список. Для этого алгоритма помечает всех соседей v, просматривает все ребра, инцидентные соседние v, выводя треугольник для каждого ребра, имеющего две конечные точки, удаляет метки и удаляет v из графа. Как показывают авторы, время для этого алгоритма пропорционально графа (обозначается a (G), умноженной на количество ребер, которое равно O (m a (G)). Древовидность древовидность не превосходит O (m), этот алгоритм работает за время O (m). В более общем смысле, все клики с k вершинами могут быть с помощью одного алгоритма, который требует времени, умноженному количеству ребер, умноженному на древовидность в степени (k - 2). Для графов с постоянной древовидностью, таких как планарные графы (или вообще графы из любого нетривиального семейства второстепенных замкнутых графов ) этот алгоритм занимает время O (m), что является оптимальным, поскольку он линейен по размеру входных данных.
Если нужен только один треугольник или гарантия, что график не содержит треугольников, возможны более быстрые алгоритмы. Как отмечают Itai Rodeh (1978), граф содержит треугольник тогда и только тогда, когда его матрица взаимосвязей и квадратные матрицы, содержащие ненулевые элементы в одной и той же ячейке. Следовательно, методы быстрого матричного умножения, такие как алгоритм Копперсмита - Винограда, могут правила для поиска треугольников за время O (n). Алон, Юстер и Цвик (1994) использовали быстрое матричное умножение для улучшения алгоритма O (m) для поиска треугольников до O (m). Эти алгоритмы, основанные на быстром умножении матриц, также были расширены для поиска задач k-клик для больших значений k.
По результатам Moon Moser (1965), каждый граф с n вершинами имеет не более 3 максимальных клик. Их можно перечислить с помощью ма Брона - Кербоша, рекурсивной процедуры обратного алгоритма из Bron Kerbosch (1973). Основная рекурсивная подпрограмма этой имеет три аргумента: частично построенную (не максимальную) клику, набор вершин процедур кандидатов, которые добавлены в клику, и другой набор вершин, которые не следует добавлять (потому что это приведет к в уже найденную клику). Алгоритм пытается добавить вершины-кандидаты одну за другой в частичную клику, выполняя рекурсивный вызов для каждой из них. После проверки каждой из этих вершин он перемещает ее в набор вершин, которые больше не нужно сообщений. Можно показать, что варианты этого алгоритма имеют время работы O (3) в наихудшем случае, количеству кликов, которые, возможно, потребуется указать. Следовательно, это обеспечивает наихудшее оптимальное решение проблемы перечисления всех максимальных клик. Кроме того, широко сообщалось, что алгоритм Брон-Кербоша на практике работает быстрее, чем его альтернативы.
Однако, когда количество клик значительно меньше, чем в худшем случае, другие алгоритмы могут быть предпочтительнее. Как Tsukiyama et al. (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 - количество вершин. Chiba Nishizeki (1985) улучшают это до O (ma) на клику, где a - древовидность данного графа. Макино и Уно (2004) предлагают альтернативный алгоритм, чувствительный к выходу, основанный на быстром умножении матриц. Johnson Yannakakis (1988) показывают, что можно даже перечислить все максимальные клики в лексикографическом порядке с полиномиальной задержкой на клику. Однако выбор порядка важен для эффективности этого алгоритма: для обратного этого порядка не существует алгоритма с полиномиальной задержкой, если P = NP.
На основе этого результата можно перечислите все максимальные клики за полиномиальное время для семейств графов, в которых количество клик полиномиально ограничено. Эти семейства включают хордовые графы, полные графы, графы без треугольников, интервальные графы, графы ограниченной прямоугольности <248.>и планарные графы. В частности, планарные графы имеют O (n) клик не более постоянного размера, которые могут быть перечислены за линейное время. То же самое верно для любого семейства графов, которое является как разреженным, (имеющимколичество ребер, не превышающее константу, умноженную на количество вершин), так и закрытым при операции взятия подграфов.
Можно найти максимальную клику или кликовое число произвольного n-вершинного графа за время O (3) = O (1.4422) используя один из вышеупомянутых алгоритмов, чтобы перечислить все максимальные клики в графе и вернуть самую большую. Однако для этого варианта проблемы клики возможны лучшие временные рамки для наихудшего случая. Алгоритм Tarjan Trojanowski (1977) решает эту проблему за время O (2) = O (1.2599). Это рекурсивная схема вызова обратного вызова, аналогичная схема алгоритма Брона - Кербоша, но можно исключить некоторые рекурсивные, когда можно показать, что клики, обнаруженные в вызове, будут неоптимальными. Цзянь (1986) улучшил время до O (2) = O (1,2346), а Робсон (1986) улучшил его до O (2) = O (1,2108), при счет большего использования пространства. Алгоритм Робсона сочетает в себе аналогичную схему поиска с возвратом (с более сложным анализом случаев) и технику >, в которой оптимальное решение вычисляется для всех малых связанных подграфов дополнительного графа. Эти частичные решения используются для сокращения рекурсии с возвратом. Самый быстрый алгоритм, известный сегодня - это усовершенствованная версия этого метода, разработанная Робсоном (2001), который работает за O (2) = O (1.1888).
Также были проведены обширные исследования эвристические алгоритмы для решения проблем с максимальным числом кликов без выполнения наихудшего случая, основанные на таких методах, как ветвление и граница, локальный поиск, жадные алгоритмы и программирование в ограничениях. Нестандартные вычислительные методологии, которые были предложены для поиска клик, включают ДНК-вычисление и адиабатическое квантовое вычисление. Проблема максимальной клики была предметом задачи реализации, спонсируемой DIMACS в 1992–1993 годах, и общедоступного набора графиков, используемых в качестве эталонов для этой задачи.
В этом графе перестановок максимальные клики соответствуют наиболее длинным убывающим подпоследовательностям (4,3,1) и (4,3,2) определяющую перестановки. Планарные графы и другие семейства разреженных графов обсуждались выше: они линейно много максимальных клик ограниченного размера, которые могут быть за линейное время. В частности, для плоских графов любая клика может иметь не более четырех вершин по теореме Куратовского.
Совершенные графы определенным тем своимством, что их число клики равно их хроматическому этому, и что это равенство выполняется также в каждом из их индуцированных подграфов. Для идеальных графов можно найти максимальную клику за полиномиальное время, используя алгоритм, основанный на полуопределенном программировании. Однако этот метод сложный и не является комбинаторным, и для многих подклассов совершенных графов были разработаны специализированные алгоритмы поиска клик. В дополнительных графах из двудольных графов, теорема Кенига позволяет достичь максимальной клики с использованием методов сопоставления. В другом классе совершенных графов, графах перестановок, максимальная клика является самой длинной убывающей подпоследовательностью перестановки, определяющей граф, и может быть найдена с использованием алгоритмов самой длинной убывающей подпоследовательности.. И наоборот, каждый случай самой длинной проблемы может быть описан эквивалентно как проблема поиска максимальной клики в графе перестановок. Even, Pnueli Lempel (1972) предоставляет альтернативный квадратичный алгоритм для достижения клики в графах сопоставимости, более широкого класса совершенных графов, который включает графы перестановок как частный случай. В хордовых графах максимальные клики можно найти, перечислив вершины в порядке исключения и проверив клику найти добавлений каждой вершины в этом порядке.
В некоторых случаях эти алгоритмы могут быть расширены и другие несовершенные классы графов. Например, в круговом графе добавление каждой вершины является графом перестановок, поэтому максимальную клику в круговом графе можно найти, применяя алгоритм графа перестановок к каждой окрестности. Аналогично, в единичном дисковом графе (с геометрическим представлением) алгоритм с полиномиальным временем для максимальных клик, основанный на применении алгоритма дополнений двудольных графов к общим группам пар вершин.
Алгоритмическая проблема поиска максимальной клики в случайном графе, взятом из модели Эрдеша - Реньи (в которой каждое ребро проявляется с вероятностью 1/2, независимо от других краев) был предложен Карпом (1976). Максимальный клика в случайном графе имеет максимальный размер с высокой вероятностью, ее можно найти путем перебора в ожидаемое время 2. Это квазиполиномиальная временная граница. Хотя число кликов таких графов обычно очень близко к 2 log 2 n, простые жадные алгоритмы, а также более сложные методы рандомизированной аппроксимации находят только клики с размером log 2. сущ., Вдвое меньше. Количество максимальных клик в таких графах с высокой вероятностью экспоненциально в logn, что не позволяет методам, перечисляющим все максимальные клики, работать за полиномиальное время. Из-за этой проблемы несколько авторов исследовали проблему установленной клики, проблему клики на случайных графах, которые были увеличены за счет добавления больших клик. В то время как спектральные методы и полуопределенное программирование могут обнаруживать скрытые клики размера Ω (√n), в настоящее время не известны алгоритмы полиномиального времени для обнаружения клик размера o (√n) ( выраженные с помощью небольшой нотации ).
Несколько авторов рассмотрели алгоритмы который аппроксимации, которые пытаются найти клику или независимый набор, хотя и не максимальным, имеет размер как Можно ближе максимума, которая не имеет смысла для дополнительных кликов, также есть работа над алгоритмами приближения, которые не используют такие предположения разреженности.
Feige (2004) имеет алгоритм полиномиального времени, который находит клику размера Ω ((log n / log log n)) в любом графе, который имеет номер клики Ω (n / logn) для любого константа k. Используя этот алгоритм, когда кликовое число заданного входного графа находится между n / log n и n / logn, sw желая использовать другой алгоритм Boppana Halldórsson (1992) для графов с более высокими номерами кликов, и выбирая клику с двумя вершинами, если оба алгоритма ничего не находят, Фейдж обеспечивает приближение алгоритма, который находит клику с числом вершин в пределах множителя O (n (log log n) / logn) от максимума. Хотя коэффициент приближения этого алгоритма слабым, на сегодняшний день он является наиболее известным. Результаты по жесткости приближения, описанные ниже, предполагают, что не может быть никакого алгоритма аппроксимации с коэффициентом аппроксимации, значительно меньшим, чем линейный.
Экземпляр удовлетворяемости 3-CNF (x ∨ x ∨ y) ∧ (~ x ∨ ~ y ∨ ~ y) ∧ (~ x ∨ y ∨ y) сводится к Clique. Зеленые вершины образуют 3-клику и соответствуют удовлетворительному назначению. Проблема решения клики: НП-полная. Это была одна из оригинальной 21 задачи Ричарда Карпа, показанной NP-полной в его статье 1972 года «Сводимость среди комбинаторных проблем». Эта проблема также упоминалась в статье Стивена Кука, вводящей теорию NP-полных задач. Из-за сложности решения проблема поиска максимальной клики также является сложной NP-сложной. Если бы можно было ее решить, можно было бы решить проблему Решение, сравнивая размер максимального клика с параметром размера, заданным в качестве входных данных в задаче решения.
Доказательство NP-полноты Карпа является редукцией из булевой задачи выполнимости. В нем описывается, как преобразовать булевы формулы в конъюнктивной нормальной форме (CNF) в эквивалентные примеры максимальной клики. Выполнимость, в свою очередь, была доказана NP-полная в теореме Кука - Левина. Из заданной формулы CNF Карп формирует граф, у которого есть вершина для каждой пары (v, c), где v - переменная или ее отрицание, а c - часть формулы, содержащая v. Две из этих вершин соединены ребро, если они содержат совместимые присвоения количество для разных предложений. То есть, есть ребро от (v, c) до (u, d), когда c ≠ d и u и v не имеют отрицаний друг друга. Если k обозначает количество пунктов в формуле CNF, то клики с k вершинами в этом графе обеспечивают последовательные способы присвоения значений истинности некоторые из его числа, чтобы удовлетворить формулу. Следовательно, формула выполнима тогда и только тогда, когда существует k-вершинная клика.
Некоторые NP-полные задачи (например, задача коммивояжера в планарных графах ) может быть решена за время, которое является экспоненциальным в сублинейной функции входного проекта размера n, что значительно быстрее, чем поиск методом грубой силы. Однако маловероятно, что такая субэкспоненциальная временная граница возможна для проблем в произвольных графах, поскольку она подразумевает аналогичные субэкспоненциальные границы для многих других стандартных полных задач.
наличие Монотонная схема для обнаружения k-клики в графе с n вершинами для k = 3 и n = 4. Каждый вход в схему кодирует или отсутствие определенного (красного) ребра в графе. Схема использует один внутренний логический элемент и обнаружение каждой потенциальной k-клики. Вычислительная сложность этой задачи клики к привела, что ее использовали для нескольких нижних границ в схемы. Существование клики данного размера - это означает, что она будет существовать в любом суперграфе. Чтобы решить проблему принятия решений о клике для данного фиксированного размера клики, это свойство является существующим существующим монотонным механизмом, использующим только элементы и элементы и или элементы. Однако можно доказать, что размер этой схематической суперполиномиальной функции количества вершин и размера клики, экспоненциальной от кубического корня из числа вершин. Даже если разрешено небольшое количество элементов НЕ, сложность остается суперполиномиальной. Кроме того, используется глубина монотонной схемы для задач клики, использующая вентиль с ограниченным разветвлением на входе, должна быть по крайней мере полиномом от размера клики.
Простое дерево решений для обнаружения наличия 3-клики в 4-вершинном графе. В нем используется до 6 вопросов типа «Существует ли красный край?», Соответствующих оптимальной границе n (n - 1) / 2. (детерминированная) сложность дерева решений определения свойство графа - это количество вопросов вида «Есть ли ребро между вершиной u и вершиной v?» на которые нужно ответить в худшем случае, чтобы определить, обладает ли граф определенным свойством. То есть это минимальная высота логического дерева решений для проблемы. Можно задать n (n - 1) / 2 возможных вопроса. Следовательно, любое свойство графа может быть определено с помощью не более n (n - 1) / 2 вопросов. Также можно определить сложность случайного и квантового дерева решений свойства, ожидаемое количество вопросов (для входных данных наихудшего случая), на которые должен ответить рандомизированный или квантовый алгоритм, чтобы правильно определить, имеет ли данный граф свойство.
Поскольку свойство содержать клику является монотонным, оно покрывается гипотезой Андераа – Карпа – Розенберга, которая утверждает, что сложность детерминированного дерева решений для определения любого нетривиального монотонного Свойство графа равно n (n - 1) / 2. Для произвольных свойств монотонного графа эта гипотеза остается недоказанной. Однако для детерминированных деревьев решений и для любого k в диапазоне 2 ≤ k ≤ n было показано, что свойство содержать k-клику имеет сложность дерева решений ровно n (n - 1) / 2 Боллобасом ( 1976). Детерминированные деревья решений также требуют экспоненциального размера для обнаружения клик или большого полиномиального размера для обнаружения клик ограниченного размера.
Гипотеза Андераа – Карпа – Розенберга также утверждает, что сложность рандомизированного дерева решений нетривиальных монотонных функций равна Θ (п). Гипотеза снова остается недоказанной, но была разрешена для свойства содержать k клику при 2 ≤ k ≤ n. Известно, что это свойство имеет рандомизированную сложность дерева решений Θ (n). Для квантовых деревьев решений наиболее известной нижней границей является Ω (n), но для случая k ≥ 3 не известен алгоритм сопоставления.
Параметризованная сложность - это Теоретическая сложность исследование задач, которые естественным образом снабжены малым целочисленным параметром k и для которых проблема становится более сложной с увеличением k, например, поиск k-клик в графах. Задача называется решаемой с фиксированными параметрами, если существует алгоритм для ее решения на входах размера n и функция f, такая, что алгоритм выполняется за время f (k) n. То есть ее можно решить с фиксированным параметром, если ее можно решить за полиномиальное время для любого фиксированного значения k и, более того, если показатель степени полинома не зависит от k.
Для поиска клик с k вершинами, алгоритм поиска методом перебора имеет время работы O (nk). Показатель степени n зависит от k, этот алгоритм не является управляемым с фиксированными параметрами. Хотя его можно улучшить с помощью быстрого умножения матриц, время выполнения по-прежнему имеет экспоненту, линейную по k.Таким образом, хотя время выполнения алгоритмов для задач клики является полиномиальным для любого фиксированного k, этих алгоритмов недостаточно для фиксированного сговорчивость. Дауни и Товарищи (1995) определили иерархию параметризованных задач, иерархию W, которая, по их предположениям, не управляемые алгоритмов с фиксированными функциями. Они доказали, что то же самое, клика сложно для первого уровня этой иерархии, W [1]. Таким образом, согласно их гипотезе, у клики нет алгоритма с фиксированными опасностями. Этот продукт служит для использования в качестве доказательства W [1] -твердости многих других способов, аналогом теоремы Кука - Левина для параметризованной сложности.
Чен и др. (2006) показал, что поиск k-вершинных клик не может быть выполнен за время n, если только гипотеза экспоненциального времени не сработает. Опять же, это свидетельствует о том, что никакой управляемый алгоритм с фиксированными невозможен.
Хотя проблемы перечисления максимальных кликов или нахождения максимальных клик вряд ли решатся с фиксированным параметром, управляемым параметром, они могут быть управляемыми с фиксированными параметрами для других параметров сложности экземпляра. Например, известно, что обе проблемы решаемы с фиксированными параметрами, если параметры вырождены входного графа.
График отношений совместимости между 2-битными образцами 3-битных строк доказательства. Каждая максимальная клика (треугольник) на этом графике представляет все способы выбора одной 3-битной строки. Доказательство невозможности аппроксимации проблемы включает индуцированные подграфы аналогичным образом графов для большего числа битов. Слабые результаты, намекающие на то, что проблема клики может быть трудно аппроксимировать, были известны давно. Garey Johnson (1978) заметили, что из-за того, что кликовое число принимает малые целые значения и NP-сложно вычислить, оно не может иметь полностью схему аппроксимации с полиномиальным временем. Если бы было слишком точное число приближение, округление его значения до целого числа дало бы точное число клики. Однако мало что было известно до начала 1990-х годов, когда несколько авторов начали устанавливать связь между приближением максимальных клик и вероятностно проверяемых доказательств. Они использовали эти связи, чтобы доказать трудность аппроксимации результатов для задачи о максимальной клике. После многих улучшений этих результатов теперь известно, что для каждого действительного числа ε>0 не может быть алгоритма полиномиального времени, который аппроксимирует максимальную клику с точностью до множителя лучше, чем O (n), если только P = NP.
Грубая идея этих результатов несовместимости в том, чтобы сформировать граф, представляющий систему вероятностно проверяемых доказательств для NP-полной проблемы, такая как проблема логической выполнимости. В вероятностно проверяемой системе доказательств доказательства битов. Экземпляр проблемы выполнимости должен иметь действительное доказательство тогда, когда оно выполнимо. Доказательство проверяет алгоритмом, который после вычислений за полиномиальное время выполнения задачи выполняет выбор для проверки небольшое количество случайно выбранных позиций доказательства. В этой выборке битов имеются значения, которые могут быть проверены, либо проверены, либо отклонены от других битов. Ложноотрицательные результаты не допускаются: всегда приниматься доказательство. Однако иногда может быть ошибочно принято недействительное доказательство. Для каждого недействительного доказательства того, что проверяющий его примет, должна быть низкой.
Чтобы преобразовать вероятностно проверяемую систему доказательств этого типа в проблеме клики, нужно сформировать граф с вершиной для каждого возможного принимающего прогона. средства проверки. То есть вершина определяется одним из проверяющих выборов наборов для проверки и битовыми значениями для тех позиций, которые заставили бы проверяющую принять доказательство. Он может быть представлен частичным словом с 0 или 1 в каждой исследуемой позиции и символом подстановки в каждой оставшейся позиции. В этом графе две вершины являются соответствующими, если соответствующие две принимающие серии видят одинаковые битовые значения в каждой позиции, которые они исследуют. Действующая или недействительная строка доказательства соответствует клике, набору принимающих прогонов, которые видят эти доказательства, и все максимальные клики проходят таким образом. Одна из этих клик велика тогда и только тогда, когда она проверяет доказательства, принимает многие средства проверки. Если будет принят все исходные доказательства, выполненные экземпляром. Однако, если исходный экземпляр не является выполненным, тогда все строки доказательства не исполняемой, каждая строка доказательства только небольшое количество запусков программы проверки, которые ошибочно принимают ее, и все клики небольшие. Следовательно, если бы можно было проводить полиномиальное различие между графами, имеющими большие клики и графами, в которых все клики малы, или если бы можно было точно аппроксимировать проблему кликов, то применение этого приближения к графам, созданным из экземпляров выполнимости, выполненным экземпляры отличать от неудовлетворительных случаев. Однако это невозможно, если P = NP.
