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

22

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

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

Виниций душ Сантуш
источник
2
Вырожденный ответ, который показывает, что могут быть разные сложности (хотя ни одна из них не является NP-Hard): Нахождение является постоянным временем на кубических графах, но линейным на графах с . :-)Δ 3δΔ3
Уильям Макрэй
Хорошая точка зрения. :-)
Виниций душ Сантуш
Для неправильного выбора кодировок это может быть даже -hard, когда , но будет гораздо ценнее найти проблему, которая не зависит от плохой кодировки, и даже лучше, если эта проблема хорошо изучал один. Δ 3NPΔ3
Уильям Макрэй
1
Чтобы расширить комментарий Уильяма, вот искусственная проблема. Учитывая граф , представляет ли последовательность степеней , интерпретируемая как кодирование экземпляра 3-SAT, удовлетворительный экземпляр? GGG n (Предполагая, что кодировка такова, что последовательность из всех 3 степеней представляет удовлетворительное назначение для каждого .) :-)n
Нил Янг,
См. Также cstheory.stackexchange.com/questions/1215/… для большего вдохновения (например, проблемы, которые являются сложными для деревьев максимальной степени 3, но тривиальными, если нет листовых узлов).
Юкка Суомела

Ответы:

21

(G,k)Gk

Дэвид Эппштейн
источник
«... тогда решение - либо самый длинный цикл, либо максимальное совпадение ...». Как ваша претензия зависит от k? Это не верно для всех k.
Тайсон Уильямс
1
kk=nnP
1
Дэвид, максимальное совпадение (размером больше 1) в G не является связанным подграфом G. Вы хотите сказать «... либо самый длинный цикл, либо одно ребро, ...»?
Тайсон Уильямс
2
Ладно ладно. Сегодня, кажется, не очень хороший день для меня, чтобы быть строгим - слишком много индейки, вероятно. Я добавил немного языка, чтобы исключить этот особый случай.
Дэвид Эппштейн
3
@YininCao Поскольку граф связан, но не является регулярным, нет способа выбрать 3-регулярный подграф. Предположим, что это так. Тогда существует вершина, которая не была выбрана, поскольку граф не является регулярным. Поскольку граф связан, эта вершина связана с некоторой 3-правильной вершиной, которая была выбрана. Но это означает, что существует вершина степени 4, противоречие.
Тайсон Уильямс