Answer: Polynomial-time solvable: eventual feasibility holds exactly when every vertex of \(H\) is reachable from \(w\). The running time is \(O(m^2+L)\), so the problem is also FPT parameterized by \(k\), with \(f(k)=1\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe TOURNAMENT FIXING problem is solv- able in time 2O(k log k) ·nO(1) where n and k are the number of nodes and the feedback vertex set number of the input tournament D, respectively. So, additionally, our work subsumes the best known algo- rithm for TOURNAMENT FIXING with respect to the feed- back arc set number as the parameter. Following a certain guessing step that is similar to that done in both (Ramanu- jan and Szeider 2017; Gupta et al. 2018a), our approach di- verges significantly: specifically, we make (quite technically involved) use of dynamic programming.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), a complete type-level tournament \(H\) with distinguished player \(w\), rational mass vector \(\mu\), and resolution \(N=2^d\), form one tagged \(w\) plus \(N-1\) players with type counts obtained by fixed rounding of \((N-1)\mu\) and canonical within-type outcomes; does some balanced-bracket seeding make \(w\) win? The continuum-limit version asks whether this holds for every sufficiently large \(d\).
A society is given by its support: an ordered list \(T=(t_1,\ldots,t_\tau)\) of types with positive binary rational masses \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\geq1\) is the support size, not the number of possible types. A separate distinguished player \(w\) has no mass. The input includes a tournament \(H\) on \(T\cup\{w\}\); an arc means its source beats its target, with no ties.
For each integer \(d\geq1\), put \(N=2^d\), \(a_i=\lfloor(N-1)\mu_i\rfloor\), and \(r=N-1-\sum_i a_i\). Obtain counts \(c_i\) by adding one to the \(r\) entries with largest fractional remainders, breaking ties by the support order.
Form \(D_d\) from one player \(w\) and players \((t_i,j)\) for \(1\leq j\leq c_i\). Outcomes between distinct types, and against \(w\), follow \(H\); within each type, the smaller index wins.
Let \(A_d\) mean that a bijection of these players to the leaves of a perfect binary tree of depth \(d\) makes \(w\) win the resulting single-elimination tournament. Define eventual feasibility by \(\exists d_0\geq1\;\forall d\geq d_0:\ A_d\); the seeding may depend on \(d\).
Let \(m=\tau+1\), let \(L\) be the total input bit length, and let \(k\) be the feedback vertex set number of \(H\). State running times in \(m,\tau,L,k\); resolution \(d\) is quantified, not an input to eventual feasibility.
Is eventual feasibility in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, is it nevertheless FPT parameterized by \(k\), with running time \(f(k)(m+\tau+L)^{O(1)}\)?
For explicitly listed players, Tournament Fixing is [NP-complete](https://cgi.cse.unsw.edu.au/~sergeg/papers/AzizGMMSW14.pdf) and has a [\(2^{O(k_D\log(k_D+2))}n^{O(1)}\)-time algorithm](https://ojs.aaai.org/index.php/AAAI/article/download/25728/25500), where \(k_D\) is the player tournament's feedback vertex set number.
For explicitly represented type counts, counting draws with a winning player of a specified type is polynomial-time solvable for a constant number of types [Aziz et al.](https://cgi.cse.unsw.edu.au/~sergeg/papers/AzizGMMSW14.pdf). No result settling the exact eventual-feasibility problem above was located.
Eventual feasibility is polynomial-time solvable. More precisely, the following conditions are equivalent:
Thus a graph search from \(w\) decides the problem in \(O(m^2+L)\) time under the usual adjacency-matrix representation. In particular, the problem is FPT parameterized by \(k\), with \(f(k)=1\).
The sufficiency proof below constructs winning draws for every sufficiently large resolution, including the prescribed apportionment.
A strongly connected component is a maximal set of vertices mutually reachable by directed paths. Between two distinct strongly connected components of a tournament, all arcs have the same direction: arcs in both directions, together with paths inside the components, would make their union strongly connected.
Consequently, the component graph of a tournament is an acyclic tournament. It therefore has a unique source component, which beats every other component. Let \(S\) denote this component of \(H[T]\). Every type in \(S\) reaches every type in \(T\).
Suppose first that \(w\) loses to every type in \(S\). Once a draw contains an \(S\)-player, an \(S\)-player must win the draw. Indeed, a match involving an \(S\)-player always leaves an \(S\)-player as its winner: this holds against another \(S\)-player, against a type outside \(S\), and against \(w\).
All masses are positive, so every type in \(S\) appears at all sufficiently large resolutions. Hence eventual feasibility fails.
Conversely, if \(w\) beats some \(a\in S\), then \(w\) reaches every type through \(a\). If \(w\) beats no type in \(S\), no directed path starting at \(w\) can enter \(S\), because every vertex outside \(S\), including \(w\), loses to every vertex in \(S\). This proves the equivalence of conditions 2 and 3, and proves that eventual feasibility implies them.
It remains to prove sufficiency.
Write \(N=2^d\). The apportionment rule gives each type at least its floor allocation, so
\[ c_i\geq \lfloor(N-1)\mu_i\rfloor \geq (N-1)\mu_i-1 \geq N\mu_i-2. \]
Here the last inequality uses \(\mu_i\leq1\). No other property of the remainder ordering will be needed.
We may construct a perfect-tree draw by choosing a perfect matching of the surviving players in each round. Initially each player represents a one-leaf tree. Pairing two survivors merges their equal-height trees under a new root. Repeating this process produces a perfect binary tree and a bijection of the original players to its leaves.
Within-type outcomes affect the identity of the survivor, but never its type. Thus a construction specified through type counts can be realized using the labeled players in the question.
Assume that \(w\) beats a type \(a\), which we will preserve throughout the construction. Let \(b\neq a\) be a type to eliminate, and let \(p\neq b\) satisfy \(p\to b\).
Suppose the current round has an even total number \(n\) of survivors, including \(w\), with type counts \(c_i\), and \(c_a\geq1\). Perform the following matching:
The number of leftovers in the last step is even, because the first two kinds of matches removed an even number of players.
Let \(c'_i\) be the survivor counts. For every \(i\neq b\),
\[ c'_i\geq \left\lfloor\frac{c_i-\mathbf1_{i=a}}2\right\rfloor \geq \frac{c_i}{2}-1. \]
For \(i=p\), cross-type victories can only improve this lower bound; for every other \(i\neq b\), the within-type matches alone give the stated number of survivors.
There are two possibilities for the target:
\[ c'_p=c_p-\mathbf1_{p=a}, \qquad c'_b\leq \left\lceil\frac{B-P}{2}\right\rceil \leq\left\lceil\frac{c_b}{2}\right\rceil. \]
The ceiling accounts for the possible survival of the single leftover \(b\)-player.
Assume that \(w\to a\) for some \(a\in S\). Because \(a\) reaches every support type, choose a directed spanning tree on \(T\), rooted at \(a\), whose edges point from parent to child.
Eliminate the nonroot types in decreasing order of their tree depth. When eliminating \(b\), its parent \(p\) has not yet been eliminated and satisfies \(p\to b\).
Define
\[ \varepsilon=\min_i\mu_i,\qquad q=\left\lceil\log_2\frac4\varepsilon\right\rceil, \qquad R=(\tau-1)(q+1), \qquad M=16(q+2), \]
and take
\[ d_0=R+\left\lceil\log_2\frac M\varepsilon\right\rceil. \]
Fix any \(d\geq d_0\). After \(r\) rounds, the number of survivors is \(n_r=2^{d-r}\). For every \(r\leq R\),
\[ \varepsilon n_r\geq M. \]
We now prove that each elimination phase needs at most \(q+1\) rounds.
For every type whose elimination phase has not begun, and also for the root \(a\), maintain
\[ c_i^{(r)}\geq n_r\mu_i-2. \]
This holds initially by the rounding bound. A controlled round targeting a different type preserves it, because
\[ c_i^{(r+1)} \geq \frac{c_i^{(r)}}2-1 \geq n_{r+1}\mu_i-2. \]
In particular, \(a\) remains available to play against \(w\), since its count is at least \(M-2>0\). Every parent used in a phase also satisfies this bound.
The bound is not asserted for a type during its own elimination phase.
Consider a phase beginning with \(n\) survivors, target \(b\), parent \(p\), and initial parent count \(p_0\). The abundance bound gives
\[ p_0\geq \varepsilon n-2. \]
If \(b\) has not disappeared after \(j\) rounds of this phase, every preceding round had more available \(b\)-players than \(p\)-players; otherwise that round would have eliminated \(b\).
Consequently, the formulas from Section 3 imply
\[ c_p(j)\geq p_0-j, \qquad c_b(j)\leq \left\lceil\frac{c_b(0)}{2^j}\right\rceil \leq\left\lceil\frac n{2^j}\right\rceil. \]
The first inequality allows for losing one parent copy per round when \(p=a\). The second follows by iterating the ceiling-halving inequality.
If the target remains after \(q\) rounds, then
\[ c_b(q)\leq\frac{\varepsilon n}{4}+1, \]
because \(2^q\geq4/\varepsilon\). After reserving an \(a\)-player for \(w\), the available parent count is at least
\[ c_p(q)-\mathbf1_{p=a} \geq \varepsilon n-q-3. \]
Since \(\varepsilon n\geq M=16(q+2)\),
\[ \frac{\varepsilon n}{4}+1 \leq \varepsilon n-q-3. \]
Thus the next controlled round pairs every remaining \(b\)-player with a parent player and eliminates \(b\). The phase therefore lasts at most \(q+1\) rounds.
Applying this argument successively to the \(\tau-1\) nonroot types uses at most \(R\) rounds. Inductively, all these rounds lie within the range where the abundance bounds guarantee that the required matches are available.
After these phases, only \(w\) and \(a\)-players remain. In every subsequent round, pair \(w\) with an \(a\)-player and pair the other \(a\)-players among themselves. Because \(w\to a\), \(w\) wins the whole draw.
This constructs a winning draw for every \(d\geq d_0\), proving eventual feasibility.
The decision algorithm performs a directed graph search from \(w\) in \(H\) and accepts exactly when all vertices are reached. Its running time is \(O(m^2+L)\), hence \((m+\tau+L)^{O(1)}\). It needs neither a feedback vertex set nor the expanded player tournament \(D_d\).
Therefore the requested parameterized running time holds with \(f(k)=1\). As usual, membership in \(\mathrm P\) rules out NP-hardness unless \(\mathrm P=\mathrm{NP}\).
The construction also bounds the onset of feasibility. Under ordinary binary numerator-and-denominator encoding, \(\varepsilon\geq2^{-L}\), so \(q=O(L+1)\) and \(d_0=O(\tau(L+1)+\log(L+2))\). This threshold is not an input to the decision algorithm.
There is no conflict with [NP-completeness for explicitly listed players](https://cgi.cse.unsw.edu.au/~sergeg/papers/AzizGMMSW14.pdf): one prescribed finite draw can remain infeasible despite eventual feasibility. For example, let the support be \(a\to b\to c\to a\), with equal masses, and let \(w\) beat only \(a\). At depth \(2\), the counts are one of each support type. A winning \(w\) would have to beat \(a\) in the first round, then face \(b\), which beats both \(c\) and \(w\). Thus \(A_2\) is false, while the theorem proves eventual feasibility.
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct. The argument establishes eventual feasibility exactly when every vertex of \(H\) is reachable from \(w\), and therefore gives a polynomial-time decision algorithm. I found no major or minor mathematical issues.
The strongly connected component argument is valid. If two distinct components had arcs in both directions between them, their internal directed paths would make them mutually reachable, contradicting their distinctness.
The resulting component graph is an acyclic tournament. Such a graph has a unique source, and that source has an outgoing arc to every other component. Thus the source component \(S\) of \(H[T]\) beats every support type outside \(S\).
If \(w\) loses to every type in \(S\), the stated obstruction holds: any match involving an \(S\)-player produces an \(S\)-player as winner. Following the successive matches containing any initial \(S\)-player therefore forces the tournament winner to belong to \(S\).
Positive masses ensure that every type eventually appears: the floor allocation tends to infinity with \(d\). Consequently, this obstruction applies at every sufficiently large resolution, and eventual feasibility fails.
The equivalence between conditions 2 and 3 is also correct:
This establishes necessity and the claimed graph-theoretic equivalence.
The rounding estimate is correct:
\(c_i\geq\lfloor(N-1)\mu_i\rfloor\geq(N-1)\mu_i-1\geq N\mu_i-2\).
The last inequality uses \(0<\mu_i\leq1\). No upper rounding bound or assumption about remainder ties is needed later, so the proof covers the prescribed apportionment exactly.
The round-by-round matching construction correctly produces a perfect binary tree. All survivors entering a given round represent subtrees of equal height; pairing them merges those subtrees into equal-height trees for the next round. After \(d\) rounds, the construction yields the required tree and leaf bijection.
Within-type outcomes cause no difficulty. The construction requires only the survivor’s type, which is preserved regardless of which labeled player wins a within-type match.
The proposed matching is well-defined whenever the stated hypotheses hold. Reserving one \(a\)-player for \(w\) is legitimate because \(c_a\geq1\). After the \(w\)-match and the parent-target matches, within-type pairing leaves at most one player of each type. The number of leftovers is even, since an even number of players has been removed from an initially even population.
For every type other than \(b\), the lower bound
\(c'_i\geq\lfloor(c_i-\mathbf1_{i=a})/2\rfloor\geq c_i/2-1\)
is valid. For the parent \(p\), the cross-type victories compensate for players removed from within-type pairing. For other nontarget types, the guaranteed survivors come directly from within-type matches. Arbitrary leftover matches cannot remove those already guaranteed survivors.
Both target cases are correct:
The ceiling-halving bound used subsequently is therefore justified.
Reachability from \(a\) supplies the directed spanning tree used in the proof. Processing nonroot vertices in decreasing tree depth ensures that a target’s parent has not previously been targeted.
The abundance invariant is correct. Starting from the rounding bound, a round targeting another type gives
\(c_i^{(r+1)}\geq c_i^{(r)}/2-1\geq n_{r+1}\mu_i-2\).
This applies to the root throughout the construction and to each nonroot type until its own phase begins. In particular, the parent remains eligible for the invariant during its child’s phase.
The threshold also has the stated effect. For every \(d\geq d_0\) and \(r\leq R\),
\(\varepsilon n_r=\varepsilon 2^{d-r}\geq M\).
Thus the root has at least \(M-2>0\) copies whenever a controlled round is needed.
There is no requirement that a type remain abundant during its own elimination phase; the proof explicitly excludes that requirement.
Suppose a target survives \(j\) rounds of its phase. Every preceding round must have had \(B>P\), since the other case eliminates the target immediately. The controlled-round formulas therefore justify
\(c_p(j)\geq p_0-j\)
and
\(c_b(j)\leq\lceil c_b(0)/2^j\rceil\leq\lceil n/2^j\rceil\).
The parent loses at most one copy per round, precisely when it is the root reserved against \(w\). Iterating ceiling-halving gives the asserted target bound.
The definition of \(q\) implies \(2^q\geq4/\varepsilon\), so a surviving target after \(q\) rounds has at most \(\varepsilon n/4+1\) copies. The available parent count in the next round is at least \(\varepsilon n-q-3\).
The critical comparison is correct. It requires
\(3\varepsilon n/4\geq q+4\),
which follows from \(\varepsilon n\geq16(q+2)\). Thus the next round eliminates the target, proving the bound of \(q+1\) rounds per phase.
The global round budget is consistent with this argument. Before the \(j\)-th phase, at most \((j-1)(q+1)\) rounds have occurred, and that phase finishes by round \(j(q+1)\leq R\). Hence all rounds used in establishing the phase bound remain within the threshold’s guaranteed abundance range.
An eliminated type cannot reappear because every winner is one of the players participating in its match. After all nonroot phases, only \(w\) and root-type players remain.
Their total count remains a power of two. Whenever more than one player remains, the number of root-type players is odd, so pairing one against \(w\) leaves an even number for within-type matches. Since \(w\) beats the root type, the proposed completion succeeds.
The case \(\tau=1\) is covered: there are no elimination phases, \(R=0\), and the completion applies directly whenever \(w\) beats the sole type. If it loses, the necessity argument applies.
The proof establishes the required quantifiers. Its threshold depends only on the fixed input, and it constructs a successful draw for every \(d\geq d_0\).
Directed reachability in the adjacency-matrix representation takes \(O(m^2)\) time. Including input reading gives the claimed \(O(m^2+L)\) bound. Neither resolution nor expanded player counts are inputs to this algorithm.
Consequently, the parameterized bound holds with \(f(k)=1\). The qualification concerning NP-hardness unless \(\mathrm P=\mathrm{NP}\) is appropriate.
Under the stated binary numerator-and-denominator encoding, \(\varepsilon\geq2^{-L}\), giving the claimed bounds on \(q\) and \(d_0\).
The finite-draw example is correct. At depth \(2\), all three types have one player. To survive its first match, \(w\) must face \(a\); the other match is won by \(b\), which then defeats \(w\).
No additional clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.