Packing Feedback Arc Sets in Tournaments Exactly

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\backslash F$ contains no cycles (directed). A collection $\mathcal{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 $\mathcal{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.

Funding: This work was supported by the National Natural Science Foundation of China [Grants 11801266 and 11971228]; the Chinese Academy of Sciences [Grants XDA27000000 and ZDBS-LY-7008]; the Ministry of Science and Technology of China [Grant 2018AAA0101002]; the Research Grants Council of Hong Kong; the Fundamental Research Funds for the Central Universities [Grant 020314380035].