Есть ли проблема, которая проста для кубического графа, но сложна для графов с максимальной степенью 3?

Кубические графы - это графы, в которых каждая вершина имеет степень 3. Они были тщательно изучены, и я знаю, что некоторые NP-сложные задачи остаются NP-трудными, даже если они ограничены подклассами кубических графов, но некоторые другие становятся проще. Суперкласс кубических графов - это класс графов с максимальной степенью . $\Delta \leq 3$

Есть ли какая-нибудь проблема, которую можно решить за полиномиальное время для кубических графов, но это NP-трудно для графов с максимальной степенью ? $\Delta \leq 3$

graph-theory graph-algorithms np-hardness Виниций душ Сантуш
источник

Вырожденный ответ, который показывает, что могут быть разные сложности (хотя ни одна из них не является NP-Hard): Нахождение является постоянным временем на кубических графах, но линейным на графах с . :-)

δ

$\delta$

Δ \leq 3

$\Delta \le 3$

Уильям Макрэй

Хорошая точка зрения. :-)

Виниций душ Сантуш

Для неправильного выбора кодировок это может быть даже -hard, когда , но будет гораздо ценнее найти проблему, которая не зависит от плохой кодировки, и даже лучше, если эта проблема хорошо изучал один.

N P

$NP$

Δ \leq 3

$\Delta \le 3$

Уильям Макрэй

Чтобы расширить комментарий Уильяма, вот искусственная проблема. Учитывая граф , представляет ли последовательность степеней , интерпретируемая как кодирование экземпляра 3-SAT, удовлетворительный экземпляр? $G$ $G$

(Предполагая, что кодировка такова, что последовательность из всех 3 степеней представляет удовлетворительное назначение для каждого .) :-)

n

$n$

Нил Янг,

См. Также cstheory.stackexchange.com/questions/1215/… для большего вдохновения (например, проблемы, которые являются сложными для деревьев максимальной степени 3, но тривиальными, если нет листовых узлов).

Юкка Суомела

Ответы:

$(G,k)$ $G$ $k$

Дэвид Эппштейн
источник

«... тогда решение - либо самый длинный цикл, либо максимальное совпадение ...». Как ваша претензия зависит от k? Это не верно для всех k.

Тайсон Уильямс

k

$k$

k = n

$k=n$

n

$n$

P

$P$

Дэвид, максимальное совпадение (размером больше 1) в G не является связанным подграфом G. Вы хотите сказать «... либо самый длинный цикл, либо одно ребро, ...»?

Тайсон Уильямс

Ладно ладно. Сегодня, кажется, не очень хороший день для меня, чтобы быть строгим - слишком много индейки, вероятно. Я добавил немного языка, чтобы исключить этот особый случай.

Дэвид Эппштейн

@YininCao Поскольку граф связан, но не является регулярным, нет способа выбрать 3-регулярный подграф. Предположим, что это так. Тогда существует вершина, которая не была выбрана, поскольку граф не является регулярным. Поскольку граф связан, эта вершина связана с некоторой 3-правильной вершиной, которая была выбрана. Но это означает, что существует вершина степени 4, противоречие.

Тайсон Уильямс