Speaker: Qiulan Zhao

Title: A Min-Max Relation on Tournaments

Abstract: Let T = (V,A) be a tournament with a nonnegative integral weight function w defined on A. A collection C of direct cycles is called a cycle packing in T if every arc e ∈ A is contained in at most w(e) members of C. A subset S of arcs is called a feedback arc set in T if T\S is acyclic. The cycle packing problem is to find a cycle packing with maximum size, while the feedback arc set problem is to find a feedback arc set with minimum total weight. As is well known, the maximum size of a cycle packing is always less than or equal to the minimum size of a feedback arc set. In this talk, we will present a structural characterization of all tournaments T such that, for any nonnegative integral weight function w, the maximum size of a cycle packing is equal to the minimum size of a feedback arc set. Our characterization yields polynomial-time algorithms for the feedback arc set problem and the cycle packing problem on the corresponding tournaments. This is the joint work with Chen, Ding and Zang.