Packing Feedback Arc Sets in Tournaments Exactly

• 成果类型: Article
• 署名作者: Chen, Xujin; Ding, Guoli; Zang, Wenan; Zhao, Qiulan
• 署名单位: Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Louisiana State University System; Louisiana State University; University of Hong Kong; Nanjing University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.1352
• 发表日期: 2024
• 关键词: circuits; conjecture; matroids; THEOREM; graphs; cycles

摘要

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.