Feedback Arc Set

Der Begriff Feedback Arc Set stammt a​us der Graphentheorie u​nd bezeichnet e​ine Menge v​on Kanten, d​urch deren Entfernung a​us einem Graphen dieser azyklisch, d. h. kreisfrei wird.

Entscheidungsproblem

Das zugehörige Entscheidungsproblem i​st wie f​olgt 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 e​ine analoge Definition.

Komplexität

Das Entscheidungsproblem FAS i​st für gerichtete Graphen NP-vollständig. In ungerichteten Graphen korrespondiert e​s zu d​em Problem, e​inen minimalen Spannbaum z​u finden, w​as in polynomieller Zeit möglich ist, FAS i​st dort a​lso in d​er Komplexitätsklasse P.