Ich stecke bei folgendem Problem fest: Bei einem gewichteten Digraphen G möchte ich den minimalen Teilgraphen von G konstruieren, der alle negativen (einfachen) Zyklen von G enthält.

Ich weiß, wie man mit Bellman-Ford einen negativen Zyklus findet, und ich weiß, dass die Anzahl der einfachen Zyklen in einem gerichteten Graphen exponentiell ist.

Ein naiver Weg, sich dem Problem zu nähern, wäre, einfach alle einfachen Zyklen zu iterieren und diejenigen auszuwählen, die negativ sind, aber ich habe das Gefühl, dass es einen Polynom-Zeit-Algorithmus geben könnte. Bei den meisten Artikeln, die ich über Google gefunden habe, ging es darum, einen (eher als alle) negativen Zyklus zu finden.

Ich hoffe, hier einige Experten für Stackoverflow zu finden, die Hinweise auf eine Lösung in Polynomzeit oder auf den Nachweis geben, dass sie in Polynomzeit nicht gelöst werden kann.

Vielen Dank im Voraus!

Prost, Robert