Let T=(V,A) be a tournament with a nonnegative integral weight w(e) on each arc e. A subset F of arcs is called a feedback arc set (FAS) if T\F contains no cycles (directed). A collection F of FASs (with repetition allowed) is called an FAS packing if each arc e is used at most w(e) times by the members of F. The purpose of this paper is to give a characterization of all tournaments T=(V,A) with the property that, for every nonnegative integral weight function w defined on A, the minimum total weight of a cycle is equal to the maximum size of an FAS packing. Publication: Mathematics of Operations Research, Published Online: 23 Feb, 2023, https://doi.org/10.1287/moor.2023.1352
Author: Xujin Chen, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China (Email: xchen@amss.ac.cn); Guoli Ding, Mathematics Department, Louisiana State University, Baton Rouge, LA 70803, USA; Wenan Zang, Department of Mathematics, The University of Hong Kong, Hong Kong, China; Qiulan Zhao,Department of Mathematics, Nanjing University, Nanjing 210093, China
地址 北京市海淀区中关村东路55号 思源楼6-7层 南楼5-6、8层 邮编：100190 电子邮箱：iam@amss.ac.cn
