Feedback Arc Set
The term Feedback Arc Set comes from graph theory and describes a set of edges, by their removal from a graph of these acyclic, ie is cycle-free.
The corresponding decision problem is defined as follows:
G is Gerichter graph and contains a set of edges so that applies: is acyclic
For undirected graphs, there is a similar definition.
The decision problem for directed graphs FAS is NP- Complete, in undirected graphs, however, it corresponds to the problem of finding a minimum spanning tree, which is possible in polynomial time, ie, FAS is in the complexity class P.
- Graph Theory
- Complexity Theory