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.

Karps 21 NP-vollständige Probleme

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