Графовые задачи, NP-полные на ориентированных графах, но полиномиальные на неориентированных графах

16

Я ищу проблемы, которые, как известно, являются NPC для ориентированных графов, но имеют полиномиальный алгоритм для неориентированных графов.

Я видел вопрос, касающийся здесь «направленных» проблем, которые проще, чем их «ненаправленный» вариант , но я ищу жесткость на направленной стороне.

Например, известно, что набор ребер обратной связи является NPC для ориентированного, но полиномиального времени, разрешимого на неориентированных графах.

Какие другие природные проблемы имеют такое же свойство?

RB
источник
2
st-связность является интересным примером для аналогичных классов более низкого уровня - L для неориентированного случая против NL-полного для направленного случая.
Гек Беннетт

Ответы:

18

Первая проблема, которая приходит мне в голову, - это проблема 2-пути (или, в более общем случае, проблема k-пути). Учитывая и ( s 2 , t 2 ) , найдите два непересекающихся пути от s 1 до t 1 и от s 2 до t 2 соответственно. Проблема в NPC для ориентированных графов, но за полиномиальное время разрешимая для неориентированных графов (хотя и не тривиальная).(s1,T1)(s2,T2)s1T1s2T2

Bangye
источник
1
Не могли бы вы привести цитату для этого NPC?
Остин Бьюкенен
8
k2К
Очень мило @Bangye!
РБ
10

Решение о наличии 3-х тактного покрытия Nп-полный на ориентированных графах, в то время как это разрешено за полиномиальное время на неориентированных графах путем сокращения до идеального соответствия.

Мухаммед Аль-Туркистани
источник
3

В задаче раскраски пути нам дано дерево T и набор путей в этом дереве (идея состоит в том, что T является сетью связи, а пути являются запросами связи). Мы хотим закрасить пути минимальным количеством цветов, чтобы два пути, которые имеют общий край, имели разные цвета.

Известно, что эта задача разрешима за полиномиальное время, если T - неориентированное дерево ограниченной степени. Однако NP-полна, если T является двунаправленным двоичным деревом. Я считаю, что оба результата приведены в статье ниже.

[1] Т. Эрлебах и К. Янсен. «Сложность раскраски пути и планирования звонков». Теоретическая информатика, 255 (1-2): 33–50, 2001.

Майкл Лэмпис
источник
1

Если я не ошибаюсь, получение аппроксимации постоянного фактора для дерева Штейнера является NP-трудным на ориентированных графах, но является P-временем на неориентированных графах.

Суреш Венкат
источник