Твердость NP через ограничение

Question

Допустим, у меня есть проблема с решением $ p $ на графиках, для которых я знаю, что он NP-Hard на графиках с максимальной степенью $ D $. Подразумевает ли это, что это np-hard на графиках $ d $ -regular? Хотя это может показаться, очевидно, правда, возможно, это неотъемлемое сокращение, чтобы показать, что $ p $ сложно, что некоторые вершины имеют степень меньше, чем $ d $.

Answer 1

Нет, это не так в целом.

Общая проблема, состоящая в том, что NP-Hard не подразумевает, что специализация будет NP-Hard. Это правда наоборот.

Например, Max-Cut является NP-Hard для общих графиков, но для класса плоских графиков он находится в P.

В вашем случае графики $ D $-это особый случай графиков максимальной степени $ D $, поэтому NP-Hardness для максимальной степени $ D $ не является автоматическим доказательством NP-жесткости обычных графиков $ D $.

На самом деле, для конкретного примера, посмотрите на этот вопрос CSTheory: Есть ли проблема, которая легко для кубического графика, но трудно для графиков с максимальной степенью 3? со следующим отвечать(Дэвид Эппштейн) в утвердительном (скопированном для удобства):

Вот разумно естественный: на входном $ (g, k) $ определить, имеет ли $ g $ подключенный регулярный подграф с краями как минимум $ k $. Для 3-регтурных графиков это тривиально, но если максимальная степень составляет 3, а вход подключен, а не дерево, а не регулярно, то самый большой такой подграф-самый длинный цикл, поэтому проблема-NP-завершение.