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

Question

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

Answer 1

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

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

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