Research on Minimum Feedback Arc Set Problem

The feedback arc set of a directed graph is the subset of the graph that consists of at least one edge from every cycle in the graph. Removing the fewest number of these edges gives the minimum feedback arc set. Three methods that attempt to solve this problem use equivalency and NP reductions, an approximate greedy algorithm, and an integer linear program for an exact solution. The minimum FAS can be applied to real world events such as sporting tournaments and ranked voting.