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

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

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

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

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

Ура, Роберт