Проблема Клика на фиксированных графах

Как известно, -clique функция принимает ( охватывающий ) подграф полного -vertex графа и выходов тогда и только тогда содержит -clique . Переменные в этом случае соответствуют краям от . Известно (Разборов, Алон-Боппана), что для эта функция требует монотонных схем размером около . $k$G ⊆ K n n K n 1 G k K n 3 ≤ k ≤ n / 2 n $CLIQUE(n,k)$$G\subseteq K_n$$n$$K_n$$1$$G$$k$$K_n$$3\leq k\leq n/2$$n^k$

Но что, если мы возьмем один фиксированный граф и рассмотрим монотонную булеву функцию , которая принимает подмножество вершин и выдает если некоторые вершин в образуют a кликать в . Переменные в этом случае соответствует вершинам из и функции только стандартная функция клики , но ограничиваются затягивающими подграфами один фиксированный графом .$G\subseteq K_n$$CLIQUE(G,k)$$S\subseteq [n]$$1$$k$$S$K n$G$$K_n$$G$

1. Существуют ли вершинные графы для которых требуются монотонные схемы размером больше ? Я думаю - НЕТ. G C L I Q U E ( G , k ) n O ( log n $n$$G$$CLIQUE(G,k)$$n^{O(\log n)}$

2. Является ли NP-трудной задачей для некоторой последовательности графов ? Я думаю - НЕТ. ( G n : n = 1 , 2 … $CLIQUE(G_n,k)$$(G_n\colon n=1,2\ldots)$

Обратите внимание, что если - все максимальные клики в , то может быть вычислено как OR для пороговых функций , из которых проверяет, . Таким образом, если , то вся схема имеет полиномиальный размер. Но как насчет графов с экспоненциальным числом максимальных кликов? (Клика максимальна, если к ней нельзя добавить вершину.) G C L I Q U E ( G , k ) r k i | S a ∩ C i | ≥ k r = p o l y ( n $C_1,\ldots,C_r$$G$$CLIQUE(G,k)$$r$$k$$i$$|S_a\cap C_i|\geq k$$r=poly(n)$

Можно «внедрить» в для конкретного графа на вершинах. В частности, Боллобас и Томасон (1981) показали, что если - граф Адамара, вершинами которого являются подмножества в , а две вершины и смежны тогда только тогда, когдачетно, то содержит изоморфную копию каждого графа на вершинах. Можно ли объединить этот факт с нижней границей Разборова (около ) для чтобы сделать вывод, что C L I Q U E ( Н , к ) H n = 2 $CLIQUE(m,k)$$CLIQUE(H,k)$$H$$n=2^m$[ m ] u v | u ∩ v | H G m m k C L I Q U E ( м , k ) C L I Q U E ( H , k $H$$[m]$$u$$v$$|u\cap v|$$H$$G$$m$$m^k$$CLIQUE(m,k)$$CLIQUE(H,k)$ требует монотонных схем размером около ? Потенциальная проблема здесь заключается в том, что, хотя граф «содержит» все вершинные графы, эти графы не находятся на одном и том же наборе вершин. А аргумент Разборова требует, чтобы положительные и отрицательные входы ( клики и дополнения полных -частичных графов) были графами на одном и том же наборе вершин. Более того, все положительные входы ( клики) являются просто изоморфными копиями одного и того же фиксированного клика.$m^k$$H$ $m$( к - 1 $k$$(k-1)$$k$ $k$

3. Есть идеи? Кто-нибудь видел такие проблемы, которые рассматриваются? Я имею в виду решение задач для подграфов фиксированного графа. Или, скажем, проблема SAT для суб-CNF одного фиксированного (выполнимого) CNF (полученного путем удаления некоторых литералов)?

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

Замечание 1: Если граф является двудольным , то матрица инцидентности ребро-вершина неравенств для всех полностью унимодулярна и можно решить задачу клика на индуцированных подграфах помощью линейного программирования. Таким образом, для двудольных графов , имеет небольшую (хотя и не-монотонной) цепи. x u + x v ≤ 1 ( u , v ) ∉ E G G C L I Q U E ( G , k $G=(L\cup R,E)$$x_u+x_v\leq 1$$(u,v)\not\in E$$G$$G$$CLIQUE(G,k)$

Замечание 2: Указание на то, что в случае двудольных графов ответ на вопрос 1 «должен» действительно быть НЕТ, заключается в том, что следующая монотонная игра Карчмера-Вигдерсона на требует только битов связи. Пусть наибольшее число вершин в полном двудольный подграф . Алиса получает набор красных узлов , а Боб набор голубых узлов таких что . Цель состоит в том, чтобы найти некраевой между и .G O ( log n ) k G A B | A | + | Б | > k A $G$$G$$O(\log n)$$k$$G$$A$$B$$|A|+|B|>k$$A$$B$

Мы провели некоторое исследование проблемы доказательства в древовидном разрешении, имеет ли фиксированный граф клику размера (где обычно мало). В частности, мы обнаружили, что опровержения размера необходимы для большого класса графов.k k n Ω ( k $G$$k$$k$$n^{\Omega(k)}$

Вы можете найти документ « Параметризованная сложность процедур поиска DPLL» по этой ссылке .

Я полагаю, что этот документ может ответить на ваши вопросы: http://arxiv.org/abs/1204.6484

В статье определены семейства задач NP hard 3SAT, так что структура формулы фиксирована для каждого n, а входной сигнал является полярностью формулы.

Используя стандартное сокращение от 3SAT до CLIQUE (каждое предложение 3CNF определяет набор из 8 возможных назначений (или 7 удовлетворяющих назначений) с ребрами между не конфликтующими назначениями), существует такой график, что после удаления одной вершины для каждого предложения это NP трудно найти максимальную клику (или даже приблизить ее размер, используя графические продукты или дерандомизированные графовые продукты)

Что касается Q3, то есть некоторая эмпирическая работа по «остову» и возможным «бэкдорам» проблем SAT. Магистраль - это набор литералов, которые верны в каждом удовлетворительном задании. Бэкдор в проблему SAT - это (надеюсь, небольшой) набор переменных, которые обеспечивают «короткий путь» в решении проблемы. Эти две структуры, вероятно, будут полезны и / или ключом к пониманию того, что вы называете «суб-CNF» или CNF с удалением некоторых переменных. но также и DP, алгоритм Дэвиса Патнама можно рассматривать как систематическое исследование многих «суб-CNF» CNF для его решения.

[1] Основы и бэкдоры в соответствии с Kilby et al.