Utknąłem w następującym problemie: Biorąc pod uwagę ważony digraf G, chciałbym skonstruować minimalny podgraf G, który zawiera wszystkie ujemne (proste) cykle G.

Wiem, jak znaleźć ujemny cykl za pomocą Bellmana-Forda i wiem, że liczba prostych cykli na wykresie kierowanym jest wykładnicza.

Jednym z naiwnych sposobów podejścia do problemu byłoby po prostu iterowanie wszystkich prostych cykli i wybieranie tych, które są negatywne, ale mam wrażenie, że może istnieć algorytm czasu wielomianowego. Większość artykułów, które znalazłem w Google, dotyczyła znalezienia (a nie całego) negatywnego cyklu.

Mam nadzieję, że uda mi się znaleźć kilku ekspertów na temat stackoverflow, który może dać pewne wskazówki co do rozwiązania wielomianowego, lub podpowiedzi, aby udowodnić, że nie można go rozwiązać w czasie wielomianowym.

Z góry bardzo dziękuję!

Pozdrawiam, Robert