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

Offset

0,6

Comments

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

References

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

Links

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 and 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

Formula

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

Crossrefs

Equals C(n, 2) - A001225.

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

Sequence in context: A129819 A025032 A207524 * A338467 A284491 A284506

Adjacent sequences: A003138 A003139 A003140 * A003142 A003143 A003144

Keyword

hard,more,nonn,nice

Author

N. J. A. Sloane

Extensions

More terms from Irène Charon and Olivier Hudry

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

Status

approved