Какова сложность следующей задачи ( P? NP-hard?):
Входные данные: направленный ациклический граф , множество обратных ребер и два отдельных узла и .E ′ ⊂ V × V s t
Вопрос: Пусть обозначает граф, образованный добавлением к ребер из . Существует ли простой путь от до в который использует хотя бы один обратный край?D E ′ s t G
Примечание: 0) Простой путь - это путь, в котором ни одна вершина не повторяется. Обратное ребро - это ребро, которое противоречит частичному порядку, подразумеваемому DAG. 1) проблема проста, если мы просим простой путь использовать ровно одно обратное ребро (или постоянное число) путем тривиальной редукции к проблеме непересекающихся путей, которая допускает простое решение PTime в DAG ( Perl and Shiloach, JACM'78 ) 2) проблема непересекающихся путей является NP-полной в общих графах ( Fortune et al., TCS'80 ).
источник