Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing MEDExtDomk(V ) is NP-hard, even for k = m 2 .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an even candidate set \(X\) and a rational distribution \(\mu\) over complete rankings of \(X\), compute an extended dominating \(m/2\)-subset graph \(G\) maximizing \(\sum_{(x,y)\in E(G)} d_\mu(x,y)\), where \(d_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t-\sum_{t:y\succ_t x}\mu_t\). The graph is a tournament whose upper set has size \(m/2\) and dominates its complement; the question is to return a maximizing graph, equivalently its selected upper set and internal orientations.
Let \(X\) have even cardinality \(m\geq4\). A society is given by its support: a list of \(\tau\) distinct strict complete rankings \(\succ_t\) of \(X\), each with positive binary rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length. State running times in \(m,\tau,L\).
Define \(d_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t-\sum_{t:y\succ_t x}\mu_t\); zero margins are allowed.
An extended dominating \(m/2\)-subset graph is a tournament \(G\) on \(X\) with a subset \(A\subset X\), \(|A|=m/2\), such that \((x,y)\in E(G)\) for every \(x\in A\), \(y\in X\setminus A\). Orientations within both parts are unrestricted, including cycles.
The computational problem is to return any such graph maximizing \(\sum_{(x,y)\in E(G)}d_\mu(x,y)\); any maximizing graph is acceptable when optima tie.
Is this optimization problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite profiles of strict rankings, maximizing the corresponding sum of integer pairwise margins is NP-hard even when the upper subset has size \(m/2\); with internal edges omitted, the maximizing subsets are those with the highest Borda scores. [Source](https://www.lamsade.dauphine.fr/~lang/papers/JL-JM-AS-WZ-long.pdf)
No separately stated complexity classification for this rational-distribution formulation was located in the search.
The optimization problem is \(\mathrm{NP}\)-hard. In particular, a running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The reduction preserves every maximizing graph, so allowing arbitrary choices among tied optima does not change this conclusion.
Use the finite-profile hardness result given in the question: returning an extended dominating \(m/2\)-subset graph maximizing the sum of integer pairwise margins is \(\mathrm{NP}\)-hard. This is Proposition 8 of [Lang, Monnot, Slinko and Zwicker](https://www.lamsade.dauphine.fr/~lang/papers/JL-JM-AS-WZ-long.pdf), for the same graph class and the same objective before normalization.
Let a source instance consist of an explicitly listed profile \(V=(V_1,\ldots,V_n)\) of strict complete rankings on \(X\), where \(m=|X|\) is even. Define its integer margin by
\(M_V(x,y)=|\{i:x\succ_{V_i}y\}|-|\{i:y\succ_{V_i}x\}|.\)
List the distinct rankings occurring in \(V\) as \(\succ_1,\ldots,\succ_\tau\), and let \(c_t\) be the number of occurrences of \(\succ_t\). Construct the target society by setting
\(\mu_t=c_t/n.\)
This satisfies every input requirement: the rankings are distinct and strict, each mass is positive, and \(\sum_{t=1}^{\tau}\mu_t=1\).
For every pair of distinct alternatives,
\(d_\mu(x,y)=\frac{1}{n}\left(\sum_{t:x\succ_t y}c_t-\sum_{t:y\succ_t x}c_t\right)=\frac{M_V(x,y)}{n}.\)
Consequently, for every feasible tournament \(G\),
\(\sum_{(x,y)\in E(G)}d_\mu(x,y)=\frac{1}{n}\sum_{(x,y)\in E(G)}M_V(x,y).\)
The feasible graphs depend only on \(X\) and the required subset size, so they are identical in the source and target instances. Since \(1/n>0\), the displayed identity preserves all comparisons and all ties between their objective values. Thus any graph returned by a target optimizer also solves the source instance.
Repeated rankings can be grouped by sorting the explicitly listed profile and counting equal rankings. This takes polynomial time in the source input length.
Moreover, \(\tau\leq n\), and each fraction \(c_t/n\) requires \(O(\log(n+1))\) bits. The constructed target input therefore has length
\(L=O\!\left(\tau m\log m+\tau\log(n+1)\right),\)
which is polynomial in the source input length. Reducing fractions, if required by the encoding, also takes polynomial time.
Hence an algorithm polynomial in \(m,\tau,L\) for the target problem would solve the known \(\mathrm{NP}\)-hard source problem in polynomial time. This completes the hardness proof.
The hardness is not caused by difficulty computing rational margins.
Write each input mass as \(\mu_t=a_t/b_t\), with positive integers encoded in binary. Set
\(D=\prod_{t=1}^{\tau}b_t,\qquad w_t=a_t(D/b_t).\)
The integer \(D\) has \(O(L)\) bits. Since the masses sum to one, \(\sum_t w_t=D\). Define
\(N(x,y)=\sum_{t:x\succ_t y}w_t-\sum_{t:y\succ_t x}w_t.\)
Then \(d_\mu(x,y)=N(x,y)/D\), with \(|N(x,y)|\leq D\). Using ordinary integer arithmetic, all margins can be computed within the conservative bound \(O(\tau m^2L^2)\) bit operations.
For completeness, there is an exact exhaustive algorithm with running time
\(O\!\left(\tau m^2L^2+\binom{m}{m/2}m^2L\right).\)
To justify it, fix a subset \(A\) of size \(m/2\). Its cross edges are forced. Every internal edge can be chosen independently because internal cycles are permitted. Thus the best score for this subset is
\(F_\mu(A)=\sum_{\substack{x\in A\\y\notin A}}d_\mu(x,y)+\sum_{\{x,y\}\subseteq A}|d_\mu(x,y)|+\sum_{\{x,y\}\subseteq X\setminus A}|d_\mu(x,y)|.\)
Enumerate all such subsets and evaluate \(D F_\mu(A)\) using the integer margins. Each evaluation takes \(O(m^2L)\) bit operations. For a maximizing subset, orient each internal pair toward its positive margin; choose either direction when its margin is zero. The resulting graph achieves the global optimum.
Let \(b_\mu(x)=\sum_{y\neq x}d_\mu(x,y)\). Antisymmetry gives
\(\sum_{\substack{x\in A\\y\notin A}}d_\mu(x,y)=\sum_{x\in A}b_\mu(x),\)
because the margins of pairs entirely inside \(A\) cancel. This proves the Borda characterization when internal edges are omitted.
For the present problem, however, the two internal absolute-margin sums in \(F_\mu(A)\) also contribute and depend on \(A\). The finite-profile reduction preserves precisely this full objective.
⟨structured verdict parsed — rendered above⟩
The output proves the requested NP-hardness classification. The reduction is valid, preserves every optimum and every tie, and has polynomial encoding size. The additional exact algorithm and Borda calculation are also correct. No major or minor issues were found.
The prover explicitly invokes the finite-profile hardness result supplied in USER_TASK.
The citation matches the claimed problem: Proposition 8 states hardness for extended dominating subsets with upper-set size \(m/2\). The paper defines these graphs as tournaments with all cross edges directed from the upper part to the lower part, without imposing transitivity inside either part. Its median objective is the sum of integer pairwise margins over graph edges. Thus both the feasible class and objective match the source problem used by the prover. See [the cited paper, Sections 3 and 5.2](https://www.lamsade.dauphine.fr/~lang/papers/JL-JM-AS-WZ-long.pdf).
The proof legitimately uses this supplied hardness result; it does not need to reproduce that theorem’s proof.
Grouping equal rankings produces distinct strict complete rankings with positive occurrence counts \(c_t\). For a nonempty finite profile, \(n>0\), so the masses
\[
\mu_t=c_t/n
\]
are positive rational numbers and satisfy
\[
\sum_{t=1}^{\tau}\mu_t=\frac{\sum_{t=1}^{\tau}c_t}{n}=1.
\]
The construction retains the alternatives and therefore preserves the required even cardinality. It introduces no additional restriction on margins; zero margins remain admissible.
Finding: All target input requirements are satisfied.
For each distinct pair, the occurrence counts reproduce exactly the numbers of source voters preferring either direction. Hence
\[
d_\mu(x,y)=M_V(x,y)/n.
\]
Summing over the edges of any feasible graph gives the stated objective identity. The feasible graphs are unchanged, and the scaling factor \(1/n\) is strictly positive.
Therefore objective comparisons, equalities, and the complete set of maximizing graphs are preserved. In particular, an optimizer returning an arbitrary tied optimum still returns a source optimum.
Finding: The reduction correctly handles the task’s tie convention.
An explicitly listed profile can be sorted and grouped in polynomial time. Each count satisfies \(1\leq c_t\leq n\), so its rational mass requires \(O(\log(n+1))\) bits. The bound
\[
L=O\!\left(\tau m\log m+\tau\log(n+1)\right)
\]
is valid for the ordinary explicit ranking encoding.
Since \(\tau\leq n\), the target length and parameters are polynomially bounded by the source input length. Reducing fractions also takes polynomial time.
Consequently, a target algorithm polynomial in \(m,\tau,L\) would solve the supplied NP-hard source optimization problem in polynomial time.
Finding: The hardness conclusion follows.
The product \(D=\prod_t b_t\) has bit length bounded by the sum of denominator bit lengths, hence \(O(L)\). Each \(D/b_t\) is an integer, and
\[
w_t=a_t(D/b_t),\qquad \sum_t w_t=D.
\]
Thus every integer margin satisfies \(|N(x,y)|\leq D\), and dividing by \(D\) recovers the rational margin exactly.
Ordinary multiplication and division on \(O(L)\)-bit integers, followed by accumulation over all rankings and pairs, fit within the conservative bound
\[
O(\tau m^2L^2).
\]
Finding: The arithmetic identities and preprocessing bound are correct.
For a fixed subset \(A\), cross edges are forced. Every internal pair can be oriented independently because cycles are permitted. Its maximum contribution is therefore \(|d_\mu(x,y)|\). This establishes the displayed formula for \(F_\mu(A)\).
Enumerating every subset of size \(m/2\) covers every feasible graph’s possible upper subset. Maximizing the integer score \(DF_\mu(A)\) therefore identifies a globally optimal subset. Choosing a maximizing orientation for each internal pair constructs a globally optimal graph, including when margins vanish.
Each score involves \(O(m^2)\) integer additions. Intermediate scores have \(O(L+\log m)=O(L)\) bits under the explicit input encoding, so the stated \(O(m^2L)\) evaluation bound is valid. The total exhaustive running time follows.
Finding: The algorithm and its stated bound are correct.
Antisymmetry makes the sum of all directed margins within \(A\) vanish. Consequently,
\[
\sum_{\substack{x\in A\\y\notin A}}d_\mu(x,y)
=\sum_{x\in A}b_\mu(x).
\]
For the objective omitting internal edges, maximizing this sum selects the highest scores, with arbitrary choices at the cutoff when scores tie. For the actual objective, the additional internal absolute-margin terms depend on the subset, so the omitted-edge simplification does not establish a polynomial algorithm.
Finding: This explanation is correct and consistent with the reduction.
No repair or additional clarification is needed. The target complexity classification is established by the normalization reduction.
⟨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.