d4-conf-ijcai-2018-0577 (d4-conf-ijcai-2018-0577)

Given entrant types \(T\), a tournament relation \(\succ\) between distinct types, rational initial masses \(\mu_t\) summing to \(1\), a target type \(t^\star\), and \(R\) bracket rounds, decide whether nonnegative match masses \(x^r_{\{t,u\}}\) and survivor masses \(p_t^r\) exist with \(p_t^0=\mu_t\), \(2x^r_{\{t,t\}}+\sum_{u\ne t}x^r_{\{t,u\}}=p_t^{r-1}\), and \(p_t^r=x^r_{\{t,t\}}+\sum_{u\ne t:\,t\succ u}x^r_{\{t,u\}}\), such that \(p_{t^\star}^R=2^{-R}\).

A society is given by its support \(T\): the list of its \(\tau\) entrant types with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; set \(m=|T|=\tau\).
The input also contains a tournament relation \(\succ\) on distinct types, a target \(t^\star\in T\), and a positive integer \(R\) encoded in unary. Exactly one of \(t\succ u\) and \(u\succ t\) holds for distinct types; there are no draws.
Mass is divisible. Every round pairs all surviving mass without byes; a match between different types retains the winning type, and a match within one type retains half its participating mass.
For each \(r\in\{1,\ldots,R\}\), let \(x^r_{\{t,u\}}\) be a nonnegative real match mass indexed by unordered pairs, allowing \(t=u\), and let \(p_t^r\) be nonnegative real survivor mass. Require \(p_t^0=\mu_t\) and, for every \(t\in T\),
\[2x^r_{\{t,t\}}+\sum_{u\in T\setminus\{t\}}x^r_{\{t,u\}}=p_t^{r-1},\qquad p_t^r=x^r_{\{t,t\}}+\sum_{u\in T:\,t\succ u}x^r_{\{t,u\}}.\]
The decision problem asks whether such masses exist with \(p_{t^\star}^R=2^{-R}\). Let \(k\) be the minimum number of arcs whose deletion makes the type tournament acyclic, and let \(L\) be the total input bit length. State running times in \(m,\tau,L,R\), and \(k\) where relevant.

Is this continuous tournament-fixing problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, is it fixed-parameter tractable with parameter \(k\)?

For discrete balanced knockout tournaments on \(n=2^R\) players, deciding whether a designated player can win is [NP-complete](https://cgi.cse.unsw.edu.au/~sergeg/papers/AzizGMMSW14.pdf).
It admits an algorithm with running time \(2^{O(k\log k)}n^{O(1)}\), where \(k\) is the player tournament's feedback arc set number ([Gupta et al.](https://www.ijcai.org/proceedings/2018/0038.pdf)). No result settling the exact continuous formulation above was located.

Result

The stated continuous problem is in \(\mathrm{P}\). It can be decided in time
\((Rm^2+L)^{O(1)}=(R\tau^2+L)^{O(1)}\).
Consequently, it is also fixed-parameter tractable with parameter \(k\), with no dependence on \(k\) required.

The proof applies to exactly the divisible-mass formulation in the question.

1. Total survivor mass

Let \(\mathcal U\) be the set of unordered pairs of types, including self-pairs. Thus \(|\mathcal U|=m(m+1)/2\). Define
\(S_r=\sum_{t\in T}p_t^r\).

Summing the participation equations over all types gives
\(S_{r-1}=2\sum_{e\in\mathcal U}x_e^r\).
Indeed, a self-pair contributes twice through its coefficient \(2\), and each distinct-type pair appears once in each endpoint’s equation.

Summing the survivor equations gives
\(S_r=\sum_{e\in\mathcal U}x_e^r\).
Each self-pair contributes once, and each distinct-type pair contributes once because exactly one endpoint wins.

Therefore \(S_r=S_{r-1}/2\). Since \(S_0=1\), induction yields
\(S_r=2^{-r}\).

In particular, nonnegativity implies that the requested equality
\(p_{t^\star}^R=2^{-R}\)
is equivalent to having all terminal survivor mass of the target type. There is no missing terminal condition.

2. An exact linear feasibility formulation

Introduce one variable \(x_e^r\) for each \(e\in\mathcal U\) and each round, and one variable \(p_t^r\) for each type and each round. Substitute the input constants \(\mu_t\) for \(p_t^0\).

Impose precisely the participation and survivor equations from the question, nonnegativity of every variable, and the terminal equation
\(p_{t^\star}^R=2^{-R}\).

These form a rational linear system
\(Ay=b,\ y\geq 0\).
In particular, linking consecutive rounds introduces only linear terms \(p_t^{r-1}\); there are no products of variables.

Its number of variables is
\(N=R\bigl(m(m+1)/2+m\bigr)=Rm(m+3)/2\),
and its number of equality constraints is
\(E=2Rm+1\).

Equivalence. Any schedule satisfying the question supplies a feasible vector \(y\). Conversely, every feasible vector supplies nonnegative match and survivor masses satisfying every requirement of the question. Thus the decision problem is exactly the feasibility problem for this linear system.

3. Encoding size and polynomial running time

Every entry of \(A\) belongs to \(\{-2,-1,0,1,2\}\). The only nonzero entries of \(b\) are the initial masses and the terminal value \(2^{-R}\).

The initial masses already have total encoding length at most \(L\). The terminal value can be written as the rational number \(1/2^R\); its denominator has \(R+1\) binary digits. Hence this value requires \(O(R)\) bits, despite its potentially small magnitude.

Even a dense encoding of the equality matrix and right-hand side has length
\(B=O(EN+L+R)=O(R^2m^3+L+R)\).
It can be constructed in time polynomial in \(Rm^2+L\).

We use the following standard theorem: feasibility of a finite system of linear equalities and weak inequalities with binary-encoded rational coefficients is decidable exactly in deterministic time polynomial in its encoding length. This is the polynomial-time rational linear programming theorem established by [Khachiyan](https://www.mathnet.ru/eng/dan42319).

All hypotheses hold here: the system is finite, its coefficients are rational and explicitly encoded, and nonnegativity consists of weak inequalities. Equalities can, if necessary, be replaced by two weak inequalities. Exact rational feasibility handles the terminal equality directly; an approximate numerical comparison is unnecessary.

Since \(N\), \(E\), and \(B\) are polynomially bounded in \(Rm^2+L\), the resulting running time is
\((Rm^2+L)^{O(1)}=(R\tau^2+L)^{O(1)}\).

Finally, unary encoding gives \(R\leq L\), and the explicit support gives \(m\leq L\). Thus this is \(L^{O(1)}\) time in the input bit model, proving membership in \(\mathrm{P}\).

4. Discrete hardness and the parameter \(k\)

The cited [discrete NP-completeness result](https://cgi.cse.unsw.edu.au/~sergeg/papers/AzizGMMSW14.pdf) concerns assigning indivisible players to a balanced knockout tree. The present problem allows arbitrary nonnegative real match masses and defines feasibility through the displayed linear equations. Discrete hardness therefore does not establish hardness of this formulation: a reduction would have to preserve equivalence under these permitted divisions of mass.

For parameterized complexity, the same algorithm works for every tournament relation, independently of its feedback arc set number \(k\). Its running time has the required form \(f(k)L^c\), with \(f(k)=1\) and a fixed constant \(c\). Computing \(k\), or finding a feedback arc set, is unnecessary.

Thus the continuous problem is polynomial-time solvable and fixed-parameter tractable with parameter \(k\). Under polynomial-time many-one reductions, NP-hardness of this problem would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument correctly establishes polynomial-time decidability for the exact continuous formulation and, consequently, fixed-parameter tractability with parameter \(k\). No major or minor mathematical issues were found.

• Total survivor mass.

The two summations are correct. Every distinct-type match variable appears twice in the participation equations and once in the survivor equations, because the tournament has exactly one winner for each distinct pair. Every self-pair variable has participation coefficient \(2\) and survivor coefficient \(1\).

Thus \(S_r=S_{r-1}/2\), and the stated base case \(S_0=1\) gives \(S_r=2^{-r}\) for every relevant round. Nonnegativity then makes \(p_{t^\star}^R=2^{-R}\) equivalent to all other terminal survivor masses being zero. No additional terminal constraint is required.

• Linear formulation and equivalence.

All constraints are linear: the preceding round’s survivor mass is a variable appearing with a constant coefficient, not a product of variables. Substituting \(\mu_t\) for \(p_t^0\) is legitimate.

The variable count is correctly calculated as
\[ N=R\left(\frac{m(m+1)}2+m\right)=\frac{Rm(m+3)}2. \]
There are exactly \(2Rm+1\) listed equality constraints. Their possible linear dependence does not affect feasibility or the complexity bound.

Both directions of the equivalence hold directly because the constructed system reproduces the problem’s defining constraints. No integrality, bracket realization, or additional scheduling condition is required by the stated task.

• Coefficient and encoding bounds.

The stated coefficient set is valid. The right-hand side contains only initial masses, the terminal value, and zeros.

The denominator of \(2^{-R}=1/2^R\) has \(R+1\) binary digits, so its encoding requires \(O(R)\) bits. This correctly accounts for exact representation of the terminal equality.

The dense encoding bound
\[ B=O(EN+L+R)=O(R^2m^3+L+R) \]
is valid. Encoding nonnegativity explicitly also fits within this bound. The construction and its size are polynomial in \(Rm^2+L\).

• Application of polynomial-time linear programming.

The prover states the required theorem precisely: exact feasibility of finite systems of linear equalities and weak inequalities with binary-encoded rational coefficients is decidable in deterministic polynomial time. This is the standard rational linear programming result associated with [Khachiyan’s cited paper](https://www.mathnet.ru/eng/dan42319).

Every hypothesis is verified: the system is finite, explicitly encoded, rational, and uses only equalities and weak inequalities. Replacing equalities by paired inequalities is valid. The theorem applies to feasibility over real variables and does not require an approximate numerical acceptance criterion.

• Input-model running time and edge cases.

The conclusion
\[ (Rm^2+L)^{O(1)}=(R\tau^2+L)^{O(1)} \]
follows from the encoding bound and \(m=\tau\). Unary encoding gives \(R\leq L\), and explicitly listing the support gives \(m\leq L\), so the algorithm runs in \(L^{O(1)}\) time.

The argument also covers a singleton support and zero intermediate survivor masses. Positive initial masses and their normalized sum are used consistently. There is no omitted degenerate case affecting the conclusion.

• Discrete hardness and parameterization.

The prover correctly observes that discrete hardness alone does not establish hardness of this divisible-mass formulation. It does not assert an unsupported reduction.

Since the polynomial-time algorithm applies independently of \(k\), its running time has the fixed-parameter form \(f(k)L^c\) with \(f(k)=1\). Computing \(k\) is unnecessary. The qualification that NP-hardness under polynomial-time many-one reductions would imply \(\mathrm{P}=\mathrm{NP}\) is also correct.

Repair feedback: None required; the write-up resolves the assigned question.

⟨structured verdict parsed — rendered above⟩