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:

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

Für ungerichtete Graphen existiert eine analoge Definition.

Komplexität

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.