Tournaments as feedback arc sets (Q1899826)

Summary: We examine the size \(s(n)\) of a smallest tournament having the arcs of an acyclic tournament on \(n\) vertices as a minimum feedback are set. Using an integer linear programming formulation we obtain lower bounds \(s(n) \geq 3n - 2 - \lfloor \log_2 n \rfloor\) or \(s(n) \geq 3n - 1 - \lfloor \log_2 n \rfloor\), depending on the binary expansion of \(n\). When \(n = 2^k - 2^t\) we show that the bounds are tight with \(s(n) = 3n - 2 - \lfloor \log_2 n \rfloor\). One view of this problem is that if the `teams' in a tournament are ranked to minimize inconsistencies there is some tournament with \(s(n)\) `teams' in which \(n\) are ranked wrong. We also pose some questions about conditions on feedback arc sets, motivated by our proofs, which ensure equality between the maximum number of arc disjoint cycles and the minimum size of a feedback arc set in a tournament.