Известно ли, что задача множества вершин обратной связи на неориентированных плоских графах ограниченной степени является трудной?
Известно ли, что задача множества вершин обратной связи на неориентированных плоских графах ограниченной степени является трудной?
Согласно книге Гэри и Джонсона, покрытие вершин является NP-полным на планарных графах максимальной степени четыре. Использование простого сокращения от покрытия вершины до набора вершин обратной связи должно дать максимальную степень восемь и сохранить плоскостность.
VC to FVS: Заменить каждое ребро треугольником (или двойным ребром).
Одно замечание: Гэри и Джонсон также утверждают, что направленный FVS является NP-полным на планарных орграфах без внутренней или внешней степени, превышающей два. Они конкретно не упоминают о ненаправленных ФВС при таких ограничениях.
Ограничение степени является наилучшим вариантом, так как FVS является полиномиальным для графов максимальной степени не более трех; см здесь .
Изменить: Эрнст де Риддер graphclasses.org теперь содержит всю доступную информацию о FVS; включая около 550 полиномиально разрешимых и около 250 случаев NP-c.
Согласно Wikipedia, Garey & Johnson также показали, что «покрытие вершин остается NP-полным ... даже на планарных графиках степени не более 3».
Таким образом, FVS сложен на плоских графах с максимальной степенью 6.
источник
По-видимому, в кандидатской диссертации Шпекенмейера он демонстрирует, что проблема множества вершин обратной связи является NP-трудной для графов максимальной степени 4. Это утверждение появляется здесь , например.
Редактировать: недостаточно внимательно изучил редактирование файла vb le ...
источник