0,6

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

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

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

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

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

Sanchez-Flores, Neumann-Lara and Bermond, Math. Sci. Humaines 37 (1972) 5-25.

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

Yahoo Groups, Range Voting

Index entries for sequences related to tournaments

The asymptotics for large n are (n+1)n/4-Cn^{3/2} <= F(n) <= (n+1)n/4-Kn^{3/2} for all sufficiently large n and certain constants C,K>0. - Warren Smith, Sep 14 2006

Equals C(n, 2) - A001225.

Sequence in context: A026449 A129819 A025032 this_sequence A008368 A023054 A060023

Adjacent sequences: A003138 A003139 A003140 this_sequence A003142 A003143 A003144

hard,nonn,nice

njas

Additional comments from Warren D. Smith, Sep 14 2006