The Complexity of Tournament Fixing: Subset FAS Number and Acyclic Neighborhoods
Yuxi Liu, Junqiang Peng, Mingyu Xiao
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.
BibTeX
@inproceedings{ijcai2026_thecomplexityoft,
title = {The Complexity of Tournament Fixing: Subset FAS Number and Acyclic Neighborhoods},
author = {Yuxi Liu and Junqiang Peng and Mingyu Xiao},
booktitle = {IJCAI 2026},
year = {2026}
}