Topologische Art von zyklischen Graph mit minimaler Anzahl von verletzten Kanten

Question

Ich suche nach einer Möglichkeit, eine topologische Sortierung auf einem bestimmten gerichteten ungewichteten Graphen durchzuführen, der Zyklen enthält. Das Ergebnis sollte nicht nur die Ordnung der Knoten enthalten, sondern auch die Menge der Kanten, die durch die gegebene Reihenfolge verletzt werden. Dieser Kantensatz soll minimal sein.

Da mein Eingabediagramm möglicherweise groß ist, kann ich keinen exponentiellen Zeitalgorithmus verwenden. Wenn es nicht möglich ist, eine optimale Lösung in polynomieller Zeit zu berechnen, welche Heuristik wäre für das gegebene Problem sinnvoll?

Answer 1

Eades, Lin und Smyth vorgeschlagen A fast and effective heuristic for the feedback arc set problem. Der Originalartikel befindet sich hinter einer Paywall, aber eine kostenlose Kopie ist erhältlich unter here.

Es gibt einen Algorithmus für die topologische Sortierung, der die Scheitelpunktordnung aufbaut, indem er einen Scheitelpunkt ohne ankommende Bögen auswählt, auf dem Graphen minus dem Scheitel rekursiv vorgeht und diesen Scheitelpunkt der Reihenfolge voranstellt. (Ich beschreibe den Algorithmus rekursiv, aber Sie müssen ihn nicht so implementieren.) Der Eades-Lin-Smyth-Algorithmus sucht auch nach Scheitelpunkten ohne ausgehende Bögen, und hängt sie an an. Natürlich kann es vorkommen, dass alle Scheitelpunkte ein- und ausgehende Bögen haben. Wählen Sie in diesem Fall den Eckpunkt mit der höchsten Differenz zwischen ein- und ausgehend. Hier kann zweifellos experimentiert werden.

Die Algorithmen mit nachweisbarem Worst-Case-Verhalten basieren auf linearen Programmier- und Graphenschnitten. Diese sind sauber, aber die Garantien sind weniger als ideal (log^2 n oder log n log log n mal so viele Bögen wie benötigt), und ich vermute, dass effiziente Implementierungen ein ziemliches Projekt wären.