Параметризованная сложность от P до NP-хард и обратно

60

Я ищу примеры задач, параметризованных числом , где жесткость задачи немонотонна по k . Большинство проблем (по моему опыту) имеют один фазовый переход, например, k- SAT имеет один фазовый переход от k { 1 , 2 } (где проблема в P) к k 3 (где проблема NP- полный). Меня интересуют проблемы, в которых происходят фазовые переходы в обоих направлениях (от простого к сложному и наоборот) при увеличении k .kNkkk{1,2}k3k

Мой вопрос чем-то похож на вопрос, заданный в « Переходах твердости в вычислительной сложности» , и на самом деле некоторые ответы там относятся к моему вопросу.

Примеры, которые я знаю:

  1. k -цветность плоских графов: в P за исключением случаев, когдаk=3 , где NP-полная.
  2. Дерево Штейнера с терминалами: в P, когда k = 2 (сворачивается на кратчайший s - t путь) и когда k = n (сворачивается в MST), но NP-hard «между». Я не знаю, являются ли эти фазовые переходы резкими (например, P для k 0, но NP-hard для k 0 + 1 ). Кроме того, переходы k зависят от размера входного экземпляра, в отличие от моих других примеров.kk=2stk=nk0k0+1k
  3. Подсчет удовлетворяющих присвоений плоской формулы по модулю n : В P, когда n - простое число Мерсенна, n=2k1 , и # P-Complete для большинства (?) / Всех других значений n (от Аарона Стерлинга в этой теме ) , Много фазовых переходов!
  4. Индуцированное обнаружение подграфа: проблема не параметризована целым числом, а графиком. Существуют графы (где обозначает определенный вид отношения подграфа), для которых определяется, находится ли H iG для данного графа G в P для i { 1 , 3 }, но NP- завершено для i = 2 . (от Сянь-Чжи Чанга в той же теме ).H1H2H3HiGGi{1,3}i=2
mikero
источник
3
Незначительная коррекция по примеру (3): проблема в если n - целое число типа Мерсенна, т. Е. N = 2 k - 1 для некоторого натурального числа k ; п не должно быть простым. (Например, 2 11 - 1 не является простым.) Если n не имеет такой формы, проблема # P -полна. Pnn=2k1kn2111nP
Аарон Стерлинг
Спасибо Аарону Стерлингу - я исправил этот пример.
Микеро
1
Пример основной коррекции (3): формулы также должны быть монотонными, дважды читаемыми и иметь предложения размера , где n = 2 k - 1 , чтобы их можно было обрабатывать. Это доказали Джин-И Цай и Пиньян Лу. Это не то, как Valiant мотивировал это. Он установил размер предложения до 3, а затем изменил только модуль. Было известно, что оно является твердым по характеристике 0. Valiant показал твердость mod 2 и изменяемость mod 7. Твердость mod 2 равна P = # 2 P твердости, а не # P-твердости. Я не знаю, какую параметризованную семью проблем вы пытаетесь описать. kn=2k1P=#2P
Тайсон Уильямс
1
Подробнее об этом, включая ссылки на статью, см. Holographic_algorithm # History в Википедии.
Тайсон Уильямс
Беспокойство по поводу примера (4): Я надеюсь , что вы имеете в виду , что обозначим G быть реализация S -граф H . Но как мы можем сказать , что тета призма пирамида? Обратите внимание, что речь идет о индуцированных подграфах, а не о подграфах. HGGsH
Кириак Антоний

Ответы:

25

Одна область с большим количеством немонотонности сложности проблемы - это тестирование свойств. Пусть - множество всех n- вершинных графов, а P G n - свойство графа. Общая проблема состоит в том, чтобы определить, обладает ли граф G свойством P (т. Е. G P ) или «далек» от свойства P в некотором смысле. В зависимости от того, что представляет собой P и какой тип запроса у вас есть к графику, проблема может быть довольно сложной.GnnPGnGPGPPP

Но легко заметить, что проблема немонотонная: в том случае, если мы имеем , тот факт, что P легко тестируем, не означает, что S легко тестируемо или T таково . SPTPST

Чтобы убедиться в этом, достаточно заметить , что и P = оба тривиальным проверяемым, но для некоторых свойств, существуют сильные нижние границы.P=GnP=

Аарон Рот
источник
Не могли бы вы упомянуть (или указать на) нетривиальный пример? Я думаю, вы уже знаете некоторые. Интересно также, существуют ли фазовые переходы P NP P NP.
Кириак Антоний
20

Для данного графа и целого числа к 1 , в K -й мощности G , обозначаемой G к , имеет ту же самую вершину устанавливается так , что две различные вершины смежны в G к , если их расстояние в G не превосходит к . Задача k-й степени расщепленного графа спрашивает, является ли данный граф k -й степенью графа расщепления.Gk1kGGkGkGkkk

VB Le
источник
17

ΔΔ=23 Δ 6Δ73Δ6

Соответствующий вопрос обсуждается здесь .

Александр бондаренко
источник
14

Определение, имеет ли граф доминирующую клику для:G

  • diam(G)=1 тривиально - ответ всегда «да»
  • diam(G)=2 является NP-полным
  • diam(G)=3 является NP-полной
  • diam(G)4 тривиален - ответ всегда «нет»

Случай связан с Брандштадтом и Крачем , а случай отмечен в моей недавней статье .d i a m ( G ) = 2diam(G)=3diam(G)=2

Остин Бьюкенен
источник
+1 Хороший ответ. Какая доминирующая клика?
Мухаммед Аль-Туркистани
1
Так же, как это звучит - доминирующий набор, который также является кликой .
Остин Бьюкенен
13

Это пример того явления, которое вы ищете?

Рассмотрим задачу k-Clique, где k - это размер клики, которую мы ищем. Итак, проблема в том, есть ли клика размера k в графе G по n вершинам?

Для всех констант k проблема в P. (Алгоритм грубой силы выполняется за время .) Для больших значений k, например, таких как n / 2, он является NP-полным. Когда k становится очень близко к n, как nc для некоторой константы c, проблема снова в P, потому что мы можем искать по всем подмножествам n вершин размера nc и проверять, образует ли какая-либо из них клику. (Есть только таких подмножеств, которые полиномиально велики, когда c является константой.)O ( n c )O(nk)O(nc)

Робин Котари
источник
7
Это явление только потому, что мы могли бы также рассматривать k как min (k, nk) и либо решать k-clique, либо k-indept set (на самом деле та же проблема). Если по этой причине мы думаем о 0 <k <= n / 2, то сложность строго увеличивается в k.
Аарон Рот
4
@ Аарон: Боюсь, что ваш аргумент неверен. Поиск клики размером n − k сильно отличается от поиска независимого набора размера k. Вы должны быть смущены тем фактом, что нахождение клики размера k в графе G эквивалентно нахождению независимого набора размера k в дополнении G.
Tsuyoshi Ito
Цуёши: Да, конечно. Я намеревался сказать, что WLOG можно считать k <= n / 2, поскольку, если нет, возьмите граф дополнения и решите задачу для k '= nk. И, конечно, это подчеркивает, что сложность увеличивается в k.
Аарон Рот
1
@ Аарон: «если нет, возьмите граф дополнения и решите задачу для k '= nk». Это именно неправильное утверждение, которое я пытаюсь возразить. Позвольте мне повторить то, что я сказал: «нахождение клики размера k в графе G эквивалентно нахождению независимого набора размера k в дополнении к G.» Нахождение клики размера k в графе G не эквивалентно нахождению клика размером n − k в дополнении G.
Tsuyoshi Ito
2
О да. :-) Это было глупо, я отказываюсь от своих возражений. Здесь происходит только то, что Binomial [n, k] = Binomial [n, nk], и поэтому время полного поиска монотонно увеличивается при k <n / 2, а монотонно уменьшается при k> n / 2.
Аарон Рот
12

Вот пример, который может быть того типа, который вы ищете. Параметр не является целым числом, это пара чисел. (Хотя один из них может быть исправлен, чтобы сделать его проблемой с одним параметром.)

Задача состоит в том, чтобы оценить многочлен Тутте графа G в координатах (x, y). Мы можем ограничить координаты целыми числами. Проблема в P, если (x, y) является одной из точек (1, 1), (-1, -1), (0, -1), (-1,0) или удовлетворяет (x-1 ) (у-1) = 1. Иначе это # ​​P-hard.

Я получил это из статьи Википедии о полиноме Тутте .

Робин Котари
источник
12

kk=22dO(n4d3)d2k2

Кевин Костелло
источник
10

t

ttGHGxyxyHtGtt

Сплит график представляет собой график , у которого множество вершин можно разбить на клики и независимое множество.

t3t

user13136
источник
10

k

kΔNP

Для кубических графов, решающих существование окраски ребер, используем:

  • k=2
  • k=3NP
  • k4

Холиер, Ян (1981), «NP-полнота окраски краев», журнал SIAM по вычислительной технике 10: 718–720

http://en.wikipedia.org/wiki/Edge_coloring

Мухаммед Аль-Туркистани
источник
Не могли бы вы добавить ссылку?
Александр Бондаренко
6

UV(G)GG[U]GU

Решение о том, имеет ли график диаметра 1 несвязанный срез, является тривиальным. Проблема становится NP-трудной на графиках диаметра 2, см. Эту статью, и опять же легко на графиках диаметром не менее 3 см. Эту статью .

user13136
источник