Research on Minimum Feedback Arc Set Problem
DOI:
https://doi.org/10.54097/az8w1s78Keywords:
minimum FAS, graph theory, set problem.Abstract
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.
Downloads
References
[1] Ali Baharev, Hermann Schichl, Arnold Neumaier, Tobias Achterberg, An Exact Method for the Minimum Feedback Arc Set Problem, ACM J. Exp.
Algorithmics, vol. 26 (2021), no. 1.4, pp. 1 - 28, DOI 10.1145/3446429.
[2] Benno Schwikowski, Ewald Spunkmeyer, On Enumerating All Minimal Solutions of Feedback Problems, Discrete Applied Mathematics, vol. 117 (2002), no. 1-3, pp. 253 - 265, DOI 10.1016/S0166 - 218X (00) 00339 - 5.
[3] John G. Kemeny, Mathematics Without Numbers, Daedalus, vol. 88 (1959), no. 4, pp. 577 - 591.
[4] Marek Karpinski, Warren Schudy, Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament, ISAAC, vol. 6506 (2010), pp. 3 - 14, DOI 10.1007/978 - 3 - 642 - 17517 - 6_3.
[5] Mark Gritter. How would a reduction from Vertex-cover to Feedback Vertex Set work. https://www.quora.com/How-would-a-reduction-from-Vertex-cover-to-Feedback- Vertex-Set-work. (updated 2020).
[6] Peter Eades, Xuemin Lin, W. F. Smyth, A Fast and Effective Heuristic for the Feedback Arc Set Problem, Information Processing Letters. vol. 47 (1993), no. 6, pp. 319 - 323, DOI 10.1016/0020-0190 (93) 90079 - O.
[7] R. Ravi. Approximation Algorithms. https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec9.pdf. (updated October 10, 2005).
[8] Richard M. Karp, Reducibility Among Combinatorial Problems, The Journal of Symbolic Logic, vol. 40 (1975), no. 4, pp. 85 - 103, DOI 10.2307/2271828.
[9] Wikipedia. Feedback Vertex Set https://en.wikipedia.org/wiki/Feedback_vertex_set (updated 13 July 2021).
[10] Wikipedia. Feedback Arc Set. https://en.wikipedia.org/wiki/Feedback_arc_set (updated November 17, 2021).
[11] Wikipedia. Graph (Discrete Mathematics). https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) (updated October 10, 2021).
[12] Wikipedia. NP (Complexity). https://en.wikipedia.org/wiki/NP_(complexity) (updated September 29, 2021).
[13] Wikipedia. Ranked Voting. https://en.wikipedia.org/wiki/Ranked_voting (updated November 18, 2021).
[14] Wikipedia. Vertex Cover. https://en.wikipedia.org/wiki/Vertex_cover (updated 11 November 2021).
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Highlights in Science, Engineering and Technology
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
