Feedback Arc Set

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

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

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.