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

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

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

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

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

Ура, Роберт