tailieunhanh - Báo cáo toán học: "Tournaments as Feedback Arc Sets"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Tournaments as Feedback Arc Sets. | Tournaments as Feedback Arc Sets Garth Isaak Department of Mathematics Lehigh University Bethlehem PA 18015 gi02@ Submitted April 21 1995 Accepted October 3 1995 Abstract We examine the size s n of a smallest tournament having the arcs of an acyclic tournament on n vertices as a minimum feedback arc set. Using an integer linear programming formulation we obtain lower bounds s n 3n 2 _log2 n or s n 3n 1 _log2 n depending on the binary expansion of n. When n 2k 2 we show that the bounds are tight with s n 3n 2 _log2 n . 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 will 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. AMS Classification Primary 05C20 Secondary 68R10 1 Introduction A feedback arc set in a digraph is a set of arcs whose removal makes the digraph acyclic. . Barthelemy asked whether every acyclic digraph arises as the arcs of a minimum sized feedback arc set of some tournament. In 1 we showed that this was the case and examined the smallest vertex size of such a tournament. For a digraph on n vertices this size is at most s n where s n is the smallest size of a tournament with the acyclic tournament Tn on n vertices as a feedback arc set. In 1 we used the term reversing number which is the number of additional vertices . s n n. Partially supported by a grant from the ONR 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 2 1995 R20 2 In Section 2 we will review an integer linear programming formulation from 1 and sketch a proof that s n is determined by its optimal value. We obtain lower bounds on s n in Section 3 and exact values in Section 4. These can be summarized as Theorem s n 3n 2 log2 n if n is Type I or III and s n 3n 1 log2 n if n is Type II. .