%I M2334 #60 Feb 14 2023 02:36:53

%S 0,0,0,1,1,3,4,7,8,12,15,20,22,28

%N Minimal number of arcs whose reversal yields a transitive tournament.

%C This is the "minimum feedback arc set" problem.

%C The minimal number of arcs you need to delete to make a directed graph acyclic (maxed over all n-vertex directed graphs) is the same as the minimal number of arcs you need to reverse to make a tournament acyclic (maxed over all n-player tournaments).

%D Sanchez-Flores, Neumann-Lara and Bermond, Graphs & Combin 10 (1994) 363-366 and 367-376.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H J.-C. Bermond, <a href="http://www.numdam.org/item?id=MSH_1972__37__5_0">Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux</a>, Math. Sci. Hum., No. 37 (1972), 5-25.

%H J.-C. Bermond, <a href="/A003141/a003141.pdf">Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux</a>, Math. Sci. Hum., No. 37 (1972), 5-25. [Annotated scanned copy]

%H I. Charon and O. Hudry, <a href="http://biblio.telecom-paristech.fr/cgi-bin/download.cgi?id=9665">An updated survey on the linear ordering problem for weighted or unweighted tournaments</a>, Ann. Oper. Res. 175 (2010), 107-158

%H Don Coppersmith, Lisa Fleischer and Atri Rudra, <a href="http://www.cse.buffalo.edu/faculty/atri/papers/algos/FAS-journal-final.pdf">Ordering by weighted number of wins gives a good ranking for weighted tournaments</a>, SODA 2006: 776-782.

%H Robert A. Laird and Brandon S. Schamp, <a href="https://doi.org/10.1086/696266">Calculating Competitive Intransitivity: Computational Challenges</a>, The American Naturalist (2018), Vol. 191, No. 4, 547-552.

%H Range Voting Yahoo Group, <a href="http://groups.yahoo.com/group/RangeVoting/">Range Voting</a>.

%H Range Voting Yahoo Group, <a href="/A003141/a003141.txt">Introduction</a>. [Cached copy]

%H RangeVoting.org, <a href="https://rangevoting.org/">Group Website</a>.

%H K. B. Reid, <a href="http://dx.doi.org/10.4153/CMB-1969-032-x">On sets of arcs containing no cycles in tournaments</a>, Canad. Math. Bull., 12 (1969), 261-264.

%H W. D. Smith, <a href="http://rangevoting.org/PuzzDG.html">Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs</a> [Has much more information]

%H <a href="/index/To#tournament">Index entries for sequences related to tournaments</a>

%F The asymptotics for large n are (n+1)*n/4 - C*n^(3/2) <= F(n) <= (n+1)*n/4 - K*n^(3/2) for all sufficiently large n and certain constants C, K > 0. - _Warren D. Smith_, Sep 14 2006

%Y Equals C(n, 2) - A001225.

%Y a(n) = A182079(n) iff n <= 9, thereafter a(n) > A182079(n). [Bermond]

%K hard,more,nonn,nice

%O 0,6

%A _N. J. A. Sloane_

%E More terms from Irène Charon and Olivier Hudry

%E Terms a(12) and a(13) from _Christian Stricker_, Jan 14 2017