Нахождение минимального подграфа, содержащего все отрицательные циклы

Question

Я застрял в следующей проблеме: учитывая взвешенный орграф G, я хотел бы построить минимальный подграф G, который содержит все отрицательные (простые) циклы G.

Я знаю, как найти отрицательный цикл, используя Беллмана-Форда, и знаю, что число простых циклов в ориентированном графе является экспоненциальным.

Одним из наивных способов решения этой проблемы было бы просто повторить все простые циклы и выбрать те, которые являются отрицательными, но у меня есть ощущение, что может существовать алгоритм за полиномиальное время. Большинство статей, которые я нашел через Google, были посвящены поиску (а не всему) негативного цикла.

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

Спасибо заранее!

Ура, Роберт

Answer 1

Для тех, кто заинтересован или застрял в аналогичной проблеме: она NP-полная. Спасибо, что указал мне на тему в cstheory.

Чтобы понять, почему он NP-полон, прежде всего заметим, что задача может быть сформулирована следующим образом: для заданного взвешенного ориентированного графа G с N вершинами и ребром E на G выяснить, лежит ли E в (простом) отрицательном цикле. Если это так, E должен быть в подграфе H. Если это не так, он не должен быть в H.

Пусть теперь ребро E есть E = (u, v) с весом w. Мы хотели бы знать, существует ли путь от v к u с полным весом W, такой что W + w < 0. Если бы мы могли сделать это за полиномиальное время, мы могли бы также решить проблему цикла Гамильтона за полиномиальное время:

Присвойте ребру E вес N - 1.00001. Присвойте всем остальным ребрам графа вес -1. Теперь единственным отрицательным циклом графа, на котором лежит E, является цикл, который содержит все вершины (этот цикл имеет вес -0,00001) и, таким образом, является гамильтоновым циклом.

Большое спасибо за размышления!