Packing Feedback Arc Sets in Tournaments Exactly (Xujin Chen)

Watch Video

05 29, 2023

  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

Contacts:

E-mail:

Copyright@2008,All Rights Reserved, Academy of Mathematics and Systems Science,CAS
Tel:86-10-82541777 Fax: 86-10-82541972 E-mail: contact@amss.ac.cn
京ICP备05002806-1号 京公网安备110402500020号