A tournament is an orientation of a complete graph. A feedback arc set is a set of arcs in a digraph whose removal leave the digraph acyclic. The feedback arc set problem consists in finding a feedback arc set of minimum size. A polynomial time approximation scheme is an algorithm which takes an instance of an optimization problem and a parameter $ \epsilon > 0 $ and, in polynomial time, produces a solution that is within a factor $ 1+\epsilon $ of being optimal. 


The feedback arc set problem has been proved NP-hard. See [ACM, A, CTY, C]. It was shown in [RS] that the feedback arc set problem is fixed parameter tractable for tournaments.


Bibliography


\*[AA] N. Ailon, N. Alon, link, Inform. and Comput. 205 (8) (2007) 1117–1129.


[ACM] N. Alion, M. Charikar, A. Newman, Aggregating inconsistent information: Ranking and clustering, in: Proceedings of the 37th Symposium on the Theory of Computing, STOC, ACM Press, 2005, pp. 684–693.


[A] N. Alon, Ranking tournaments, SIAM J. Discrete Math. 20 (2006) 137–142.


[CTY] P. Charbit, P. Thomassé, A. Yeo, The minimum Feedback arc set problem is NP-hard for tournaments, Combin. Probab. Comput. 16 (1) (2007) 1–4.


[C] V. Conitzer, Computing Slater rankings using similarities among candidates, in: Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16–20, AAAI Press, Boston, Massachusetts, USA, 2006.


[RS] V. Raman, S. Saurabh, Parameterized complexity of directed feedback arc set problems in tournaments, in: Algorithms and Data Structures, in: Lecture Notes in Computer Science, vol. 2748, Springer, Berlin, 2003, pp. 484–492.



Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?
Not only a PTAS is known for this problem.


It is also possible to compute a PTAS, even without seeing the entire adjacency matrix !


In 2011, Ailon [has showed](http://arxiv-web3.library.cornell.edu/pdf/1011.0108v3.pdf) that by a smart choice of queries you can compute a $(1+\epsilon)$-approximation while reading only $O(\epsilon^{-6}\cdot n\cdot log^5n)$ entries (while having the entire matrix means making $O(n^2)$ queries) of the weight matrix $W$ (which becomes the adjacency matrix for unweighted instances),.


