Answer: \(\mathrm{NP}\)-complete under polynomial-time many-one reductions; polynomial-time solvable if and only if \(\mathrm{P}=\mathrm{NP}\).
Theorem 2.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a preference profile $\mathcal{P}$, it is NP-hard to find a graph compatible with $\mathcal{P}$ with a minimum number of edges.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed candidate set \(C\) and a finite-support distribution \(\mu\) over complete rankings of \(C\), find a connected graph \(G=(C,E)\) minimizing \(|E|\), subject to every ranking \(t\) with \(\mu_t>0\) having each of its prefixes induce a connected subgraph of \(G\).
Let \(C\) be an input candidate set with \(m\geq 1\) candidates; \(m\) is not fixed as a constant. Types are strict complete rankings of \(C\).
A society is given by its support: a list of \(\tau\) distinct types with positive binary-rational masses \(\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.
A feasible solution is a connected simple undirected graph \(G=(C,E)\) such that, for every supported ranking \(t=(\pi_t(1),\ldots,\pi_t(m))\) and every \(1\leq k\leq m\), the subgraph induced by \(\{\pi_t(1),\ldots,\pi_t(k)\}\) is connected. Minimize \(|E|\).
For the decision version, the input additionally contains a binary-encoded integer \(B\geq 0\), and asks whether a feasible graph with \(|E|\leq B\) exists.
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\), and \(B\).
For finite lists of voters with strict complete rankings, minimizing the number of edges of a compatible graph is \(\mathrm{NP}\)-hard.
For that discrete formulation, recognizing compatibility with a tree, or with a connected graph having at most \(m\) edges, is polynomial-time solvable.
The decision problem is \(\mathrm{NP}\)-complete under polynomial-time many-one reductions. Consequently, it is polynomial-time solvable if and only if \(\mathrm{P}=\mathrm{NP}\).
The key point is that feasibility depends only on the supported rankings. Neither their positive masses nor the multiplicities of identical voters affect the constraints.
For a ranking \(t\), write \(P_{t,k}=\{\pi_t(1),\ldots,\pi_t(k)\}\).
Lemma. All prefixes of \(t\) induce connected subgraphs precisely when, for every \(k\in\{2,\ldots,m\}\), there is some \(j<k\) such that \(\{\pi_t(j),\pi_t(k)\}\in E\).
Proof. If the induced subgraph on \(P_{t,k}\) is connected, its vertex \(\pi_t(k)\) must have a neighbor among the other vertices, which constitute \(P_{t,k-1}\).
Conversely, the first prefix is a singleton and therefore connected. Inductively, if the preceding prefix is connected, adding a vertex with a neighbor in that prefix preserves connectivity. This proves the assertion for every prefix. \(\square\)
Since the positive masses sum to one, the support is nonempty. Thus these conditions also ensure connectivity of the whole graph by taking \(k=m\).
A certificate is an adjacency matrix with \(\binom m2\) independent bits. Check symmetry, absence of loops, the edge budget, and the lemma’s conditions for every supported ranking.
Let \(\ell_B=\lceil\log_2(B+2)\rceil\). On a word RAM, verification takes
\[ O\!\left(L+\ell_B+(\tau+1)m^2\right) \]
operations, with polynomial bit complexity as well. If \(L\) already includes the budget encoding, the separate \(\ell_B\) term is redundant. Mass arithmetic is unnecessary for verification on the stipulated valid inputs. Therefore the decision problem belongs to \(\mathrm{NP}\).
We use the following precise form of the discrete hardness result:
Given an explicitly listed, nonempty finite profile of strict complete rankings and an integer budget, deciding whether there is a connected compatible graph within that edge budget is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions.
The hypothesis uses exactly the prefix-connectivity definition in this question. The set-cover reduction in the proof of Theorem 2.1 of [Escoffier, Spanjaard, and Tydrichová](https://arxiv.org/pdf/2004.13602) establishes this decision formulation: with \(s\) set candidates and one additional candidate, the budget is \(\binom s2+k\), and compatibility within that budget is equivalent to a set cover of size at most \(k\).
We next transfer this theorem to the required support representation.
Take a discrete instance with \(n\geq1\) explicitly listed voters, candidate set \(C\), and budget \(B\). Delete duplicate rankings, obtaining distinct rankings \(t_1,\ldots,t_\tau\), where \(\tau\leq n\).
A graph is compatible with the original profile if and only if it is compatible with these distinct rankings: repeated occurrences impose identical constraints.
We must assign positive masses with polynomial encoding length. The following construction works even if “binary-rational” requires a finite binary expansion.
Set \(s=\lceil\log_2\tau\rceil\), and define
\[ \mu_{t_i}=2^{-s}\quad(1\leq i<\tau), \qquad \mu_{t_\tau}=\frac{2^s-\tau+1}{2^s}. \]
Every mass is positive because \(2^s\geq\tau\). Their sum is
\[ (\tau-1)2^{-s}+(2^s-\tau+1)2^{-s}=1. \]
For \(\tau=1\), this gives the single mass \(1\). Each mass requires \(O(\log(\tau+1))\) bits.
Keep the candidate set and budget unchanged. For every graph \(G\),
\[ G\text{ is feasible for the discrete instance} \quad\Longleftrightarrow\quad G\text{ is feasible for the constructed society}. \]
The edge count is unchanged too, so this equivalence preserves the answer to the decision problem.
With candidates labeled by integers in \(\{1,\ldots,m\}\), sorting the \(n\) rankings lexicographically and deduplicating them takes \(O(nm\log(n+1))\) word operations. Writing the masses takes \(O(\tau\log(\tau+1))\) bit operations. Apart from the candidate labels, the output length is
\[ O\!\left(\tau m\log(m+1)+\tau\log(\tau+1)+\ell_B\right). \]
Both construction time and output length are polynomial in the discrete input length. This is therefore a polynomial-time many-one reduction. Together with membership in \(\mathrm{NP}\), it proves \(\mathrm{NP}\)-completeness.
Write \(M=\binom m2\). Every connected graph has at least \(m-1\) edges, and the complete graph is always feasible. Hence:
For the last two cases, apply the polynomial recognition algorithms stipulated in the question to a finite profile containing one voter per supported type. If their running times are \(p_{\mathrm{tree}}(m,n)\) and \(p_{\mathrm{cycle}}(m,n)\), respectively, the support-input running times are
\[ O\!\left(L+\ell_B+p_{\mathrm{tree}}(m,\tau)\right) \quad\text{and}\quad O\!\left(L+\ell_B+p_{\mathrm{cycle}}(m,\tau)\right), \]
where both \(p_{\mathrm{tree}}\) and \(p_{\mathrm{cycle}}\) are polynomials. These algorithms require no expansion of the masses into voters.
For arbitrary budgets, an explicit exhaustive algorithm enumerates edge subsets of size at most \(b=\min\{B,M\}\) and applies the verifier. Its word-RAM running time is bounded by
\[ O\!\left( L+\ell_B+ (\tau+1)m^2\sum_{j=0}^{b}\binom Mj \right), \]
and consequently by \(O(L+\ell_B+(\tau+1)m^2 2^M)\).
Thus the polynomial tree and one-cycle cases coexist with hardness for unrestricted budgets. Binary-encoded masses do not alter this classification.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned decision problem. Its support reduction is correct, its certificate verification is polynomial, and the cited hardness result applies to the required compatibility definition. I found no major or minor mathematical issues.
The observation that masses and voter multiplicities do not affect feasibility is correct.
The constraints quantify over every supported ranking individually. They contain no mass-dependent expressions. Repeating a ranking repeats the same constraints, so deleting duplicate rankings preserves the entire collection of feasible graphs, including their edge counts.
Positive masses summing to \(1\) imply \(\tau\geq 1\). The prover correctly uses this fact when deriving whole-graph connectivity from the final prefix.
Both directions of the lemma are valid.
For any supported ranking, \(P_{t,m}=C\), so the conditions also establish connectivity of \(G\). When \(m=1\), the condition indexed by \(k\geq 2\) is vacuous, and the singleton graph is connected.
The proposed certificate has polynomial length. Checking its graph representation, counting edges, comparing the count with \(B\), and inspecting earlier-ranked neighbors all take polynomial time.
For one ranking, the number of potential adjacency checks is at most
\[
\sum_{k=2}^{m}(k-1)=\binom m2.
\]
Thus the stated word-RAM bound
\[
O\!\left(L+\ell_B+(\tau+1)m^2\right)
\]
is valid under the usual word-RAM convention permitting candidate indices and input addresses in a word. Processing the binary budget is covered by \(\ell_B\); the claim of polynomial bit complexity also holds.
Ignoring mass arithmetic is justified because the task stipulates valid society inputs. Consequently, membership in NP is established.
The external reference matches the problem being reduced.
Definition 2.1 requires a connected undirected graph and connectivity of every ranking prefix. Theorem 2.1 concerns minimizing its edge count. Its proof constructs set candidates and one additional candidate, forces all edges among the set candidates, and relates the remaining edge count to set-cover size. This supports the budget decision hardness invoked by the prover. [Escoffier, Spanjaard, and Tydrichová, Definition 2.1 and Theorem 2.1](https://arxiv.org/pdf/2004.13602)
The prover therefore does more than infer decision hardness from an unspecified optimization-hardness statement: it identifies the threshold reduction supplying polynomial-time many-one hardness.
The discrete source has explicitly listed strict complete rankings and a variable candidate count, as required. There is no mismatch between its compatibility constraints and those in USER_TASK.
Every part of this reduction checks out.
Deduplication. Starting from a nonempty profile gives \(1\leq\tau\leq n\). Deleting identical rankings preserves feasibility in both directions.
Mass positivity. With \(s=\lceil\log_2\tau\rceil\), one has \(2^s\geq\tau\). Hence \(2^{-s}>0\), and the final numerator satisfies \(2^s-\tau+1\geq 1\).
Normalization. The displayed sum is correct:
\[
(\tau-1)2^{-s}+(2^s-\tau+1)2^{-s}=1.
\]
Boundary case. For \(\tau=1\), \(s=0\), and the unique mass is \(1\).
Encoding. Each mass is dyadic and therefore has a finite binary expansion. The numerator and denominator have \(O(\log(\tau+1))\) bits. The construction works under either of the relevant readings of “binary-rational.”
Answer preservation. The candidate set and budget remain unchanged, and the feasible graphs remain exactly the same. Therefore the decision answers agree.
Polynomial size and time. Lexicographic comparison of two rankings takes \(O(m)\) word operations, so the stated sorting bound is valid. The mass-writing bound and output-length bound are also valid. Because the voters are explicitly listed, these bounds are polynomial in the source input length.
This establishes a polynomial-time many-one reduction. Together with membership in NP, it proves NP-completeness.
The boundary cases are correct:
The last characterization concerns the entire connected graph, so it correctly includes trees as well as graphs with one cycle.
The supplied recognition results can be applied to one voter per supported type. The stated bounds using polynomial functions \(p_{\mathrm{tree}}(m,\tau)\) and \(p_{\mathrm{cycle}}(m,\tau)\) accurately express this transfer without requiring any expansion of masses.
For arbitrary budgets, there are exactly
\[
\sum_{j=0}^{b}\binom Mj,\qquad b=\min\{B,M\},
\]
edge subsets to inspect. Applying the verifier to each gives the stated exhaustive-search upper bound. Its simplification follows from
\[
\sum_{j=0}^{b}\binom Mj\leq 2^M.
\]
These are exponential general-purpose bounds, consistent with the hardness classification.
The claimed classification is fully established: the support-encoded decision problem is NP-complete under polynomial-time many-one reductions. The conclusion that it is polynomial-time solvable exactly when P equals NP follows.
No additional mathematical clarification or repair is needed. The polynomial special-budget cases do not conflict with hardness for unrestricted budgets.
⟨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.