Feedback Arc Set
# 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 gerichteter 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 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.

Erfüllbarkeitsproblem der Aussagenlogik | Cliquenproblem | Mengenpackungsproblem | Knotenüberdeckungsproblem | Mengenüberdeckungsproblem | Feedback Arc Set | Feedback Vertex Set | Hamiltonkreisproblem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by cliques | Problem der exakten Überdeckung | 3-dimensional matching | Steinerbaumproblem | Hitting set | Rucksackproblem | Job sequencing | Partitionsproblem | Maximaler Schnitt

