The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003141 Minimal number of arcs whose reversal yields a transitive tournament.
(Formerly M2334)
0, 0, 0, 1, 1, 3, 4, 7, 8, 12, 15, 20, 22, 28 (list; graph; refs; listen; history; text; internal format)



This is the "minimum feedback arc set" problem.

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).


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

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


Table of n, a(n) for n=0..13.

J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25.

J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25. [Annotated scanned copy]

I. Charon and O. Hudry, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Ann. Oper. Res. 175 (2010), 107-158

Don Coppersmith, Lisa Fleischer and Atri Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, SODA 2006: 776-782.

Robert A. Laird, Brandon S. Schamp, Calculating Competitive Intransitivity: Computational Challenges, The American Naturalist (2018), Vol. 191, No. 4, 547-552.

Range Voting Yahoo Group, Range Voting.

Range Voting Yahoo Group, Introduction. [Cached copy]

RangeVoting.org, Group Website.

K. B. Reid, On sets of arcs containing no cycles in tournaments, Canad. Math. Bull., 12 (1969), 261-264.

W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs [Has much more information]

Index entries for sequences related to tournaments


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


Equals C(n, 2) - A001225.

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

Sequence in context: A129819 A025032 A207524 * A284491 A284506 A157419

Adjacent sequences:  A003138 A003139 A003140 * A003142 A003143 A003144




N. J. A. Sloane


More terms from Irène Charon and Olivier Hudry.

Terms a(12) and a(13) from Christian Stricker, Jan 14 2017



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 09:09 EDT 2020. Contains 337380 sequences. (Running on oeis4.)