Answer: \(\mathrm{NP}\)-complete
Corollary 5.16 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWe can find an optimal house allocation for an instance on an undirected 𝑛-agent graph 𝐺 that is the disjoint union of cliques in time 𝑂(𝑛𝑟+2), where 𝑟 is the number of cliques. There seems to be a separation between unions of differently- sized cliques and unions of stars, cycles, and paths. We suspect the problem may be W[1]-hard for unions of arbitrary cliques.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite catalogue \(S\) of clique sizes, rational component masses \(\rho_s\), and rational masses \(\nu_j\) of house values \(v_1<\cdots<v_q\) satisfying \(\sum_{s\in S}s\rho_s=\sum_{j=1}^q\nu_j\), choose masses \(\lambda_{s,b}\) over nondecreasing bundles \(b\in\{v_1,\ldots,v_q\}^s\) such that \(\sum_b\lambda_{s,b}=\rho_s\) and \(\sum_{s,b}\mathrm{mult}_{v_j}(b)\lambda_{s,b}=\nu_j\); minimize \(\sum_{s,b}\lambda_{s,b}\sum_{1\le p<\ell\le s}(b_\ell-b_p)\), or decide whether the optimum is at most a given rational threshold.
Given an undirected graph \(G=(V,E)\) with \(|V|=n\), distinct rational values \(a_1<\cdots<a_n\), and rational \(B\), let \(S_n\) be the bijections \(\pi:V\to[n]\). For \(\pi\in S_n\), define \(c(\pi)=\sum_{\{u,v\}\in E}|a_{\pi(u)}-a_{\pi(v)}|\).
A feasible atomless allocation is a distribution \(\lambda\in\Delta(S_n)\), where \(\lambda_\pi\ge0\) and \(\sum_{\pi\in S_n}\lambda_\pi=1\); its aggregate envy is \(\sum_{\pi\in S_n}\lambda_\pi c(\pi)\). Decide whether some feasible \(\lambda\) has aggregate envy at most \(B\).
Target: Is this continuous graphical-house-allocation decision problem NP-hard, or solvable in polynomial time?
Nearest known results: The corresponding discrete problem, which asks whether a single bijection \(\pi\) satisfies \(c(\pi)\le B\), is NP-hard even with identical valuations, by a linear-time reduction from Minimum Bisection. No result for the atomless distributional formulation is assumed here.
The continuous distributional problem is \(\mathrm{NP}\)-complete. In particular, allowing distributions over bijections does not improve the optimum: a linear objective over the probability simplex attains its minimum at a single bijection.
Let
\[ m(G,a)=\min_{\pi\in S_n} c(\pi). \]
This minimum exists because \(S_n\) is finite and nonempty.
For every \(\lambda\in\Delta(S_n)\), the inequality \(c(\pi)\geq m(G,a)\) holds for every \(\pi\in S_n\). Hence
\[ \sum_{\pi\in S_n}\lambda_\pi c(\pi) \geq \sum_{\pi\in S_n}\lambda_\pi m(G,a) = m(G,a)\sum_{\pi\in S_n}\lambda_\pi = m(G,a). \]
Conversely, choose a minimizer \(\pi^\star\in S_n\), so that \(c(\pi^\star)=m(G,a)\). Define the Dirac distribution
\[ \lambda^{\star}_{\pi^\star}=1, \qquad \lambda^{\star}_{\pi}=0 \quad\text{for every }\pi\neq\pi^\star. \]
This distribution belongs to \(\Delta(S_n)\), and its aggregate envy is
\[ \sum_{\pi\in S_n}\lambda^\star_\pi c(\pi) = c(\pi^\star) = m(G,a). \]
Therefore
\[ \min_{\lambda\in\Delta(S_n)} \sum_{\pi\in S_n}\lambda_\pi c(\pi) = \min_{\pi\in S_n}c(\pi). \]
The preceding identity gives
\[ \exists\,\lambda\in\Delta(S_n): \sum_{\pi\in S_n}\lambda_\pi c(\pi)\leq B \quad\Longleftrightarrow\quad \exists\,\pi\in S_n:c(\pi)\leq B. \]
Indeed, the forward implication follows because the minimum single-bijection cost is at most every distributional average. The reverse implication follows by placing probability \(1\) on the qualifying bijection.
Thus the continuous problem and the corresponding discrete problem define exactly the same language of yes-instances.
By the stated known result, deciding whether there is a bijection \(\pi\) with \(c(\pi)\leq B\) is \(\mathrm{NP}\)-hard. The identity transformation, which leaves \(G\), \(a_1,\ldots,a_n\), and \(B\) unchanged, is therefore a polynomial-time many-one reduction from the discrete problem to the continuous problem. Hence the continuous problem is \(\mathrm{NP}\)-hard.
It also belongs to \(\mathrm{NP}\). A certificate is a bijection \(\pi:V\to[n]\). One can verify bijectivity and compute
\[ c(\pi)=\sum_{\{u,v\}\in E} \left|a_{\pi(u)}-a_{\pi(v)}\right| \]
using exact rational arithmetic in time polynomial in the binary input length. The sum contains at most \(\binom{n}{2}\) rational terms, and the bit lengths of the intermediate numerators and denominators remain polynomially bounded. The verifier then compares \(c(\pi)\) with \(B\).
Consequently, the continuous graphical-house-allocation decision problem is \(\mathrm{NP}\)-complete. This conclusion uses the stated definition \(\Delta(S_n)\), which permits Dirac distributions.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes that the distributional problem has exactly the same optimum and yes-instances as the discrete single-bijection problem. Given the NP-hardness premise supplied in USER_TASK, the conclusion that the continuous problem is NP-complete is rigorous.
The definition
\[
m(G,a)=\min_{\pi\in S_n}c(\pi)
\]
is valid because \(S_n\) is finite and nonempty.
Since \(c(\pi)\geq m(G,a)\) for every \(\pi\), multiplying by \(\lambda_\pi\geq0\) and summing is valid. The normalization \(\sum_\pi\lambda_\pi=1\) then gives
\[
\sum_\pi\lambda_\pi c(\pi)\geq m(G,a).
\]
All required hypotheses are explicitly stated.
A minimizing bijection \(\pi^\star\) exists. The distribution assigning probability \(1\) to \(\pi^\star\) is permitted by the stated definition of \(\Delta(S_n)\), and its aggregate envy is exactly \(m(G,a)\). Thus the equality of the two optima follows.
The equivalence
\[
\exists\lambda:\sum_\pi\lambda_\pi c(\pi)\leq B
\quad\Longleftrightarrow\quad
\exists\pi:c(\pi)\leq B
\]
follows directly from the established equality of minima. There is no missing quantifier or boundary issue, including when \(B=m(G,a)\).
The prover is entitled to use the discrete problem’s NP-hardness because it is explicitly supplied as a known result in USER_TASK. Since the continuous and discrete instances use the same data and have identical yes/no answers, the identity mapping is a valid polynomial-time many-one reduction.
A bijection has polynomial encoding length. Bijectivity can be checked in polynomial time, and \(c(\pi)\) contains at most \(\binom n2\) rational differences. Exact rational addition and comparison have polynomial bit complexity: even unreduced products of input denominators have bit length bounded by the sum of the denominator bit lengths across polynomially many terms. The proposed certificate therefore gives a valid polynomial-time verifier.
Combining NP-hardness with membership in NP establishes NP-completeness. The exponentially large formal simplex does not obstruct this conclusion because feasibility below \(B\) always has a Dirac witness.
No mathematical errors, unjustified steps, or missing cases were found.
⟨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.