Proceedings

The Complexity of Tournament Fixing: Subset FAS Number and Acyclic Neighborhoods

Yuxi Liu, Junqiang Peng, Mingyu Xiao

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 3497-3504.

https://doi.org/10.24963/ijcai.2026/389

Keywords

  • Game Theory and Economic Paradigms: Computational social choice

Abstract

The Tournament Fixing Problem (TFP) asks whether a knockout tournament can be scheduled to guarantee that a given player v* wins. Although TFP is NP-hard in general, it is known to be fixed-parameter tractable (FPT) when parameterized by the feedback arc/vertex set number, or the in/out-degree of v*. However, it remained open whether TFP is FPT with respect to the subset FAS number of v* --- the minimum number of arcs intersecting all cycles containing v* --- a parameter that is never larger than the aforementioned ones. In this paper, we resolve this question negatively by proving that TFP stays NP-hard even when the subset FAS number of v* is constant ≥ 1 and either the subgraph induced by the in-neighbors D[N_{in}(v*)] or the out-neighbors D[N_{out}(v*)] is acyclic. Conversely, when both D[N_{in}(v*)] and D[N_{out}(v*)] are acyclic, we show that TFP becomes FPT parameterized by the subset FAS number of v*. Furthermore, we provide sufficient conditions under which v* can win even when this parameter is unbounded.

Yuxi Liu, Junqiang Peng, and Mingyu Xiao. 2026. The Complexity of Tournament Fixing: Subset FAS Number and Acyclic Neighborhoods. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 3497–3504. https://doi.org/10.24963/ijcai.2026/389
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards