Сложна ли проблема множества вершин обратной связи на плоских ограниченных графах степеней?

Ответы:

16

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

VC to FVS: Заменить каждое ребро треугольником (или двойным ребром).

Одно замечание: Гэри и Джонсон также утверждают, что направленный FVS является NP-полным на планарных орграфах без внутренней или внешней степени, превышающей два. Они конкретно не упоминают о ненаправленных ФВС при таких ограничениях.

Стефан Крач
источник
14

4

4

Ограничение степени является наилучшим вариантом, так как FVS является полиномиальным для графов максимальной степени не более трех; см здесь .

Изменить: Эрнст де Риддер graphclasses.org теперь содержит всю доступную информацию о FVS; включая около 550 полиномиально разрешимых и около 250 случаев NP-c.

VB Le
источник
Не могли бы вы объяснить больше о сокращении, которое далеко от меня не ясно. У меня нет тезиса Спекенмейера под рукой (даже у меня был, я не буду в состоянии понимать немецкий язык). Но у меня есть упомянутая вами статья, которая, однако, относится только к его диссертации. С другой стороны, я знаю, что это NP-hard на общих графиках максимальной степени 4, как показано Ромео Рицци doi.org/10.1007/s00453-007-9112-8 . Благодарность!
Исинь Цао
5

Согласно Wikipedia, Garey & Johnson также показали, что «покрытие вершин остается NP-полным ... даже на планарных графиках степени не более 3».

Таким образом, FVS сложен на плоских графах с максимальной степенью 6.

101011
источник
2

По-видимому, в кандидатской диссертации Шпекенмейера он демонстрирует, что проблема множества вершин обратной связи является NP-трудной для графов максимальной степени 4. Это утверждение появляется здесь , например.

n/2z(G)+1nzz(G)G

Редактировать: недостаточно внимательно изучил редактирование файла vb le ...

Тимоти Сан
источник