Твердость параметризованной CLIQUE?

17

Пусть 0p1 и рассмотрим решение задачи

CLIQUE Ввод: целое числоp
s , граф G с t вершинами и края Вопрос: действительно содержит клику по крайней мере вершинами?p(t2)
Gs

Экземпляр CLIQUE содержит пропорцию от всех возможных ребер. Ясно, что CLIQUE легко для некоторых значений . CLIQUE содержит только полностью отключенные графы, а CLIQUE содержит полные графы. В любом случае CLIQUE может быть определено за линейное время. С другой стороны, для значений близких к , CLIQUE является NP-трудной по сокращению от самой CLIQUE: по существу, достаточно взять несвязное объединение с графом Турана ,pppp01pp1/2p T(t,s1)

Мой вопрос:

Является ли CLIQUE в PTIME или NP-полной для каждого значения ? Или есть значения для которых CLIQUE имеет промежуточную сложность (если P ≠ NP)?pppp

Этот вопрос возник из смежного вопроса для гиперграфов, но сам по себе он кажется интересным.

Андраш Саламон
источник
1
интересный вопрос!
Суреш Венкат
Является ли pa действительным числом от 0 до 1, или p может быть функцией от t?
Робин Котари
@ Робин: Я не уточнил, оба были бы интересны.
Андрас Саламон
3
Если доля ребер является верхней границей (а не требованием точного подсчета или нижней границей), то для любой константы эта проблема является NP-трудной путем сокращения из CLIQUE: добавьте достаточно большой набор изолированных вершин , Требуется ли, чтобы число ребер было равно заданному выражению? Или что за очевидную вещь мне не хватает? :-)0<p<1
gphilip
1
@gphilip: Как вы указали, сокращение происходит немедленно, если пропорция является только верхней границей; Вот почему вопрос сформулирован с точки зрения точной пропорции.
Андрас Саламон

Ответы:

14

Я предполагаю, что число в определении задачи CLIQUEpточно равно числу ребер в графе, в отличие от комментария gphilip к вопросу.п(T2)

Задача CLIQUE p является NP-полной для любой рациональной константы 0 < p <1 путем сокращения от обычной задачи CLIQUE. (Предположение, что p рационально, требуется только для того, чтобы можно было вычислить из N за время от полинома от N. )пN

Пусть k ≥3 - целое число, удовлетворяющее как k 2 ≥1 / p, так и (1−1 / k ) (1−2 / k )> p . Для графа G с n вершинами и m ребрами вместе с пороговым значением s редукция работает следующим образом.

  1. Если s < k , мы решаем задачу CLIQUE за время O ( n s ). Если есть клика размером не менее s , мы создаем фиксированный экземпляр yes. В противном случае мы производим фиксированный no-instance.
  2. Если n < s , мы создаем фиксированный no-instance.
  3. Если nsk , мы добавляем в G a ( k −1) -двойственный граф, где каждое множество состоит из n вершин, которые имеют точно ребер, иполучимэтот граф.п(NК2)-м

Обратите внимание, что случай 1 занимает время O ( n k −1 ), которое является полиномиальным от n для каждого p . Случай 3 возможен потому, что если nsk , то неотрицательна и непревосходитчисла ребер в полном (k−1) -раздельном графе Kn,…,n,как показано в следующих двухпунктахформулы изобретения.п(NК2)-м

П.1 . .п(NК2)-м0

Доказательство . Поскольку достаточно доказатьp ( nk)м(N2) или, что то же самое,pnk(nk −1) ≥n(n −1). Посколькуp≥ 1 /k2, имеемpnk(nk −1) ≥n(n −1 /k) ≥n(n −1). КЕД.п(NК2)(N2)

П.2 . . (Обратите внимание, что правая часть - это число ребер в полном (k − 1) -раздельном графе Kn,…,n.)п(NК2)-м<N2(К-12)

Доказательство . Поскольку и m ≥ 0, достаточно доказать p ( n kИкс<Икс+1п(NК2)+1N2(К-12)

N2(К-1)(К-2)-пNК(NК-1)-2
N2(К-1)(К-2)-N(N-1К)(К-1)(К-2)-2
знак равноNК(К-1)(К-2)-2(К-1)(К-2)-20.

Редактировать : в Редакции 1 произошла ошибка; иногда требовался граф с отрицательным числом ребер (когда p было маленьким). Эта ошибка исправлена.

Цуёси Ито
источник
это ближе всего к конкретной фразе, так что спасибо за решение. Случай 3 наиболее близок к тому, что я имел в виду. Однако я не слежу за расчетами - не могли бы вы немного расширить?
Андрас Саламон
@ Андрас Саламон: Готово.
Цуёси Ито
15

пTпжурнал4Tsжурнал2TTжурнал2T

журнал2T

п

Боаз Барак
источник