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.

Decision problem

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.

Complexity

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