Answer: Polynomial-time solvable: \(\mathrm{P}\) for fixed \(m\) and \(K\); also for fixed \(K\) with variable \(m\) and explicit tables.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose that L and |Θ| are constants. Then L- FLIP-AND-CYCLE-COVER is solvable in polynomial-time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed finite set of complete types \(\Theta\), a rational distribution \(\mu\) over those types, directed compatibility \(f\), rational switching costs \(c\), and fixed cycle cap \(L\), choose transfer masses \(y_{\theta\phi}\) and masses \(x_w\) assigned to compatible cycle templates \(w\) of lengths at most \(L\). Transfers must respect the available mass of each source type, and cycle allocations must respect the resulting mass of each type. Maximize the matched fraction \(\sum_w |w|x_w\) minus per-capita switching cost \(\sum_{\theta\ne\phi}c(\theta,\phi)y_{\theta\phi}\).
Fix a nonempty finite universe \(\Theta\) of complete patient–donor types, with \(m=|\Theta|\), and a constant cycle cap \(K\ge 2\); both \(m\) and \(K\) are constants.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\); unlisted types in \(\Theta\) have mass zero but remain available switching destinations.
Input also includes an explicit directed compatibility table \(f:\Theta\times\Theta\to\{0,1\}\), binary rational switching costs \(c(\theta,\phi)\in\mathbb Q\) for distinct types, and a binary rational threshold \(b\). Costs may have either sign; retaining one's type costs zero.
Choose divisible transfer masses \(y_{\theta\phi}\ge0\) for \(\theta\ne\phi\), with \(\sum_{\phi\ne\theta}y_{\theta\phi}\le\mu_\theta\). Each portion switches at most once, directly from its original type; switched mass may remain unmatched.
The resulting mass is \(q_\theta=\mu_\theta-\sum_{\phi\ne\theta}y_{\theta\phi}+\sum_{\phi\ne\theta}y_{\phi\theta}\).
A cycle template is an ordered tuple \(w=(\theta_1,\ldots,\theta_\ell)\), where \(2\le\ell\le K\), \(f(\theta_i,\theta_{i+1})=1\), and \(\theta_{\ell+1}=\theta_1\). Types may repeat; positions represent distinct participants, so diagonal compatibility permits exchanges between distinct participants of the same type, never singleton cycles.
Write \(a_\theta(w)\) for the number of occurrences of \(\theta\) in \(w\). Choose divisible cycle masses \(x_w\ge0\) satisfying \(\sum_w a_\theta(w)x_w\le q_\theta\) for every type.
Decide whether \(\sum_w |w|x_w-\sum_{\theta\ne\phi}c(\theta,\phi)y_{\theta\phi}\ge b\) is achievable. Let \(L\) be the total input bit length; state running times in \(m,\tau,L,K\).
Is this continuous flip-and-cycle-cover decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard, with \(m\) and \(K\) fixed?
The discrete flip-and-cycle-cover problem is polynomial-time solvable when the type-universe size and cycle cap are constants ([source](https://www.cs.cmu.edu/~sandholm/www/bitwise.aaai2017_full.pdf)).
No result settling this exact continuous problem was identified in the literature search.
Theorem. The stated decision problem belongs to \(\mathrm{P}\) when \(m\) and \(K\) are fixed. In fact, it remains polynomial-time solvable for every fixed \(K\) when \(m\) varies and the compatibility and cost tables are explicit.
Let \(S=\{\theta\in\Theta:\mu_\theta>0\}\), so \(|S|=\tau\). Set \(\mu_\theta=0\) for every unlisted type.
Let \(\mathcal W\) contain exactly the ordered tuples permitted in the question. Write \(T=|\mathcal W|\), and define
\(\displaystyle H(m,K)=\sum_{\ell=2}^{K}m^\ell.\)
Enumerate every tuple of each length and check its cyclic compatibility conditions. This requires \(O(KH(m,K))\) table lookups, and
\(\displaystyle T\le H(m,K)\le(K-1)m^K.\)
This enumeration includes repeated types and checks diagonal compatibility when successive positions have the same type. It excludes singleton cycles. We do not truncate lengths at \(m\), because types may repeat.
All types in \(\Theta\) participate in this enumeration, including types outside \(S\).
If \(\theta\notin S\), the original outgoing-transfer constraint and nonnegativity imply
\(\displaystyle 0\le\sum_{\phi\ne\theta}y_{\theta\phi}\le\mu_\theta=0.\)
Thus every transfer originating outside \(S\) is zero. We may omit those variables while retaining every type as a destination.
Introduce variables \(y_{\theta\phi}\ge0\) for \(\theta\in S\), \(\phi\in\Theta\setminus\{\theta\}\), and \(x_w\ge0\) for \(w\in\mathcal W\). Consider the following rational linear feasibility problem.
For every \(\theta\in S\), impose the original-mass constraint
\(\displaystyle \sum_{\phi\ne\theta}y_{\theta\phi}\le\mu_\theta.\)
For every \(\theta\in\Theta\), impose the cycle-capacity constraint
\(\displaystyle \sum_{w\in\mathcal W}a_\theta(w)x_w +\sum_{\phi\ne\theta}y_{\theta\phi} -\sum_{\substack{\phi\in S\\\phi\ne\theta}}y_{\phi\theta} \le\mu_\theta,\)
where an outgoing sum for \(\theta\notin S\) is defined to be zero.
Finally, impose the threshold constraint
\(\displaystyle -\sum_{w\in\mathcal W}|w|x_w +\sum_{\theta\in S}\sum_{\phi\ne\theta}c(\theta,\phi)y_{\theta\phi} \le-b.\)
Every coefficient is rational. The multiplicities and cycle lengths are integers at most \(K\).
Suppose an admissible switching and cycle plan achieves the threshold. Its transfers from unsupported origins are zero, as proved above. For each type, substituting
\(\displaystyle q_\theta=\mu_\theta-\sum_{\phi\ne\theta}y_{\theta\phi} +\sum_{\substack{\phi\in S\\\phi\ne\theta}}y_{\phi\theta}\)
into \(\sum_w a_\theta(w)x_w\le q_\theta\) and rearranging gives precisely the displayed cycle-capacity inequality. Negating the objective threshold gives the final inequality. Hence the linear system is feasible.
Conversely, suppose the linear system is feasible. Extend its transfers by zero for all unsupported origins. The outgoing constraints allow the original mass of each supported type to be divided into the specified direct transfers and its retained remainder. Because outgoing transfers are bounded by \(\mu_\theta\), rather than by \(q_\theta\), received mass supplies no additional switching capacity.
The resulting masses are nonnegative: each is a nonnegative retained remainder plus incoming mass. Rearranging the cycle-capacity inequalities gives exactly \(\sum_w a_\theta(w)x_w\le q_\theta\). Thus the cycle masses satisfy the model’s capacity requirements. The last inequality gives the required objective value.
Therefore the decision problem is exactly equivalent to this rational linear feasibility problem.
The feasible set before adding the threshold inequality is nonempty: choose all transfers and cycle masses to be zero.
It is also bounded. Summing the outgoing constraints gives
\(\displaystyle \sum_{\theta\in S}\sum_{\phi\ne\theta}y_{\theta\phi}\le1.\)
Transfers preserve total mass, since each transfer appears once positively and once negatively in the sum defining \(q\). Consequently,
\(\displaystyle \sum_{\theta\in\Theta}q_\theta=1.\)
Summing cycle capacities and using \(\sum_\theta a_\theta(w)=|w|\) gives
\(\displaystyle \sum_{w\in\mathcal W}|w|x_w\le1.\)
Since every cycle has length at least two, \(\sum_w x_w\le1/2\). All variables are therefore bounded. The feasible set is closed, so it is compact, and the linear objective attains its maximum. Arbitrary signs of the finite rational costs do not change these conclusions.
For the algorithm, we use the standard rational linear-programming theorem: feasibility of a finite system of non-strict linear inequalities with binary rational coefficients is decidable exactly in time polynomial in its total encoding length. This theorem concerns feasibility over the reals and includes equality at the threshold; no numerical tolerance is required. See [Khachiyan, “A polynomial algorithm in linear programming”](https://www.mathnet.ru/eng/dan42319).
Its hypotheses hold here: the system is finite, all coefficients are explicitly encoded rationals, and all constraints are non-strict linear inequalities.
The formulation has
\(\displaystyle d=T+\tau(m-1)\)
nonnegative variables and
\(\displaystyle r=m+\tau+1\)
additional inequalities.
Using a dense encoding with nonnegativity specified as variable bounds, its total encoding length \(B\) satisfies
\(\displaystyle B=O\!\left(L+(r+1)(d+1)\log(K+2)\right).\)
Indeed, the input rational masses occur at most twice, each retained cost occurs once, and the remaining coefficients are zero or integers of magnitude at most \(K\). Thus their rational encodings contribute \(O(L)\), while the dense coefficient layout contributes the second term.
Including input processing, template enumeration, formulation construction, and exact linear feasibility, a running-time bound is
\(\displaystyle O\!\left(L+KH(m,K)+B\right)+\operatorname{poly}(B),\)
where one may substitute
\(\displaystyle B=O\!\left(L+(m+\tau+2)\bigl(H(m,K)+\tau(m-1)+1\bigr)\log(K+2)\right).\)
For fixed \(m\) and \(K\), we have \(\tau\le m\), so \(B=O(L+1)\) and the running time is polynomial in \(L\).
More generally, for fixed \(K\), \(H(m,K)=O(m^K)\), so the bound is polynomial in \(m,\tau,L\). Because the tables are explicit, this also gives polynomial time in the total input length.
Hence the target problem is in \(\mathrm{P}\). Under polynomial-time many-one reductions, an \(\mathrm{NP}\)-hardness result for it would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated problem. The linear formulation is exactly equivalent to the continuous model, and its encoding has polynomial size when \(m\) and \(K\) are fixed. The stronger claim for variable \(m\) and fixed \(K\), with explicit tables, also follows. No major or minor mathematical issues were found.
There are \(m^\ell\) ordered tuples of length \(\ell\), so the number of candidates is \(H(m,K)=\sum_{\ell=2}^{K}m^\ell\). Checking all cyclic compatibility conditions requires at most \(\ell\le K\) table lookups per candidate. Thus the stated \(O(KH(m,K))\) lookup bound is valid.
Since \(m\ge1\) and \(2\le\ell\le K\), every term satisfies \(m^\ell\le m^K\), yielding \(T\le H(m,K)\le(K-1)m^K\).
Enumeration correctly includes repeated types, diagonal compatibility, and unsupported destination types. It excludes singleton cycles and does not incorrectly restrict cycle length to \(m\).
Keeping different ordered representations of a cycle causes no problem: the task itself defines templates as ordered tuples, and every corresponding variable is subject to the same type-capacity accounting.
For an unsupported type, \(\mu_\theta=0\). Nonnegative outgoing transfers with total at most zero must each equal zero. Consequently, deleting these variables preserves precisely the feasible plans.
The proof correctly retains all types as switching destinations. It does not confuse the support size \(\tau\) with the universe size \(m\).
For supported origins, the outgoing constraints are the prescribed bounds on original mass.
Moving the outgoing and incoming terms from the definition of \(q_\theta\) into the cycle-capacity inequality gives exactly the displayed constraint. Both signs are correct: outgoing transfers consume available mass, while incoming transfers increase it.
The threshold inequality also has the correct signs. Negating the required objective inequality produces negative cycle-length coefficients, positive switching-cost coefficients, and right-hand side \(-b\). This remains valid when costs are negative.
Both directions of equivalence are established:
The converse correctly enforces switching at most once from original mass. Incoming mass never enlarges the outgoing-transfer allowance. No constraint inadvertently requires switched mass to be matched.
There is no omitted participant-realization requirement: the task expressly defines admissibility through divisible template masses and these capacity inequalities.
Setting every variable to zero establishes nonemptiness before the threshold constraint is added.
Summing outgoing-transfer constraints gives total transferred mass at most \(1\). Each transfer cancels when resulting masses are summed, so their total remains \(1\).
Summing cycle-capacity inequalities counts each template once per position and therefore yields \(\sum_w |w|x_w\le1\). Since all cycle lengths are at least two, \(\sum_w x_w\le1/2\).
Nonnegativity converts these total bounds into bounds on every variable. The feasible region is closed and bounded in finite-dimensional Euclidean space, hence compact; the linear objective attains its maximum. Finite negative switching costs do not affect this reasoning.
These claims are sound, although attainment is not needed for the direct feasibility algorithm.
The invoked theorem concerns exact feasibility over the reals of finite systems of non-strict inequalities with binary rational coefficients, in time polynomial in their encoding length. The constructed system satisfies all these hypotheses.
The cited [Khachiyan paper](https://www.mathnet.ru/eng/dan42319) establishes polynomial-time feasibility for binary-encoded integer systems; the prover states the standard rational-coefficient version. This is a valid formulation of the theorem.
In particular, an achievable value exactly equal to \(b\) is accepted. No numerical approximation assumption enters the argument.
There are \(T\) cycle variables and \(\tau(m-1)\) transfer variables, giving \(d=T+\tau(m-1)\).
The additional inequalities comprise \(\tau\) outgoing bounds, \(m\) cycle capacities, and one threshold constraint, giving \(r=m+\tau+1\). Nonnegativity is separately specified as variable bounds.
Each supported mass appears in two right-hand sides. Each retained switching cost appears once, and the threshold appears once. Their combined rational encoding length is therefore \(O(L)\).
All remaining numerical entries are zero or integers of magnitude at most \(K\). Consequently, the stated dense-encoding bound \(B=O(L+(r+1)(d+1)\log(K+2))\) is valid. Representing nonnegativity bounds does not invalidate this bound.
Construction, enumeration, and polynomial-time linear feasibility give the claimed overall polynomial bound. For fixed \(m,K\), the dimension and number of constraints are bounded constants, so \(B=O(L+1)\). For fixed \(K\) and variable \(m\), the template count is polynomial in \(m\); explicit input tables ensure that this also yields polynomial time in total input length.
The formulation remains meaningful when no compatible templates exist, when no transfer variables exist, and when \(m=1\). Empty sums impose the appropriate constraints without requiring additional assumptions.
The argument accommodates arbitrary rational thresholds, zero masses outside the support, and costs of either sign. It establishes membership in \(\mathrm P\) for the intended model.
The final statement about \(\mathrm{NP}\)-hardness is appropriately conditional: polynomial-time many-one hardness together with this algorithm would imply \(\mathrm P=\mathrm{NP}\).
No additional clarification or repair is required.
⟨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.