Пусть и рассмотрим решение задачи
CLIQUE Ввод: целое число
, граф с вершинами и края Вопрос: действительно содержит клику по крайней мере вершинами?
Экземпляр CLIQUE содержит пропорцию от всех возможных ребер. Ясно, что CLIQUE легко для некоторых значений . CLIQUE содержит только полностью отключенные графы, а CLIQUE содержит полные графы. В любом случае CLIQUE может быть определено за линейное время. С другой стороны, для значений близких к , CLIQUE является NP-трудной по сокращению от самой CLIQUE: по существу, достаточно взять несвязное объединение с графом Турана ,
Мой вопрос:
Является ли CLIQUE в PTIME или NP-полной для каждого значения ? Или есть значения для которых CLIQUE имеет промежуточную сложность (если P ≠ NP)?
Этот вопрос возник из смежного вопроса для гиперграфов, но сам по себе он кажется интересным.
источник
Ответы:
Я предполагаю, что число в определении задачи CLIQUEpточно равно числу ребер в графе, в отличие от комментария gphilip к вопросу.⌈ р ( т2) ⌉
Задача CLIQUE p является NP-полной для любой рациональной константы 0 < p <1 путем сокращения от обычной задачи CLIQUE. (Предположение, что p рационально, требуется только для того, чтобы можно было вычислить из N за время от полинома от N. )⌈ р Н⌉
Пусть k ≥3 - целое число, удовлетворяющее как k 2 ≥1 / p, так и (1−1 / k ) (1−2 / k )> p . Для графа G с n вершинами и m ребрами вместе с пороговым значением s редукция работает следующим образом.
Обратите внимание, что случай 1 занимает время O ( n k −1 ), которое является полиномиальным от n для каждого p . Случай 3 возможен потому, что если n ≥ s ≥ k , то неотрицательна и непревосходитчисла ребер в полном (k−1) -раздельном графе Kn,…,n,как показано в следующих двухпунктахформулы изобретения.⌈ p ( n k2) ⌉-м
П.1 . .⌈ p ( n k2) ⌉-m≥0
Доказательство . Поскольку достаточно доказатьp ( nk)м ≤ ( н2) или, что то же самое,pnk(nk −1) ≥n(n −1). Посколькуp≥ 1 /k2, имеемpnk(nk −1) ≥n(n −1 /k) ≥n(n −1). КЕД.p ( n k2) ≥ ( н2)
П.2 . . (Обратите внимание, что правая часть - это число ребер в полном (k − 1) -раздельном графе Kn,…,n.)⌈ p ( n k2) ⌉-m<n2( к-12)
Доказательство . Поскольку и m ≥ 0, достаточно доказать p ( n k⌈ x ⌉ < x + 1 p ( n k2) +1≤n2( к-12)
Редактировать : в Редакции 1 произошла ошибка; иногда требовался граф с отрицательным числом ребер (когда p было маленьким). Эта ошибка исправлена.
источник
источник