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

1 Introduction

Knockout tournaments represent a fundamental class of competition structures, characterized by a sequence of recursive elimination rounds [Horen and Riezman, 1985; Connolly and Rendleman, 2011; Groh et al., 2012]. In each round, players are partitioned into disjoint pairs (matches). For each pair, the loser is eliminated, and the winner advances to the next round. The process repeats until a single champion remains. Owing to their efficiency and simplicity, these structures are employed in large-scale events such as the FIFA World Cup [Scarf and Yusof, 2011] and the NCAA Basketball Tournament [Kvam and Sokol, 2006]. Beyond sports, they serve as critical models for elections, organizational decision-making, and various game-based settings where sequential elimination serves as a natural selection mechanism [Kim et al., 2017; Stanton and Williams, 2011a;

∗Corresponding author

Ramanujan and Szeider, 2017]. Consequently, knockout tournaments have attracted considerable attention in artificial intelligence [Vu et al., 2009; Williams, 2010], economics, and operations research [Rosen, 1985; Mitchell, 1983; Laslier, 1997], motivating a rich body of theoretical and applied studies.

Given a favorite player v∗ , a fundamental computational challenge is to determine whether the tournament be arranged to ensure that v∗ wins. Let N denote the set of n players, where n = 2c players (for some c ∈ N). The structure of a knockout tournament is represented by a complete (unordered) binary tree T with n leaves. A seeding is a bijection σ : N → leaves(T) that assigns each player to a distinct leaf. The tournament proceeds in rounds: in each round, for any internal node, the winners of the subtrees rooted at its children compete, with the winner advancing to this node. This continues until one player remains - the tournament champion.

The question becomes meaningful when predictive information about match outcomes is available. We model this with a tournament digraph D = (V = N,E), where V is the set of n players. For every distinct pair of vertices {u, v} ⊆ V , the arc set E contains exactly one of the ordered pairs (u, v) or (v, u), signifying that u defeats v or vice versa. We investigate the following problem:

TOURNAMENT FIXING PROBLEM (TFP)

Input: A tournament D and a player v∗ ∈ V (D). Question: Does there exist a seeding σ for the n = |V (D)| players such that v∗ wins the resulting knockout

tournament?

1.1 RelatedWork

The computational study of tournament manipulation was initiated by Vu et al. [2009]. The complexity of TFP, specifically its NP-hardness, remained open for several years [Vu et al., 2009; Williams, 2010; Russell and Van Beek, 2011; Lang et al., 2012]. Aziz et al. [2014] finally proved that TFP is NP-complete. They also provided exact exponentialtime algorithms running in O(2.83n ) time with exponential space, or 4n+o(n) time with polynomial space. Kim and Vassilevska Williams [2015] later improved this to 2nnO(1) time and space, and Gupta et al. [2018b] achieved the same time bound using only polynomial space.

Given the intractability of TFP in general, its parameterized complexity has been extensively investigated. We recall several key parameters studied in the literature and this paper:

• fas number (resp., fvs number): the minimum number of arc reversals (resp., vertex deletions) needed to make the tournament acyclic;
• in-degree (resp., out-degree) of v∗ : the number of inneighbors (resp., out-neighbors) of v∗ ;
• sfas-v number (resp., sfvs-v number): the minimum number of arc reversals (resp., vertex deletions, excluding v∗ ) needed to remove v∗ from all cycles;
• sfas-in number (resp., sfas-out number): the minimum number of arc deletions required to exclude the in-neighborhood of v∗ , i.e., Nin(v∗ ) (resp., the outneighborhood of v∗ , i.e., Nout(v∗ )) from cycles.

These parameters share the property that TFP becomes polynomial-time solvable when they equal zero. Their relationships are illustrated in Figure 1 (an arrow from x to y indicates x ≤ y).

The fas number, positioned at the top of this hierarchy, was first shown to be fixed-parameter tractable (FPT) by Ramanujan and Szeider [2017], who gave an algorithm running in pO(p2 )nO(1) time, where p is the fas number. This was subsequently improved to pO(p)nO(1) by Gupta et al. [2018a]. Later, Gupta et al. [2019] gave a polynomial kernel. For the fvs number q, Zehavi [2023] proved the FPT via a qO(q)nO(1) -time algorithm. This result subsumes the fasnumber parameterization since q ≤ p.

Wang et al. [2026] established that TFP is FPT parameterized by either the out-degree l or the in-degree k of v∗ , with running times 22l nO(1) and 22O(k) nO(1) , respectively.

It is not hard to see that when the sfas-v number or sfvs-number is zero, TFP becomes polynomial-time solvable. Furthermore, the sfas-v number and the sfvs-v number are smaller than fas and fvs, and the in-degree and out-degree of v∗ . Whether TFP is FPT parameterized by the smaller parameters the sfas-v number or the sfvs-v number becomes an interesting open problem in the literature [Wang et al., 2026].

1.2 Our Contributions

In this paper, we resolve the open problem concerning the parameterized complexity of TFP with respect to subset-based parameters centered around the favorite player v∗ . Our main contributions are:

• Negative Results: We prove that TFP remains NP-hard when:
• The sfas-v number (or sfvs-v number) is any constant ≥ 1, answering the open question from [Wang et al., 2026] in the negative.
• The sfas-in number (or sfas-out number) is 1.
• Positive Results: We identify tractable frontiers:
• TFP is FPT when parameterized by the sum of the sfas-in and sfas-out numbers.
• When both D[Nin(v∗ )] and D[Nout(v∗ )] are acyclic, TFP is FPT parameterized by the sfas-v number.
• Structural Insights: For an instance (D, v∗ ) with Nin(v∗ ) and Nout(v∗ ) both acyclic, we provide new sufficient conditions under which v∗ can be guaranteed to win, even when the relevant parameters are unbounded. These extend the known polynomial-time solvable cases and offer practical structural guarantees for tournament manipulability.

Our results complete the parameterized complexity landscape of TFP with respect to natural "distance-fromacyclicity" parameters localized around v∗ . The hardness results demonstrate that restricting cycles to involve only specific neighborhoods of v∗ does not generally lead to tractability, while the positive result identifies certain structural conditions that do. The hardness results can also be interpreted as a guarantee that this manipulation is computationally difficult to carry out in the cases studied.

Due to space constraints, the proofs of some lemmas are omitted, which can be found in the full version of this paper [Liu et al., 2026].

2 Preliminaries

In this paper, we only focus on digraphs. Let D = (V,E) be a digraph with n = |V | vertices and m = |E| edges. We denote the vertex set and edge set of a digraph D′ as V (D′ ) and E(D′ ), respectively. We use (u, v) to denote an arc from vertex u to vertex v. If there exists an arc (u, v) ∈ E, then we say that u is an in-neighbor of v and v is an outneighbor of u. The out-neighborhood and in-neighborhood of a vertex v is denoted by Nout(v) and Nin(v) respectively. For a vertex v, we further let out(v) = |Nout(v)| and in(v) = |Nin(v)|. For a vertex v and a vertex subset S ⊆ V , let outS(v) = |Nout(v)∩S| and inS(v) = |Nin(v)∩S|. For a vertex subset X ⊆ V , we define its out-neighborhood as Nout(X) = (⋃v∈X Nout(v)) \X and its in-neighborhood as Nin(X) = (⋃v∈X Nin(v)) \ X. We call a vertex s a source if in(s) = 0.

For a vertex subset X ⊆ V , the subgraph induced by X is denoted by D[X]. We write D - X to denote the subgraph D[V \X]. For a terminal set T ⊆ V , a vertex set X ⊆ V \T is a subset feedback vertex set of D with terminal set T if there is no cycle containing vertices in T in D-X. Similarly, an arc set A ⊆ E is a subset feedback arc set of D with terminal set T if there is no cycle containing vertices in T in D′ , where D′ is the resultant digraph after reversing arcs in A. We will always use v∗ to denote the favorite in the tournament.

A knockout tournament with n = 2p players for some integer p ≥ 0 is organized into log n successive rounds of competition. In each round r ∈ [logn], the 2logn-r+1 remaining players are paired into 2logn-r matches, with only the winners advancing to the next round. A seeding σ is a winning seeding for v∗ if v∗ survives all logn rounds of the resulting knockout tournament.

Following the notions established in [Wang et al., 2026], we utilize the concepts of match sets and match set sequences to formally characterize the matches played in each round of a knockout tournament.

Definition 1 (match set and sequence). Let D be a tournament with n players. For a fixed seeding σ, we define:

• Match Set: For each round r ∈ [logn], the match set Mr ⊆ E(D) is the set of arcs representing matches played in round r, where |Mr| = 2logn-r . Each pair (u, v) ∈ Mr indicates that player u defeated v. Let V (Mr) denote the set of players who participated in round r;
• Match Set Sequence: A match set sequence is an ordered collection of match sets for all rounds, defined as M= {M1, . . . ,Mlog n}.

A match set sequence {M1, . . . ,Mlogn} is valid for D if the following conditions hold:

• For every round r ∈ [p], Mr ⊆ E(D).
• V (M1) = V (D);
• For every round r ∈ [log n-1], the set of winners inMr is exactly V (Mr+1).

Given a seeding σ, it induces a unique match set sequence, denoted by M(σ). In contrast, if a match set sequence M∗ is valid, then there exists at least one seeding σ∗ such that M(σ∗ ) = M∗ .

To formally track the progression of the tournament, we introduce notation for the sets of winners and eliminated players in each round. Let D be a tournament with n players, and let M(σ) = (M1, . . . ,Mk) be the match set sequence induced by a seeding σ. For each round r ∈ [logn], we use Cr(σ) = {u | (u, v) ∈ Mr} to denote the set of players remaining after round r. By convention, we define C0(σ) = V (D). Correspondingly, for each r ∈ [logn], we use Lr(σ) = {v | (u, v) ∈ Mr} to denote the set of players eliminated in round r. Where the seeding σ is clear from the context, we simply write Cr and Lr.

3 Parameterized by the Subset FAS Number

In this section, we investigate the complexity of TFP when parameterized by the sfas-v/in/out number. We will show that TFP is para-NP-hard with respect to these parameters, thereby completing the parameterized complexity landscape illustrated in Figure 1.

Before presenting our main results, we define a kind of restricted instances, called special instances, and characterize several properties of winning seedings for a special instance.

Definition 2. An instance (D, v∗ ) is special with respect to a∗ ∈ Nout(v∗ ) and b∗ ∈ Nin(v∗ ) if

1. |Nout(v∗ )| = 3|Nin(v∗ )| -1, where |Nin(v∗ )| = 2p for some integer p ≥ 0;
2. There is an arc (a∗ , b∗ ) ∈ E(D), and
3. For each vertex a ∈ Nout(v∗ ) and each vertex b ∈ Nin(v∗ ) expect the case that a = a∗ and b = b∗ , there is an arc (b, a) ∈ E(D).

See Fig. 2 for an illustration for a special instance (D, v∗ ). We introduce the "special instance" because it serves as a gadget utilized in the proofs of both Theorem 1 and Theorem 2. Intuitively, this instance ensures that under a winning seeding, with the exception of the specific match between a∗ and b∗ , no other player from Nout(v∗ ) competes against a player fromNin(v∗ ). The following lemma formally introduces this property.

Lemma 1. Consider a special instance (D, v∗ ) where n = |Nout(v∗ )|. Suppose (D, v∗ ) is a yes-instance. Let σ be an arbitrary winner seeding for v∗ in tournament D and let its corresponding match set sequence be M∗ = {M ∗ 1 , . . . ,M ∗ (log n)+2 }. We have the following properties.

1. V (M ∗ (log n)+1 ) ∩ Nin(v∗ ) = {b∗ }.
2. |V (M ∗ (logn)+1 ) ∩ Nout(v∗ )| = 2 and a∗ ∈ V (M ∗ (log n)+1 ).
3. For each round r ∈ [logn], every match in Mr involves either two players in A ∪ {v∗ } or two players in B.

Proof. Assume that player v∗ beats player x1 ∈ V (D) in the last match, and in the second last round, v∗ beats x2 and x1 beats x3; that is, M ∗ (log n)+1 = {(v∗ , x2), (x1, x3)} and M ∗ (logn)+2 = {(v∗ , x1)} for some x1, x2, x3 ∈ V (D). Let M ∗ (logn)+1 = {(v∗ , x2), (x1, x3)} and M ∗ (logn)+2 = {(v∗ , x1)} for some x1, x2, x3 ∈ V (D). Since v∗ beats x1 and x2, we know that x1 and x2 are in Nout(v∗ ). Now we show that x3 ∈ Nin(v∗ ).

For round r ∈ [logn], let Br-1 = Cr-1(σ) ∩ Nin(v∗ ) be the players in Nin(v∗ ) remain after round r - 1. By the definition of D, we know that for any player b ∈ Nin(v∗ )\b∗ , b can only be beaten by players in Nin(v∗ ). If b∗ remains in this round, we know there are at most ⌈ 1 2 |Br-1 \ b∗ |⌉ vertices in Br-1 are eliminated. If b∗ is eliminated in this round, we know there are at most ⌊ 12 |Br-1 \ b∗ |⌋ vertices in Br-1 \ b∗ are eliminated, which implies that there are at most ⌊ 1 2 |Br-1 \ b∗ |⌋+1 = ⌈ 12 |Br-1|⌉ vertices inBr-1 are eliminated. Thus, we have that in each round r ∈ [logn], there are at most half of the vertices with indegree of v∗ are eliminated, i.e.,

which means that

Since |B0| = |Nin(v∗ )| = n and n = 2p for some integer p ≥ 0, we have that |Blogn| ≥ 1, which means that there are at least one vertex in Nin(v∗ ) remains after round logn. Thus, x3 ∈ Nin(v∗ ). Since x1 beats x3 and x1 ∈ Nout(v∗ ), we know that x1 = a∗ and x3 = b∗ . Thus, the first two properties hold.

Before we show the correctness of the third property. Recall that there are at most ⌈ 12 |Br-1 \b∗ |⌉ vertices in Br-1 \b∗ are eliminated in round r ∈ [log n]. Since b∗ cannot be eliminated before round (log n) + 1, we indeed have that for each round r ∈ [log n],

which means that

Now we show that the third property holds. By contradiction, assume there exists a match (b, a) ∈ M ∗ r0 for some r0 ∈ [logn] such that a ∈ Nout(v∗ ) and b ∈ Nin(v∗ ). Let r be the first round that there exists such match. We have that |Br-1| = |Nin(v∗ )|/2r-1 is an even number. Since each player in Nin(v∗ ) \ b∗ can only be beaten by Nin(v∗ ) and b∗ remains after round log n, we have that

Thus, we have that

which means that there are at least two players in Nin(v∗ ) remains after round logn. However, v∗ , x1 and x2 are not in Nin(v∗ ), a contradiction. This completes the proof of the third condition.

Consider a special yes-instance (D, v∗ ) and an arbitrary winning seeding σ. The three properties stated in Lemma 1 hold for σ. The corresponding complete binary tree T corresponding to σ is shown in Fig. 3. One of the main results of this section is the following theorem:

Theorem 1. For an input tournament D and a favorite player v∗ ∈ V (D), TFP is NP-hard even when the sfas-v number equals 1.

Proof. We will show a polynomial-time reduction from TFP to TFP with subset FAS number of v∗ that equals to 1. Specifically, consider a TFP instance (D, v∗ ) with n = |D|, we construct an equivalent instance (D′ = ({v′ } ∪ A ∪ B,E′ ), v′ ) as follows.

• D′ [A] is an acyclic tournament with 3n - 1 vertices where a∗ ∈ A is the source vertex in D′ [A].
• D′ [B] is a copy of D where b∗ ∈ B is the copy of v∗ .
• For each a ∈ A, there is an arc (v′ , a) in E′ . For each b ∈ B, there is an arc (b, v′ ) in E′ .
• (a∗ , b∗ ) ∈ E′ and for each vertex a ∈ A and each vertex b ∈ B expect the case that a = a∗ and b = b∗ , there is an arc (b, a) ∈ E′ .

Clearly, Nout(v′ ) = A and Nin(v′ ) = B, and (D′ , v′ ) is a special instance with respect to a∗ and b∗ . Now we prove both directions of the equivalence of (D, v∗ ) and (D′ , v′ ).

Forward direction. Assume that there exists a winning seeding σ for v∗ in tournament D (also for b∗ in tournament D′ [B]) and let its corresponding match set sequence be M∗ = {M1, . . . ,Mlog n}.

Let (A1,A2,A3) be a partition of D′ [A] such that |A1| = |A2| = n, |A3| = n - 1, and a∗ ∈ A1. So |A1| = |A2| = |A3 ∪ {v∗ }| = |B| = n. Now we construct four seedings for D′ [A1], D′ [A2], D′ [A3 ∪ {v∗ }] and D′ [B] respectively, and then obtain a winning seeding for v′ in D′ based on these four seedings.

1. Let σ1 be an arbitrary seeding in tournament D′ [A1]. Then a∗ must be the winner of D′ [A1] under σ1 since a∗ is a source vertex in D′ [A].
2. Let σ2 be an arbitrary seeding in tournament D′ [A2] with winner a′ .
3. Let σ3 be an arbitrary seeding in tournament D′ [A3 ∪ {v′ }]. Then v′ must be the winner of D′ [A3∪{v′ }] under σ3 since for each a ∈ A, there is an arc (v′ , a) ∈ E(D′ ).
4. Recall that σ is a winning seeding for b∗ in tournament D′ [B].

For σi (i = 1, 2, 3), the corresponding match set sequence is defined as M(σi) = {M i1 , . . . ,M i logn }. Recall that the corresponding match set sequence of σ is M∗ = {M1, . . . ,Mlog n}.

The match set sequenceM′ is then defined as:

where M ′r = Mr ∪ ⋃i∈{1,2,3} M i r for each r ∈ [logn]. M′ is obtained by unioning the match set sequences of B, A1, A2 and A3 ∪ {v′ }, and adding two new rounds {(v′ , a′ ), (a∗ , b∗ )}, {(v′ , a∗ )}, which is a valid match set sequence for V (D′ ).

Let σ′ be a corresponding seeding for M′ , note that σ′ ensures that v′ wins. Thus, there exists a winning seeding for v′ in tournament D′ .

Reverse direction. Assume that there exists a winning seeding σ′ for v′ in tournament D′ and let its corresponding match set sequence be

By the third property of Lemma 1, there exists a match set sequence M = {M1, . . . ,Mlogn} such that for each round r ∈ [logn], Mr ⊆ M ′r andM is valid for Nin(v′ ). Furthermore, by the first property of Lemma 1, the corresponding seeding σ forMensures that b∗ is the winner. Since B is the copy of D and b∗ is the copy of v∗ , we have that σ maintains that v∗ wins. Thus, (D, v∗ ) is a yes-instance.

Clearly, the construction ensures that the sfvs-v number equals 1. We have the following corollary.

Corollary 1. For an input tournament D and a favorite player v∗ ∈ V (D), TFP is NP-hard even when the size of subset feedback vertex set of D with terminal set {v∗ } is 1.

We further consider two larger parameters: the sfas-in number and the sfas-out number. Note that both are not smaller than the sfas-v number since each cycle traversing v∗ must intersect both Nin(v∗ ) and Nout(v∗ ). Nevertheless, we will show that TFP is NP-hard even when the sfas-in number equals 1 or the sfas-out number equals 1. Notably, the reduction established in Theorem 1 already yields the result for the sfas-out number, as the construction ensures that D′ [Nout(v∗ )] is an acyclic tournament. We directly obtain the following corollary.

Corollary 2. For an input tournament D and a favorite player v∗ ∈ V (D), TFP is NP-hard even when the size of subset feedback arc set of D with terminal set Nout(v∗ ) is 1.

By modifying the construction used in Theorem 1, we have the following theorem.

Theorem 2. For an input tournament D and a favorite player v∗ ∈ V (D), TFP is NP-hard even when the sfas-in number equals 1.

proof sketch. We will show a polynomial-time reduction from TFP to TFP with the sfas-in number that equals to 1. Specifically, consider a TFP instance (D, v∗ ) with n = |D|, we construct an equivalent instance (D′ = ({v′ } ∪A′ ∪A∪ B, E′ ), v′ ) as follows.

• D′ [A′ ] is an acyclic tournament with 2n - 1 vertices.
• D′ [B] is an acyclic tournament with n vertices where b∗ ∈ B is the source vertex in D′ [B].
• D′ [A] is a copy of D where a∗ ∈ A is a copy of v∗ .
• For each a ∈ A′ ∪ A, there is an arc (v′ , a) in E′ . For each b ∈ B,there is an arc (b, v′ ) in E′ .
• (a∗ , b∗ ) ∈ E′ and for each vertex a ∈ A′ ∪ A and each vertex b ∈ B expect the case that a = a∗ and b = b∗ , there is an arc (b, a) ∈ E′ .

See Fig. 4 for an illustration. Clearly, Nout[v′ ] = A∪A′ and Nin[v′ ] = B, and (D′ , v′ ) is a special instance with respect to a∗ and b∗ . The proof of the equivalence of (D, v∗ ) and (D′ , v′ ) is similar to that of Theorem 1 and is deferred to the full version.

4 Some Tractable Cases

So far, we have presented some hardness results for the TFP problem. These results can also be understood in the following way. We can partition the tournament, apart from vertex v∗ , into three components: (i) D[Nin(v∗ )], (ii) D[Nout(v∗ )], and (iii) the arcs between Nin(v∗ ) and Nout(v∗ ).

When the value of the sfas-in number (resp. sfas-out number) is small, it indicates that the structure of component (i) (resp. component (ii)) becomes relatively simple. When the sfas-v number is small, it implies that component (iii) is relatively simple. Our previous studies essentially reveal whether the problem becomes easier to solve when certain components among these three have simple structures. Theorem 1 shows that TFP remains NP-hard even when components (i) and (iii) are simple in structure. Theorem 2 shows that TFP remains NP-hard even when components (ii) and (iii) are simple in structure.

A natural remaining question is whether the problem becomes tractable when components (i) and (ii) are simple in structure. In the following, we address this question by presenting tractable results.

First, we show that TFP is FPT when parameterized by the sfas-v number. Our approach leverages the following known result about the fvs number.

Lemma 2 ([Zehavi, 2023]). TFP is solvable in time 2O(t log t) · nO(1) where n and t are the number of nodes and the fvs number, respectively.

By applying Lemma 2, we establish the following result.

Theorem 3. Given an instance (D, v∗ ) of TFP, the problem can be solved in time 2O(s log s) · nO(1) , where n = |V (D)| and s is the sum of the sfas-in number and the sfas-out number.

A proof of Theorem 3 can be found in the full version.

Next, we show that if we restrict that the in-neighborhoods and out-neighborhoods of the favourite are both acyclic, then TFP is FPT with respect to the sfas-v number.

Definition 3. An instance (D, v∗ ) is called a neighbor-acyclic instance if the induced digraphs D[Nin(v∗ )] and D[Nout(v∗ )] are both acyclic.

Theorem 4. Given a neighbor-acyclic instance (D, v∗ ) of TFP, the problem can be solved in time 2O(k log k) · nO(1) , where n = |V (D)| and k is the sfas-v number.

A proof of Theorem 4 can be found in the full version.

5 Acyclic Neighborhood Structures

In this section, we investigate several sufficient conditions for a neighbor-acyclic instance (D, v∗ ) that guarantee (D, v∗ ) is a yes-instance. We hope these structural results can be helpful to understand neighbor-acyclic instances.

A player v is a king if v has distance at most 2 to every other player in the tournament graph.(i.e., for each u, v either beats u or beats another w that beats u). Similarly, a 3-king is a player that has distance at most 3 to every other player. A significant research direction involves identifying broad classes of instances that admit efficient solutions. Prior work has established several sufficient conditions under which a given player can be guaranteed to win [Williams, 2010; Stanton and Williams, 2011b; Kim and Williams, 2015; Kim et al., 2017]. Furthermore, the corresponding winning seedings can be constructed in polynomial time, which implies that the winner is susceptible to manipulation in many practical settings. A substantial portion of these established conditions focuses on players who are kings.

Consider a neighbor-acyclic instance (D, v∗ ) where D contains a source. If v∗ is the unique source, the instance is trivially a yes-instance; Othervise it is trivially a no-instance. Consequently, we focus on the case where there is no source in D. We first establish that in this case, v∗ is a 3-king.

Lemma 3. Let (D, v∗ ) be a neighbor-acyclic instance where there is no source in D. Then, v∗ is a 3-king.

Proof. For each vertex a in Nout(v∗ ), we know that the distance from v∗ to a is 1. Let b∗ be the source of D[Nin(v∗ )]. Since b∗ is not a source of whole tournament D, there exists a vertex a′ in Nout(v∗ ) such that (a′ , b∗ ) ∈ E(D). Thus, we know that the distance from v∗ to b∗ is 2. Since b∗ is the source of D[Nin(v∗ )], for each vertex b ∈ Nin(v∗ ), we know that the distance from v∗ to b is at most 3. Thus, v∗ is a 3-king.

The following known result provides a sufficient condition guaranteeing the favorite player v∗ is a winner for the case that v∗ is a 3-king.

Lemma 4 ([Kim and Williams, 2015]). Let (D, v∗ ) be an instance where v∗ is a 3-king. Let A = Nout(v∗ ),B = Nout(A) ∩ Nin(v∗ ) and C = Nin(v∗ ) \ B. Then, (D, v∗ ) is guaranteed to be a yes-instance if the following conditions hold.

1. |A| ≥ |V (D)|/3.
2. ∀b ∈ B, out(b) ≤ out(v∗ ).
3. There is a perfect matching from B onto C.

Furthermore, a winning seeding for v∗ can be found in polynomial time.

While the equalities in Lemma 4 can simultaneously hold for general instances, we remark that the first equality cannot hold for neighbor-acyclic instances with no sources in tournaments. Consider a neighbor-acyclic instance (D, v∗ ) where D contains no source. Let A = Nout(v∗ ) and B = Nout(A)∩Nin(v∗ ). Let b∗ be the source inD[Nin(v∗ )]. Since b∗ is not a source in D, we know that b∗ ∈ Nout(A). Thus, b∗ ∈ B. By the second condition of Lemma 4, we know that out(b∗ ) ≤ out(v∗ ) = |A|. Note that since b∗ is a source in D[N -(v∗ )], its out-degree is at least |Nin(v∗ )| - 1 plus |{v∗ }|, yielding out(b∗ ) ≥ |Nin(v∗ )|. Thus, we have that |Nin(v∗ )| ≤ |Nout(v∗ )|, which implies that |A| ≥ |V (D)|/2. This gap between the 1/3 threshold in Lemma 4 and the 1/2 lower bound necessitated by the DAG structure motivates the following theorem.

Theorem 5. Let (D, v∗ ) be a neighbor-acyclic instance such that D has no source. Let A = Nout(v∗ ) and B = Nin(v∗ ). Then (D, v∗ ) is guaranteed to be a yes-instance if the following conditions hold.

proof sketch. We prove the theorem by induction on the number of vertices n = |V (D)|. To this end, for any induced subgraph D′ of D containing v∗ , we define an invariant property I(D′ ) consisting of the following two conditions:

Our inductive claim is that for any induced subgraph D′ containing v∗ whose order is a power of two, if I(D′ ) holds, then (D′ , v∗ ) is a yes-instance.

For the base case n = 2, since |A′ | ≥ n/3, we have |A′ | ≥ 1, meaning v∗ defeats the only other player.

For the inductive step, assume that the claim holds for all tournaments of size n/2. Now consider an arbitrary tournament of size n that satisfies the invariant. We denote this tournament by D′ . For simplicity of notation, we write in′ (·) and out′ (·) for the in-degree and out-degree within D′ (i.e., inV (D′ )(·) and outV (D′ )(·)), and let A′ = Nout(v∗ )∩V (D′ ) and B′ = Nin(v∗ ) ∩ V (D′ ).

The main idea is to construct a match set M on V (D′ ) to serve as the first round of the knockout tournament. We will then show that the set of winners of this round, denoted by Vwin, satisfies the invariant I(D′ [Vwin]). By the inductive hypothesis, this implies that v∗ wins in the smaller tournament D′ [Vwin], and consequently wins in D′ .

Before presenting the construction of the match set, we first derive a useful bound for the vertices in B′ . Let A′ = {a1, . . . , a|A′ |} and B′ = {b1, . . . , b|B′ |} be topologically ordered such that (ai, aj) ∈ E(D′ ) and (bi, bj) ∈ E(D′ ) for all i < j. Consider any vertex bi ∈ B′ . We have out′ (bi) = out′A′ (bi) + out′B′ (bi) + |{v∗ }| = out′A′ (bi) + (|B′ | - i) + 1. Since out′ (bi) ≤ |B′ | (Condition (ii) of the invariant), we have out′A′ (bi) + |B′ | - i + 1 ≤ |B′ |, which simplifies to

We distinguish two cases based on the parity of |A′ | and |B′ |. Case 1. |B′ | is odd and |A′ | is even.

Let k = (|B′ | + 1)/2. From Eq. (1), we have out′A′ (bk) ≤ k -1. Consequently, the in-degree of bk fromA′ satisfies:

Since |A′ | ≥ n/3, we have 3|A′ | ≥ n, which implies in′A′(bk) ≥ 1. Thus, there exists a vertex a′ ∈ A′ such that (a′ , bk) ∈ E(D′ ). Let MA be an arbitrary perfect match set on A′ \ {a′ , a|A′ |} and let MB = ⋃k-1 i=1 {(bi, bi+k)}. The match set M for the first round is constructed as

Clearly, the set of winners is Vwin = {v∗ } ∪ Awin ∪ Bwin, where Awin consists of a′ and the winners fromMA (implying |Awin| = |A′ |/2) and Bwin = {b1, . . . , bk-1}.

We show that the invariant I(D′ [Vwin]) holds. Condition (i) holds since |Awin| = |A′ |/2 ≥ (n/2)/3. Now consider Condition (ii). For any bi ∈ Bwin, we have out′Vwin (bi) = out′Awin (bi) + out′Bwin (bi) + 1. Note that out′Awin (bi) ≤ out′A′ (bi) ≤ i - 1 (by Eq. (1)) and out′Bwin (bi) = |Bwin| - i. Thus, it holds that out′Vwin (bi) ≤ (i-1)+(|Bwin|-i)+1 = |Bwin|, which proves Condition (ii).

Case 2. |B′ | is even and |A′ | is odd.

The proof proceeds analogously to Case 1. The full proof of this part can be found in the full version.

Now we consider the case that the favorite player v∗ is a king. For general instances, the following known result provides a sufficient condition for v∗ to be a winner.

Lemma 5 ([Kim and Williams, 2015]). Let (D, v∗ ) be an instance where v∗ is a king. Let k be the cardinality of the maximum matching from Nout(v∗ ) to Nin(v∗ ). Then, (D, v∗ ) is guaranteed to be a yes-instance if |Nout(v∗ )|+k > |V (D)|/2. Furthermore, a winning seeding for v∗ can be found in polynomial time.

For a neighbor-acyclic instance where v∗ is a king, we establish the following structural result.

Theorem 6. Let (D, v∗ ) be a neighbor-acyclic instance where v∗ is a king. Then, (D, v∗ ) is guaranteed to be a yesinstance if ∀b ∈ Nin(v∗ ), out(b) < 2out(v∗ ). Furthermore, a winning seeding for v∗ can be found in polynomial time.

Proof. Let n = |V (D)|. Let A = Nout(v∗ ) and B = Nin(v∗ ). With Lemma 5, it is sufficient to construct a matching of size k from A to B such that |A| + k > n/2. Since v∗ is a king, there should be at least one arc from A to B. If |A| ≥ n/2, we can construct a matching of size k ≥ 1, and then |A| + k > n/2 follows immediately. Next, we consider the remaining case |A| < n/2.

Let B = {b1, b2, . . . , b|B|} such that for each 1 ≤ i < j ≤ |B|, (bi, bj) ∈ E(D). For each bi ∈ B, we have inB(bi) + outB(bi) = |B| - 1 and inB(bi) = i - 1, and thus

Since out(bi) < 2out(v∗ ) = 2|A|, we have

Let p = n - 2|A|. We define the indexing function π : [p] → [p] as π(q) = 1 + n - 2|A| - q. Note that for each q ∈ [p], it holds that

which implies inA(bπ(q)) ≥ q.

We construct a matching M of size k = min(p, |A|) from A to B, where M = {(aq, bπ(q)) : q ∈ [k]}, by picking an arbitrary aq ∈ Nin(bπ(q)) ∩A\ {a1, . . . , aq-1} iteratively. The existence of aq is guaranteed by a simple counting argument: since |Nin(bπ(q)) ∩A| = inA(bπ(q)) ≥ q, there always exists an in-neighbor of bπ(q) in A that has not been matched in the previous q - 1 steps.

We then show that |A| + k > n/2 holds under k = min(p, |A|) = min(n-2|A|, |A|). By substituting i = 1 into Eq. (2), we obtain inA(b1) > n - 2|A| - 1. With inA(b1) ≤ |A|, it follows that n - 2|A| - 1 < |A|, which simplifies to n - 2|A| ≤ |A|. Thus, k = min(n - 2|A|, |A|) = n - 2|A|. Since |A| < n/2, we have |A| + k = n - |A| > n/2. This completes the proof.

Remark. The bound ∀b ∈ Nin(v∗ ), out(b) < 2out(v∗ ) is tight. Specifically, if we replace this bound with ∀b ∈ Nin(v∗ ), out(b) ≤ 2out(v∗ ), then there exists a no-instance. For the detailed analysis, please refer to the full version.

6 Conclusion

In this paper, we resolved the parameterized complexity of TFP with respect to several subset feedback set-based parameters centered around the favorite player v∗ . We showed that TFP remains NP-hard even when the sfas-v number is constant, answering an open question in the negative. We also established hardness for constant sfas-in and sfas-out numbers. On the positive side, we proved that TFP becomes fixedparameter tractable when parameterized by the sum of the sfas-in and sfas-out numbers, and identified sufficient conditions for v∗ to win in the neighbor-acyclic case. It remains open whether TFP is NP-hard when both D[Nin(v∗ )] and D[Nout(v∗ )] are acyclic.

Acknowledgments

We thank the anonymous reviewers for their valuable comments and suggestions that helped improve the quality of this paper. The work is supported by the National Natural Science Foundation of China, under the grants 62372095 and 62502078.