Feedback Arc Set

The term feedback arc set comes from graph theory and describes a set of edges, the removal of which from a graph makes it acyclic, i.e. H. becomes circular.

Decision problem

The associated decision problem is defined as follows:

${\displaystyle FAS}$ ${\displaystyle :=\{(G=(V,E),~k)|}$G is a directed graph and contains a set of edges such that: is acyclic ${\displaystyle E'\subset E:|E'|\leq k}$ ${\displaystyle G'=(V,E-E')}$ ${\displaystyle \}}$

An analogous definition exists for undirected graphs.

complexity

The decision problem FAS is NP-complete for directed graphs . In undirected graphs it corresponds to the problem of finding a minimal spanning tree , which is possible in polynomial time, so FAS is in complexity class P there .