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]

Das zugehörige Entscheidungsproblem ist wie folgt definiert:

FAS := \{(G=(V,E),~k) | G ist gerichter Graph und enthält eine Kantenmenge E' \subset E: |E'| \leq k so dass gilt: G=(V, E - E') ist azyklisch\}

Für ungerichtete Graphen existiert eine analoge Definition.

Komplexität[Bearbeiten]

Das Entscheidungsproblem FAS ist für gerichtete Graphen NP-Vollständig, in ungerichteten Graphen hingegen korrespondiert es zu dem Problem, einen minimalen Spannbaum zu finden, was in polynomieller Zeit möglich ist, das heißt, FAS ist in der Komplexitätsklasse P.