Простой путь на даге с задними краями

10

Какова сложность следующей задачи ( P? NP-hard?):

Входные данные: направленный ациклический граф , множество обратных ребер и два отдельных узла и .E V × V s tD=(V,E)EV×Vst

Вопрос: Пусть обозначает граф, образованный добавлением к ребер из . Существует ли простой путь от до в который использует хотя бы один обратный край?D E s t GG=(V,EE)DEstG

Примечание: 0) Простой путь - это путь, в котором ни одна вершина не повторяется. Обратное ребро - это ребро, которое противоречит частичному порядку, подразумеваемому DAG. 1) проблема проста, если мы просим простой путь использовать ровно одно обратное ребро (или постоянное число) путем тривиальной редукции к проблеме непересекающихся путей, которая допускает простое решение PTime в DAG ( Perl and Shiloach, JACM'78 ) 2) проблема непересекающихся путей является NP-полной в общих графах ( Fortune et al., TCS'80 ).

Джозеф Стэк
источник
1
Это, безусловно, не оптимально, но этого достаточно, чтобы показать, что ваша проблема в P (если я что-то не так понял): пусть - ребра ; применить алгоритм кратчайшего пути от к к графу для . Другими словами, продолжайте добавлять ребро, выбранное из в граф пока не найдете путь от до . E сек т Г я = ( V , E 'я J = 1 { е J } ) я = 1 , 2 , . , , , m E G = ( V , E ) s te1,...,emEstGi=(V,Ej=1i{ej})i=1,2,...,mEG=(V,E)st
Марцио Де Биаси,
1
Марцио: но что, если путь, который вы найдете, использует только ребра в , и ни одного в ? Еще может существовать другой путь, который также включает край . E E EEE
Дэвид Эппштейн
Что очень раздражает в вашей проблеме, так это то, что следующая связанная с ней проблема легко представляется NP-трудной: с помощью графа и двух пар вершин (s, t), (s ', t') определить, есть ли вершина-дизъюнкт пути от s к t и от s 'к t', даже когда t = s ', и даже на графах, которые являются объединением двух DAG. Тем не менее, это, кажется, не помогает для вопроса, который вы задаете.
3
1
Проблема непересекающихся путей - трудная задача W [1] даже на DAG, и это домашняя работа, чтобы показать, что в DAG это NP-Hard. Алгоритм Шилоаха предназначен для задачи о двух непересекающихся путях и в некоторой степени аналогичным образом работает для проблемы k непересекающихся путей в DAG, но требует времени n ^ k. Но, по крайней мере, допускает алгоритм XP для вашей проблемы.
Саид