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

Abstract

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