Нахождение всех вершин на отрицательных циклах

Я знаю, что проблема проверки того, принадлежит ли данное ребро взвешенного орграфа отрицательному циклу, является NP-полной (Поиск минимального подграфа, содержащего все отрицательные циклы), а Беллман-Форд позволяет проверить вершину на предмет того же самого за время O(|V|*|E|). Но что, если я хочу найти все вершины, принадлежащие отрицательным циклам? Интересно, можно ли это сделать быстрее, чем O(|V|^3) Флойда-Уоршалла.


algorithm graph-theory bellman-ford graph-algorithm floyd-warshall
person tempestadept    schedule 23.05.2013    source источник
comment
хм, недостаточно сложно, чтобы быть в теории, недостаточно программируемо, чтобы быть на SO.   -  person Woot4Moo    schedule 23.05.2013
comment
Почему Bellman-Ford не предоставила вам эту информацию? Все вершины, расстояние до которых было обновлено на n-й фазе, должны находиться в цикле с отрицательным весом, не так ли?   -  person G. Bach    schedule 23.05.2013
comment
Они также могут быть доступны из отрицательного цикла.   -  person tempestadept    schedule 23.05.2013
comment
О да, я задумался, ты прав.   -  person G. Bach    schedule 23.05.2013
comment
@Woot4Moo Прочтите FAQ: если ваш вопрос в целом касается … программного алгоритма … то вы находитесь в правильном месте, чтобы задать свой вопрос!   -  person David Eisenstat    schedule 24.05.2013
comment
@DavidEisenstat Я знаком с часто задаваемыми вопросами, я думаю, что это больше теория, но недостаточно теории, если вы будете следовать.   -  person Woot4Moo    schedule 24.05.2013
comment
@ Woot4Moo Нет, я не слежу. Как это не вопрос про программный алгоритм?   -  person David Eisenstat    schedule 24.05.2013
comment
Кстати, это не по теме cstheory (не на исследовательском уровне).   -  person David Eisenstat    schedule 24.05.2013
comment
@DavidEisenstat, вы уверены, что это не исследовательский уровень? Потому что это означает, что у вас есть решение этой проблемы теории графов.   -  person Woot4Moo    schedule 24.05.2013

Ответы (1)


arrow_upward
1
arrow_downward

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

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

Для каждого ребра (u, w) вашего взвешенного орграфа введите новую вспомогательную вершину v и разделите (u, w) на два ребра (u, v) и (v, w). Вес (u, w) может быть присвоен либо (u, v), либо (v, w). Теперь применим волшебный полиномиальный алгоритм, чтобы найти все вершины, лежащие в отрицательном цикле, и взять подмножество, состоящее из вспомогательных вершин. Поскольку каждая вспомогательная вершина связана с ребром, мы решили задачу поиска минимального подграфа, содержащего все отрицательные циклы, и, таким образом, можем также решить проблему гамильтоновых циклов за полиномиальное время, что подразумевает P = NP. Предполагая, что P != NP, нахождение всех вершин, лежащих на отрицательном цикле, является NP-полным.

person robertdg    schedule 24.05.2013
comment
Хорошо, я понял свою ошибку. Беллман-Форд проверяет не обязательно простой цикл, и нахождение простого цикла действительно является NP-полным. Спасибо. - person tempestadept; 24.05.2013