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

21

Как известно, -clique функция принимает ( охватывающий ) подграф полного -vertex графа и выходов тогда и только тогда содержит -clique . Переменные в этом случае соответствуют краям от . Известно (Разборов, Алон-Боппана), что для эта функция требует монотонных схем размером около . kG K n n K n 1 G k K n 3 k n / 2 n kCLIQUE(n,k)GKnnKn1GkKn3kn/2nk

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

1. Существуют ли вершинные графы для которых требуются монотонные схемы размером больше ? Я думаю - НЕТ. G C L I Q U E ( G , k ) n O ( log n )nGCLIQUE(G,k)nO(logn)
2. Является ли NP-трудной задачей для некоторой последовательности графов ? Я думаю - НЕТ. ( G n : n = 1 , 2 )CLIQUE(Gn,k)(Gn:n=1,2)

Обратите внимание, что если - все максимальные клики в , то может быть вычислено как OR для пороговых функций , из которых проверяет, . Таким образом, если , то вся схема имеет полиномиальный размер. Но как насчет графов с экспоненциальным числом максимальных кликов? (Клика максимальна, если к ней нельзя добавить вершину.) G C L I Q U E ( G , k ) r k i | S aC i | k r = p o l y ( n )C1,,CrGCLIQUE(G,k)rki|SaCi|kr=poly(n)

Можно «внедрить» в для конкретного графа на вершинах. В частности, Боллобас и Томасон (1981) показали, что если - граф Адамара, вершинами которого являются подмножества в , а две вершины и смежны тогда только тогда, когдачетно, то содержит изоморфную копию каждого графа на вершинах. Можно ли объединить этот факт с нижней границей Разборова (около ) для чтобы сделать вывод, что C L I Q U E ( Н , к ) H n = 2 мCLIQUE(m,k)CLIQUE(H,k)Hn=2m[ 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]uv|uv|HGmmkCLIQUE(m,k)CLIQUE(H,k) требует монотонных схем размером около ? Потенциальная проблема здесь заключается в том, что, хотя граф «содержит» все вершинные графы, эти графы не находятся на одном и том же наборе вершин. А аргумент Разборова требует, чтобы положительные и отрицательные входы ( клики и дополнения полных -частичных графов) были графами на одном и том же наборе вершин. Более того, все положительные входы ( клики) являются просто изоморфными копиями одного и того же фиксированного клика. чmkH m( к - 1 )k(k1)k k

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

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

Замечание 1: Если граф является двудольным , то матрица инцидентности ребро-вершина неравенств для всех полностью унимодулярна и можно решить задачу клика на индуцированных подграфах помощью линейного программирования. Таким образом, для двудольных графов , имеет небольшую (хотя и не-монотонной) цепи. x u + x v1 ( u , v ) E G G C L I Q U E ( G , k )G=(LR,E)xu+xv1(u,v)EGGCLIQUE(G,k)

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

Стасис
источник
Дополнительные мысли (1) кажется, что вы могли бы получить аналогичный результат, определяя функцию «фильтра», которая имеет то же число переменных, что и ребра, и «фильтрует» ребра фиксированного графа на основе значений булевых переменных 0/1 ... .? это может несколько уменьшить анализ из-за индуцированной конструкции графа, которая перемещается от ребер к вершинам. (2) ключевой более простой вопрос встроен в ваш вопрос, который стоит рассмотреть один. Какие графы с экспоненциальной максимальной кликой? примера Хадамара может не хватить, потому что он такой «большой».
vzn
недавно изучал что-то неопределенно похожее и наткнулся на этот интересный фактоид: «Жадная клика разложения графа получается путем удаления максимальных клик из графа один за другим, пока граф не опустеет. Недавно мы показали, что любая жадная клика разложения график порядка имеет не более 2/4 кликов. " --mcguinnessп 2 / 4nn2/4
vzn
@vzn: к твоему последнему вопросу. Есть простая конструкция (не помню кого). Возьмите копии непересекающихся вершин "анти-треугольников" (тройки вершин без ребер между ними), и поместите ребра между всеми вершинами любых двух анти-треугольников. Число максимальных кликов тогда равно , и это оптимально (больше невозможно). 2 н / 3n/32n/3
Стасис
@vzn: о результате McGuinness. Как я понял, он разбивает все ребра на небольшое количество кликов, не пересекающих ребра (размер). Но может случиться так, что максимальный клик индуцированного подграфа не лежит ни в одном из них. Тем не менее, результат, кажется, в «правильном направлении».
Стасис
О замечании 2 : когда вы говорите, что ищете клику в двудольном, вы имеете в виду полный двудольный?
MassimoLauria

Ответы:

10

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

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

MassimoLauria
источник
1
Очень хороший результат! На самом деле, мой вопрос возник при попытке показать тот же результат для опровержений древовидной плоскости резания (CP) для задачи (клика). Для древовидных дериваций у нас есть два (только?) Инструмента: (1) аргументы сложности коммуникации и (2) игры с задержкой игрока в Pudlak и Impagliazzo. Замечание 2 подразумевает, что (1) не будет (доказуемо) потерпеть неудачу для проблемы Клика. Есть ли некоторая аналогия (2) в случае доказательств CP?
Стасис
6

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

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

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

user15669
источник
2

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

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

ВЗН
источник
Спасибо за ссылку! Действительно, эти две концепции, кажется, важны в решениях SAT. «Бэкдоры» в нашем случае соответствуют наборам переменных (= вершин), установка которых в 0/1 делает задачу клики простой. Если есть маленький (логарифмический) бэкдор , то у нас есть небольшая схема (просто путем попытки всех назначений для ). Но я признаю, что черные ходы велики для большинства графиков. SSS
Стасис