Feedback Arc Set

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Komplexität[Bearbeiten | Quelltext bearbeiten]

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.