---
title: "The Complexity of Tournament Fixing: Subset FAS Number and Acyclic Neighborhoods"
authors:
  - "Yuxi Liu"
  - "Junqiang Peng"
  - "Mingyu Xiao"
doi: "10.24963/ijcai.2026/389"
url: "https://ijcai.org/proceedings/2026/389"
pdf: "https://ijcai.org/proceedings/2026/0389.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "3497-3504"
track: "Main Track"
keywords:
  - "Game Theory and Economic Paradigms: Computational social choice"
---

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

Yuxi Liu, Junqiang Peng, Mingyu Xiao

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 3497-3504. DOI: [10.24963/ijcai.2026/389](https://doi.org/10.24963/ijcai.2026/389)

## 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.