Answer: \(\mathrm{NP}\)-hard; more strongly, \(\Theta_2^p\)-hard and in \(\Sigma_2^p\).
Theorem 7(i) — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-hard to decide (i) whether an alter- native is contained in some minimal upward covering set, (ii) whether an alternative is contained in some minimal downward covering set, and (iii) whether there exists a downward covering set. Conclusions We have investigated solution concepts for dominance graphs that are based on the notion of covering and an- alyzed their computational complexity. It turned out that polynomial-time algorithms exist for computing (iterated) uncovered sets, the minimal bidirectional covering set, and the essential set.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) alternatives, a target \(a\), and \(\tau\) complete-ranking types with positive rational masses \(\mu_t\) summing to \(1\), define \(x \succ_\mu y\) when the total mass ranking \(x\) above \(y\) exceeds \(1/2\). Decide whether \(a\) belongs to some inclusion-minimal upward covering set of the resulting dominance relation; on yes-instances, such a set may be returned. Measure input size in \(m\), \(\tau\), and the masses’ bit length \(L\).
Let \(A\) contain \(m\geq 1\) alternatives, with designated \(a\in A\). A society is given by its support: a list of \(\tau\) distinct strict complete-ranking types, each with positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total bit length of the masses.
Define \(x\succ_\mu y\) iff the mass ranking \(x\) above \(y\) exceeds \(1/2\); an exact half-mass tie gives neither direction.
For \(S\subseteq A\) and \(x,y\in S\), define upward covering by \(xC_u^S y\) iff \(x\succ_\mu y\) and \(\forall z\in S\;(z\succ_\mu x\Rightarrow z\succ_\mu y)\).
A nonempty \(B\subseteq A\) is an upward covering set if no member is upward covered within \(B\), and every \(y\in A\setminus B\) is upward covered by some \(x\in B\) within \(B\cup\{y\}\). It is inclusion-minimal if no nonempty proper subset is an upward covering set for \(A\).
Is deciding whether \(a\) belongs to some inclusion-minimal upward covering set in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it NP-hard?
For explicitly given finite dominance graphs, this membership problem is NP-hard ([Brandt–Fischer](https://maths.qmul.ac.uk/~ffischer/publications/bf_mss08.pdf)); later work establishes \(\Theta_2^p\)-hardness and membership in \(\Sigma_2^p\) ([Baumeister et al.](https://pub.dss.in.tum.de/brandt-research/parallelcovering_journal.pdf)).
No result specifically treating the rational-mass support input above was located.
The problem is \(\mathrm{NP}\)-hard, even when every mass is dyadic. More strongly, it is \(\Theta_2^p\)-hard and belongs to \(\Sigma_2^p\).
The essential point is that every finite asymmetric dominance graph can be realized by a society with polynomially many distinct ranking types and polynomial mass bit length. The realization preserves exact ties and therefore preserves all upward covering sets, including inclusion-minimal ones.
For \(\lvert A\rvert=1\), the answer is trivially affirmative; the hardness concerns unrestricted input sizes.
Lemma. Let \(\lvert A\rvert=m\geq1\), and let \(E\subseteq A\times A\) be irreflexive and asymmetric. There is a polynomial-time construction of a valid rational-mass support satisfying
\(\displaystyle x\succ_\mu y\quad\Longleftrightarrow\quad(x,y)\in E.\)
Its support size satisfies \(\tau\leq2\lvert E\rvert+2\), and its total mass bit length is \(O(m^2\log(m+1))\). All masses are positive dyadic rationals.
Proof. Write \(k=\lvert E\rvert\). Let \(N\) be the least power of two satisfying \(N\geq2k+2\). Consequently,
\(\displaystyle 2k+2\leq N<4k+4.\)
We initially construct a list of weighted rankings that may contain duplicates, and then merge duplicates.
The edge gadget. For each edge \((x,y)\in E\), enumerate the other alternatives as \(w_1,\ldots,w_{m-2}\). Add the following two strict complete rankings, each with mass \(1/N\):
\(\displaystyle R_{xy}: x>y>w_1>\cdots>w_{m-2},\)
\(\displaystyle R'_{xy}: w_{m-2}>\cdots>w_1>x>y.\)
For an ordered pair of distinct alternatives \((u,v)\), define its signed mass margin to be
\(\displaystyle M_\mu(u,v)=\sum_{t:\,u>_t v}\mu_t-\sum_{t:\,v>_t u}\mu_t.\)
The two rankings in the gadget both rank \(x\) above \(y\), so their contribution to \(M_\mu(x,y)\) is \(2/N\). They contribute zero to the margin of every other unordered pair:
Thus this gadget changes only the comparison between \(x\) and \(y\).
Normalization. Fix any strict complete ranking \(R_0\), and let \(R_0^{\mathrm{rev}}\) be its reverse. Add both rankings, each with mass
\(\displaystyle \frac{N-2k}{2N}=\frac{N/2-k}{N}.\)
These masses are positive because \(N\geq2k+2\). Their pairwise contributions cancel. The total mass of all rankings is
\(\displaystyle \frac{2k}{N}+2\frac{N-2k}{2N}=1.\)
Since \(E\) is asymmetric, the resulting margins, for distinct \(u,v\), are exactly
\(\displaystyle M_\mu(u,v)= \begin{cases} 2/N,&(u,v)\in E,\\ -2/N,&(v,u)\in E,\\ 0,&(u,v),(v,u)\notin E. \end{cases}\)
Strict completeness and total mass one imply
\(\displaystyle \sum_{t:\,u>_t v}\mu_t=\frac{1+M_\mu(u,v)}2.\)
Hence an edge gives mass \(1/2+1/N\), its reverse gives mass \(1/2-1/N\), and a missing comparison gives exactly \(1/2\). This proves the required equality of dominance relations.
Distinct support and encoding size. Merge identical rankings by adding their masses. This operation preserves every pairwise mass and produces distinct support types with positive masses. Each resulting mass is \(c/N\) for an integer \(1\leq c\leq N\), so it remains dyadic and requires \(O(\log N)\) bits.
There are at most \(2k+2\) types before merging. Asymmetry gives \(k\leq m(m-1)/2\), and therefore
\(\displaystyle \tau\leq m(m-1)+2,\qquad L=O((k+1)\log N)=O(m^2\log(m+1)).\)
Writing the rankings and merging duplicates take polynomial time: there are \(O(m^2)\) rankings, each of length \(m\). When \(m=1\), the two neutral rankings coincide and merge into the single ranking of mass one. This completes the proof.
The graph problem takes a finite irreflexive asymmetric relation \(E\) and a designated alternative \(a\), and asks whether \(a\) belongs to some inclusion-minimal upward covering set. This is precisely the problem proved \(\mathrm{NP}\)-hard by [Brandt–Fischer, Theorem 7](https://maths.qmul.ac.uk/~ffischer/publications/bf_mss08.pdf). Its stronger \(\Theta_2^p\)-hardness is established by [Baumeister et al., Theorem 12](https://pub.dss.in.tum.de/brandt-research/parallelcovering_journal.pdf).
The hypotheses and definitions match the present task: the relation may be incomplete, upward covering uses predecessors within the specified subset, and minimality means inclusion-minimality rather than minimum cardinality.
Apply the lemma to a graph instance \((A,E,a)\), retaining the same alternatives and designated alternative. For every subset \(S\subseteq A\) and every \(x,y\in S\),
\(\displaystyle xC_{u,E}^{S}y\quad\Longleftrightarrow\quad xC_{u,\mu}^{S}y,\)
because both predicates depend only on comparisons in the identical relations \(E\) and \(\succ_\mu\).
It follows that every nonempty \(B\subseteq A\) satisfies internal and external stability in the graph instance exactly when it satisfies them in the support instance. The entire families of upward covering sets are therefore identical. Their inclusion-minimal members are identical as well, since the alternative set and subset relation are unchanged.
Consequently,
\(\displaystyle a\text{ belongs to some inclusion-minimal upward covering set for }E \quad\Longleftrightarrow\quad a\text{ belongs to one for }\mu.\)
The construction is a polynomial-time many-one reduction, with \(m,\tau,L\) all polynomially bounded in the graph input size. Thus both cited hardness results transfer. In particular, an algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The dominance graph can also be extracted from any valid support input in polynomial time. For every unordered pair, sum exactly the masses ranking one alternative above the other and compare with \(1/2\).
This uses \(O(m^2\tau)\) rational arithmetic operations. For binary-encoded rational numerators and denominators, a common denominator can be their product; its bit length is at most the sum of the denominator bit lengths, hence \(O(L)\). The resulting sums and comparisons therefore have polynomial bit complexity.
For completeness, define \(\mathrm{CS}(B)\) to mean that \(B\) is a nonempty upward covering set for the extracted graph. Checking \(\mathrm{CS}(B)\) takes \(O(m^3)\) Boolean operations: examine all possible covering pairs and all predecessor witnesses in the relevant subsets.
The target condition is exactly
\(\displaystyle \exists B\subseteq A\ \forall D\subseteq A: \bigl[ a\in B\ \land\ \mathrm{CS}(B)\ \land\ \bigl((\varnothing\ne D\subsetneq B)\Rightarrow\neg\mathrm{CS}(D)\bigr) \bigr]. \)
Both subsets have \(m\)-bit encodings, and the bracketed predicate is computable in polynomial time. This is the existential-universal characterization of membership in \(\Sigma_2^p\).
Thus the support representation preserves the graph problem’s established lower and upper bounds. The requested hardness question is settled.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the assigned question. The polynomial realization is correct, preserves exact ties, and transfers the cited graph hardness results to the required support representation. The upper-bound argument is also valid. I found no major or minor mathematical issues requiring repair.
The prover addresses membership in some inclusion-minimal upward covering set, exactly as requested. It does not substitute membership in every such set or in a minimum-cardinality set.
The external results are correctly identified:
Thus the cited theorems have the necessary hypotheses and concern the correct target problem.
For \(k=|E|\), the least power of two satisfying \(N\geq 2k+2\) exists and satisfies
\(2k+2\leq N<4k+4\).
This includes \(k=0\), where \(N=2\). Because \(N\) is a power of two, all masses constructed with denominator \(N\) are dyadic.
Both gadget rankings are strict complete rankings. An edge requires distinct endpoints, so the gadget is used only when \(m\geq 2\).
The margin calculation is correct:
These cases exhaust all unordered pairs. The gadget therefore changes exactly its intended comparison. For \(m=2\), the two rankings coincide, but their contributions still add correctly; duplicates are explicitly permitted before merging.
Each neutral ranking has mass \((N/2-k)/N\). Its numerator is a positive integer because \(N\geq 2k+2\). A ranking and its reverse cancel on every pair of distinct alternatives.
The stated total-mass calculation is correct:
\(2k/N+(N-2k)/N=1\).
Consequently, normalization neither changes the margins nor introduces unwanted comparisons.
Asymmetry prevents simultaneous gadgets for opposing edges. Summing gadget contributions therefore gives precisely the three stated margin values.
For distinct alternatives, strict completeness partitions the total mass between the two possible orders. Hence the identity
\(\sum_{t:u>_t v}\mu_t=(1+M_\mu(u,v))/2\)
is valid.
The resulting pairwise masses correctly yield:
Thus missing graph comparisons remain ties, as required. Diagonal comparisons are absent in both representations by irreflexivity of strict rankings and of \(E\).
Merging identical rankings preserves every pairwise mass. All merged masses remain positive and sum to one.
Each merged mass is \(c/N\) with \(1\leq c\leq N\). This is dyadic and requires \(O(\log N)\) bits under ordinary binary rational encoding.
The bounds
\(\tau\leq 2k+2\) and
\(L=O((k+1)\log N)=O(m^2\log(m+1))\)
follow correctly from asymmetry and the bound on \(N\).
The rankings themselves also have polynomial total encoding length: there are \(O(m^2)\) rankings, each listing \(m\) alternatives. Constructing and merging them is polynomial time. The proof therefore bounds the full output size, not merely the mass encoding.
The explicitly discussed singleton case is correct: its two neutral rankings merge into one ranking of mass one, and the sole alternative belongs to the unique nonempty covering set.
The construction also handles an edgeless graph of any size: the neutral rankings produce only exact ties. No exceptional case invalidates the lemma.
The reduction retains the alternative set and designated alternative and realizes exactly the original dominance relation.
For every subset \(S\), the covering predicate uses only dominance comparisons and quantification over \(S\). Equality of dominance relations therefore implies equality of all restricted covering predicates.
This establishes, in succession:
The polynomial construction is therefore a valid many-one reduction. Both cited lower bounds transfer, including under the stated dyadic restriction.
The conclusion that a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\) is correct. The prover does not claim an unconditional separation from \(\mathrm{P}\).
Exact graph extraction is polynomial time. The \(O(m^2\tau)\) arithmetic-operation count is valid after polynomial-time indexing of positions in the rankings.
The rational bit-complexity argument is sound: the product of input denominators has bit length bounded by their total encoding length. Exact summation and comparison therefore use polynomially bounded integers. This covers general binary-encoded rational masses as well as dyadic ones.
Checking \(\mathrm{CS}(B)\) in \(O(m^3)\) Boolean operations is valid: there are at most quadratically many candidate covering pairs, each requiring at most \(m\) predecessor checks.
The existential-universal formula expresses the target correctly:
Both quantified subsets have polynomial-length encodings, and the predicate is polynomial-time decidable. The claimed membership in \(\Sigma_2^p\) follows.
No repair or additional clarification is necessary. The output establishes NP-hardness, the stronger \(\Theta_2^p\)-hardness lower bound, and membership in \(\Sigma_2^p\), without asserting completeness for either stronger class.
⟨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.