Общее понимание гипотетической сложности графовых задач

Я наткнулся на два примера гипотетической сложности некоторых графовых задач. Гипотетическая твердость означает, что опровержение некоторой гипотезы подразумевает NP-полноту соответствующей задачи графа. Например, гипотеза Барнетта утверждает, что каждый 3-связный кубический плоский двудольный граф является гамильтоновым. Федер и Суби доказали, что опровержение гипотезы подразумевает NP-полноту задачи о гамильтоновом цикле на графах в классе гипотезы.

Гипотеза Тутте о 5-потоке утверждает, что у каждого безмостового графа есть 5-поток без нуля. Кохол показал, что если гипотеза неверна, то проблема определения, допускает ли кубический граф 5-поток в никуда-ноль, является NP-полной .

Существуют ли общие взгляды на приведенные выше гипотезы, объясняющие гипотетическую NP-полноту соответствующих графовых задач? Есть ли другие примеры гипотетической сложности в вышеприведенном смысле?

PS Это было опубликовано на MathoverFlow без ответа.

Вот две ссылки на вторую часть вашего вопроса.

В работе [1] рассматриваются некоторые типы окрашиваемости разреженных графов с заданным обхватом . Для каждого фиксированного g они показывают, что связанная с ним задача решения является либо тривиальной (каждый граф в классе имеет раскраску), либо NP-полной. Но определение порогового значения g остается трудной открытой проблемой! Редактировать: Одна из рассмотренных проблем связана с гипотезой Йегера о том, что каждый плоский граф обхват 4 k допускает гомоморфизм C 2 k + 1$g$$g$$g$
$4k$$C_{2k+1}$, В [1] показано, что любой контрпример непосредственно обеспечивает доказательство твердости. (Аналогичная гипотеза Клостермейера и Чжана существует для нечетного обхвата.) Для других проблем, рассмотренных в [1], нет официальной гипотезы, но для любого предположения о правильном пороговом значении которое можно сделать, если окажется ложным контрпример, последний непосредственно подразумевает соответствующее доказательство твердости.$g$

Во введении цитируемой выше статьи также упоминается следующий интересный результат о SAT [2]. Там доказано, что для каждого существует функция f ( k ) такая, что ( k , f ( k ) ) -SAT (т.е. k -SAT, где каждая переменная встречается f ( k ) раз) тривиальна, но ( k , f ( k ) + 1 ) -SAT является NP-полным. (Точное значение f ( k $k$$f(k)$$(k,f(k))$$k$$f(k)$$(k,f(k)+1)$$f(k)$ кажется неизвестным, хотя некоторые оценки даны.)

[1] Л. Эсперет, М. Монтасье, П. Очем и А. Пинлоу. Сложная дихотомия для раскраски разреженных графов. Журнал теории графов 73: 85-102, 2012. ссылка + PDF на сайте автора

[2] J. Kratochvil, P. Savicky и Zs. Tuza. Еще одно вхождение переменных делает скачок выполнимости с тривиального на NP-полный. SIAM Journal of Computing 22: 203-210, 1993. ссылка

Существуют ли общие взгляды на приведенные выше гипотезы, объясняющие гипотетическую NP-полноту соответствующих графовых задач?

$O(1)$

И общее понимание состоит в том, что естественные проблемы, гамильтонов цикл и нулевой нулевой поток в общих графах, являются «сложными и мощными», достаточными для того, чтобы эффективно «моделировать» след машины Тьюринга (по Кук-Левину). Затем вы начинаете добавлять все больше и больше ограничений, пока не получите никакой «вычислительной мощности».

Для меня это все равно, что добавлять все больше и больше ограничений на граф переходов машины Тьюринга (или на ленточное устройство чтения / записи) до тех пор, пока вы не получите что-то тривиальное, например, «граф переходов не содержит цикла».

Есть ли другие примеры гипотетической сложности в вышеприведенном смысле?

В качестве (вероятно) «разрешенного случая» я могу поделиться своим опытом, связанным с проблемой « Перекатывание кубика по маркированной доске» .

Несколько лет назад было неизвестно, могут ли полностью помеченные доски содержать два разных цикла Гамильтона ( однозначно-раскручиваемая гипотеза была утверждена для всех досок с длинами сторон не более 8). Domotor P. (здесь пользователь domotorp) и я (независимо) доказали, что такие доски существуют и гипотеза неверна (... обратите внимание, что Джозеф О'Рурк еще не обновил свою страницу :-).

Затем, используя этот факт, я смог доказать, что прокатка матрицы на полностью маркированной доске с отверстиями является NP-полной ( корпус без отверстий все еще открыт); хотя это неопубликованный результат.