Answer: Polynomial-time solvable
Theorem 1(iii) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet S be a proper tournament solution. Then the following holds: (i) Each of the four basic properties is satisfied by S if it is satisfied by ˚ S. (ii) If RS is pairwise intersecting, each of the following properties is satisfied by S if and only if it is satisfied by ˚ S: (MON ∧SSP), SSP, WSP, IUA. (iii) ˚ S is efficiently computable if and only if S is efficiently computable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set C of m alternatives and a finite-support distribution μ over strict rankings of C, with binary-rational masses summing to 1 and strict majority comparisons for every pair, compute ∘TC of the induced majority tournament in time polynomial in m, τ, and L, where τ is the support size and L is the total bit length of the masses.
Let \(C\) be a nonempty set of \(m\) alternatives. A society is given by its support: a list of \(\tau\) distinct strict rankings of \(C\), each with a positive binary-rational mass, with masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total bit length of the masses.
Define \(a\succ b\) when the mass ranking \(a\) above \(b\) exceeds \(1/2\). Assume every distinct pair has a strict majority comparison, so \(T=(C,\succ)\) is a tournament.
For a nonempty subtournament \(U\), its top cycle \(\mathrm{TC}(U)\) is the smallest nonempty set whose members all dominate every alternative outside it. Write \(D_T(b)=\{a\in C:a\succ b\}\), and let \(T|_A\) denote restriction to \(A\).
A nonempty set \(B\subseteq C\) is \(\mathrm{TC}\)-retentive if \(\mathrm{TC}(T|_{D_T(b)})\subseteq B\) for every \(b\in B\) with \(D_T(b)\ne\varnothing\). Define \(\mathring{\mathrm{TC}}(T)\) as the union of all inclusion-minimal \(\mathrm{TC}\)-retentive sets.
Is computing \(\mathring{\mathrm{TC}}(T)\) from this society possible in time polynomial in \(m,\tau,L\), or is this computation NP-hard?
For explicitly given finite tournaments, a proper tournament solution and its retentiveness operator are polynomial-time computable exactly when each other is; in particular, \(\mathring{\mathrm{TC}}\) is polynomial-time computable (Brandt, Brill, Fischer, and Harrenstein, 2010).
Computing \(\mathring{\mathrm{TC}}(T)\) from the given society is possible in time polynomial in \(m,\tau,L\). The binary encoding of the masses causes no difficulty: the majority tournament can be constructed using exact arithmetic of polynomial bit length.
Below is a direct algorithm and correctness proof.
Write the supplied masses as \(w_i=p_i/q_i\), for \(1\leq i\leq\tau\), with positive integers \(p_i,q_i\) encoded in binary. This includes dyadic rational masses. Define
\( Q=\prod_{i=1}^{\tau}q_i, \qquad W_i=p_i(Q/q_i). \)
These are integers satisfying \(w_i=W_i/Q\) and \(\sum_i W_i=Q\). The bit length of \(Q\) is at most the sum of the bit lengths of the denominators, hence is \(O(L)\). Since each mass is at most one, \(W_i\leq Q\), so each \(W_i\) also has \(O(L)\) bits. Products and exact divisions therefore compute all these integers in polynomial time.
For each ranking, build a table recording every alternative’s position. For distinct alternatives \(a,b\), compute
\( M_{ab}=\sum_{\substack{1\leq i\leq\tau\\ \text{ranking }i\text{ places }a\text{ above }b}}W_i. \)
Then, exactly,
\( a\succ b\quad\Longleftrightarrow\quad 2M_{ab}>Q. \)
Each sum uses at most \(\tau\) additions of integers with \(O(L)\) bits. There are \(\binom m2\) pairs. The strict-majority hypothesis ensures that each pair receives exactly one orientation.
Thus the explicit tournament \(T\), including all sets \(D_T(b)\), is constructed in polynomial time in \(m,\tau,L\). No enumeration of rankings outside the supplied support is required.
Orient tournament edges from the dominating alternative to the dominated alternative.
A strongly connected component is a maximal set of vertices that are mutually reachable by directed paths, allowing paths of length zero. The condensation graph contracts each strongly connected component to one vertex.
The condensation graph of any finite directed graph is acyclic: a directed cycle of distinct components would make those components mutually reachable, contradicting their distinctness.
For a tournament, all edges between two distinct components have the same direction. Otherwise, an edge in each direction, together with paths within the components, would make them mutually reachable. Consequently, its condensation graph is an acyclic tournament.
Every nonempty finite acyclic directed graph has a source, meaning a vertex with no incoming edges: repeatedly following incoming edges, if possible, would otherwise produce a cycle. An acyclic tournament has exactly one source, since an edge between two alleged sources would enter one of them.
Let \(K\) be the corresponding source component of a nonempty tournament \(U\). Every member of \(K\) dominates every vertex outside \(K\), because all edges between components have a uniform direction and none enter \(K\).
We now verify that \(K=\mathrm{TC}(U)\). Let \(S\) be any nonempty set whose members all dominate every vertex outside \(S\).
First, \(S\cap K\ne\varnothing\). Otherwise, choosing \(s\in S\) and \(k\in K\), the source-component property gives \(k\succ s\), whereas the defining property of \(S\) gives \(s\succ k\), a contradiction.
Next, suppose \(k\in K\setminus S\), and choose \(s\in K\cap S\). Strong connectivity gives a directed path within \(K\) from \(k\) to \(s\). Its first edge entering \(S\) runs from outside \(S\) to inside \(S\), contradicting the fact that every member of \(S\) dominates every vertex outside \(S\). Thus \(K\subseteq S\).
Therefore \(K\) is the smallest nonempty dominating set, exactly as required by the definition of \(\mathrm{TC}(U)\).
This also gives a polynomial algorithm. For example, compute all-pairs reachability in \(O(|U|^3)\) Boolean operations, identify components by mutual reachability, and select the source component.
For every \(b\in C\), define
\( F(b)= \begin{cases} \mathrm{TC}(T|_{D_T(b)}),&D_T(b)\ne\varnothing,\\ \varnothing,&D_T(b)=\varnothing. \end{cases} \)
Construct a directed graph \(G\) on \(C\) by placing an edge \(b\to a\) exactly when \(a\in F(b)\).
By the definition in the question, a nonempty set \(B\subseteq C\) is \(\mathrm{TC}\)-retentive exactly when
\( b\in B\quad\Longrightarrow\quad F(b)\subseteq B. \)
Equivalently, no edge of \(G\) leaves \(B\). Such a set contains every vertex reachable from any of its members: this follows by applying edge closure successively along a directed path.
We prove that the inclusion-minimal nonempty sets with this closure property are precisely the sink strongly connected components of \(G\), where a sink component has no outgoing edge to another component.
Every sink component is minimal. A sink component \(H\) has no edge leaving it, so it is closed. If a nonempty closed subset \(B\subseteq H\) contains \(b\), strong connectivity makes every vertex of \(H\) reachable from \(b\). Path closure forces \(H\subseteq B\). Thus \(B=H\).
Every minimal nonempty closed set is a sink component. Let \(B\) be nonempty and closed, and choose \(b\in B\). In the finite acyclic condensation graph of \(G\), the component containing \(b\) can reach a sink component \(H\): follow outgoing edges until reaching a vertex with none. Every vertex of \(H\) is reachable from \(b\), so \(H\subseteq B\). Since \(H\) is itself nonempty and closed, minimality of \(B\) implies \(B=H\).
Consequently,
\( \mathring{\mathrm{TC}}(T) = \bigcup_{\substack{H\text{ a strongly connected component of }G\\ H\text{ has no outgoing edge to another component}}}H. \)
This characterization requires no uniqueness assumption about minimal retentive sets.
The complete algorithm is:
Step 1 has polynomial bit complexity, as established above. Step 2 makes at most \(m\) top-cycle computations on tournaments of at most \(m\) vertices, using \(O(m^4)\) Boolean operations with the reachability algorithm. Steps 3 and 4 are also polynomial; all-pairs reachability for \(G\) uses \(O(m^3)\) Boolean operations.
The algorithm therefore runs in time polynomial in \(m,\tau,L\) and returns exactly the requested set. It also handles \(m=1\): the dependency graph has one sink component, and the output is \(C\).
This agrees with the explicit-tournament tractability result in [Brandt, Brill, Fischer, and Harrenstein (2010)](https://pub.dss.in.tum.de/brandt-research/minretentive.pdf). The additional input-representation issue is resolved by the exact majority construction in Section 1.
⟨structured verdict parsed — rendered above⟩
The prover’s output correctly resolves the task: computing \(\mathring{\mathrm{TC}}(T)\) from the supplied support is polynomial-time solvable in \(m,\tau,L\). The argument is self-contained, and no major or minor mathematical issues were found.
The common-denominator construction is valid. With \(Q=\prod_i q_i\) and \(W_i=p_i(Q/q_i)\), each division is exact, \(w_i=W_i/Q\), and the normalization of the masses implies \(\sum_i W_i=Q\).
The bit-length bounds are correct:
Consequently, the products, exact divisions, additions, and comparisons have polynomial bit complexity.
The equivalence \(a\succ b\) if and only if \(2M_{ab}>Q\) follows directly from the definition of weighted majority. Strict rankings give \(M_{ab}+M_{ba}=Q\), and the strict-majority assumption excludes equality with \(Q/2\). Each pair therefore receives exactly one orientation.
Building position tables and examining the supplied rankings requires polynomial time in \(m,\tau\). The argument correctly uses the support size \(\tau\) without enumerating other rankings.
Assessment: Correct and rigorous.
The condensation argument is sound. A directed cycle among distinct strongly connected components would merge them into one component, so the condensation is acyclic.
For a tournament, edges between two distinct components must have a uniform direction: opposite-direction edges, combined with internal directed paths, would make the components mutually reachable. Hence the condensation is itself a tournament.
The existence and uniqueness of its source are correctly justified. The corresponding component \(K\) dominates every vertex outside it.
The proof that \(K\) is the smallest nonempty dominating set checks both necessary claims:
Thus the claimed characterization agrees exactly with the task’s definition of \(\mathrm{TC}\), including its requirement of a smallest set.
All-pairs reachability, component identification, and source selection give the stated polynomial algorithm.
Assessment: Correct and rigorous.
Defining \(F(b)=\varnothing\) when \(D_T(b)=\varnothing\) correctly incorporates the exception in the retentiveness definition.
With edges \(b\to a\) for \(a\in F(b)\), retentiveness is exactly closure under outgoing edges. Closure under directed reachability follows by successive application along a path.
Both directions of the minimality characterization are valid:
Therefore, inclusion-minimal nonempty retentive sets are precisely the sink components of \(G\), and their union is exactly the requested output. The proof does not assume uniqueness.
Assessment: Correct and rigorous.
At most \(m\) top-cycle computations, each using \(O(m^3)\) Boolean operations, give the stated \(O(m^4)\) bound for that stage. Constructing \(G\) and finding its sink components are also polynomial. Together with the verified arithmetic bounds, this establishes polynomial time in \(m,\tau,L\).
The singleton case is handled correctly. More generally, vertices with empty dominator sets cause no undefined top-cycle computation because the algorithm explicitly assigns them an empty dependency set.
The cited explicit-tournament result is corroborative; the correctness argument does not depend on an unverified application of that result.
Actionable feedback: No repair or additional clarification 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.