Feedback Arc Set

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Begriff Feedback Arc Set stammt aus der Graphentheorie und bezeichnet eine Menge von Kanten, durch deren Entfernung aus einem Graphen dieser azyklisch, d. h. kreisfrei wird.

Entscheidungsproblem

[Bearbeiten | Quelltext bearbeiten]

Das zugehörige Entscheidungsproblem ist wie folgt definiert:

G ist gerichteter Graph und enthält eine Kantenmenge so dass gilt: ist azyklisch

Für ungerichtete Graphen existiert eine analoge Definition.

Das Entscheidungsproblem FAS ist für gerichtete Graphen NP-vollständig. In ungerichteten Graphen korrespondiert es zu dem Problem, einen minimalen Spannbaum zu finden, was in polynomieller Zeit möglich ist, FAS ist dort also in der Komplexitätsklasse P.