Я ищу примеры задач, параметризованных числом , где жесткость задачи немонотонна по k . Большинство проблем (по моему опыту) имеют один фазовый переход, например, k- SAT имеет один фазовый переход от k ∈ { 1 , 2 } (где проблема в P) к k ≥ 3 (где проблема NP- полный). Меня интересуют проблемы, в которых происходят фазовые переходы в обоих направлениях (от простого к сложному и наоборот) при увеличении k .
Мой вопрос чем-то похож на вопрос, заданный в « Переходах твердости в вычислительной сложности» , и на самом деле некоторые ответы там относятся к моему вопросу.
Примеры, которые я знаю:
- -цветность плоских графов: в P за исключением случаев, когда , где NP-полная.
- Дерево Штейнера с терминалами: в P, когда k = 2 (сворачивается на кратчайший s - t путь) и когда k = n (сворачивается в MST), но NP-hard «между». Я не знаю, являются ли эти фазовые переходы резкими (например, P для k 0, но NP-hard для k 0 + 1 ). Кроме того, переходы k зависят от размера входного экземпляра, в отличие от моих других примеров.
- Подсчет удовлетворяющих присвоений плоской формулы по модулю : В P, когда -
простоечисло Мерсенна, , и # P-Complete длябольшинства (?) /Всех других значений (от Аарона Стерлинга в этой теме ) , Много фазовых переходов! - Индуцированное обнаружение подграфа: проблема не параметризована целым числом, а графиком. Существуют графы (где ⊆ обозначает определенный вид отношения подграфа), для которых определяется, находится ли H i ⊆ G для данного графа G в P для i ∈ { 1 , 3 }, но NP- завершено для i = 2 . (от Сянь-Чжи Чанга в той же теме ).
Ответы:
Одна область с большим количеством немонотонности сложности проблемы - это тестирование свойств. Пусть - множество всех n- вершинных графов, а P ⊆ G n - свойство графа. Общая проблема состоит в том, чтобы определить, обладает ли граф G свойством P (т. Е. G ∈ P ) или «далек» от свойства P в некотором смысле. В зависимости от того, что представляет собой P и какой тип запроса у вас есть к графику, проблема может быть довольно сложной.Gn n P⊆Gn G P G∈P P P
Но легко заметить, что проблема немонотонная: в том случае, если мы имеем , тот факт, что P легко тестируем, не означает, что S легко тестируемо или T таково .S⊂P⊂T P S T
Чтобы убедиться в этом, достаточно заметить , что и P = ∅ оба тривиальным проверяемым, но для некоторых свойств, существуют сильные нижние границы.P=Gn P=∅
источник
Для данного графа и целого числа к ≥ 1 , в K -й мощности G , обозначаемой G к , имеет ту же самую вершину устанавливается так , что две различные вершины смежны в G к , если их расстояние в G не превосходит к . Задача k-й степени расщепленного графа спрашивает, является ли данный граф k -й степенью графа расщепления.G k≥1 k G Gk Gk G k k k
источник
Соответствующий вопрос обсуждается здесь .
источник
Определение, имеет ли граф доминирующую клику для:G
Случай связан с Брандштадтом и Крачем , а случай отмечен в моей недавней статье .d i a m ( G ) = 2diam(G)=3 diam(G)=2
источник
Это пример того явления, которое вы ищете?
Рассмотрим задачу 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)
источник
Вот пример, который может быть того типа, который вы ищете. Параметр не является целым числом, это пара чисел. (Хотя один из них может быть исправлен, чтобы сделать его проблемой с одним параметром.)
Задача состоит в том, чтобы оценить многочлен Тутте графа G в координатах (x, y). Мы можем ограничить координаты целыми числами. Проблема в P, если (x, y) является одной из точек (1, 1), (-1, -1), (0, -1), (-1,0) или удовлетворяет (x-1 ) (у-1) = 1. Иначе это # P-hard.
Я получил это из статьи Википедии о полиноме Тутте .
источник
источник
Сплит график представляет собой график , у которого множество вершин можно разбить на клики и независимое множество.
источник
Для кубических графов, решающих существование окраски ребер, используем:
Холиер, Ян (1981), «NP-полнота окраски краев», журнал SIAM по вычислительной технике 10: 718–720
http://en.wikipedia.org/wiki/Edge_coloring
источник
Доказательство было объявлено в этой статье .
источник
См. Чандран, Л. Сунил, Дипак Раджендрапрасад и Марек Тесарж. «Радужная раскраска расщепленных графов». Препринт arXiv arXiv: 1404.4478 (2014).
источник
Решение о том, имеет ли график диаметра 1 несвязанный срез, является тривиальным. Проблема становится NP-трудной на графиках диаметра 2, см. Эту статью, и опять же легко на графиках диаметром не менее 3 см. Эту статью .
источник