Answer: \(\mathrm P\): every valid instance has optimum \(0\), and therefore every threshold \(B\ge 0\) gives a YES answer.
Theorem 4.10 — class: hardness
Given a bounded-degree tree \(F=(V,E)\), rational house values \(h_1,\ldots,h_q\), and rational masses \(\nu_1,\ldots,\nu_q\) with \(\sum_j\nu_j=1\), consider a continuum of exchangeable copies of \(F\) with pooled house supply \(n\nu_j\) per copy on average, where \(n=|V|\). Choose a distribution \(p\) over configurations \(a:V\to\{1,\ldots,q\}\) satisfying \(\sum_a p_a=1\) and \(\sum_a p_a|\{v:a(v)=j\}|=n\nu_j\), minimizing \(\sum_a p_a\sum_{\{u,v\}\in E}|h_{a(u)}-h_{a(v)}|\).
Let \(F=(V,E)\) be an explicitly given nonempty undirected tree, with \(n:=|V|\) and maximum degree at most a fixed constant \(\Delta\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here the types are house values \(0\le h_1<\cdots<h_q\), with \(h_j\in\mathbb Q\), \(\nu_j\in\mathbb Q_{>0}\), \(\sum_j\nu_j=1\), and \(\tau=q\).
There is a continuum of copies of \(F\), of total copy mass one, sharing a pooled supply of \(n\nu_j\) houses of type \(j\). Each vertex receives one house.
A configuration is any map \(a:V\to\{1,\ldots,q\}\). An allocation is a distribution \((p_a)_a\), with \(p_a\in\mathbb R_{\ge0}\), satisfying \(\sum_a p_a=1\) and \(\sum_a p_a|\{v\in V:a(v)=j\}|=n\nu_j\) for every \(j\); there are no supply constraints within individual copies.
Its cost is \(C(p):=\sum_a p_a\sum_{\{u,v\}\in E}|h_{a(u)}-h_{a(v)}|\). Given a binary rational threshold \(B\ge0\), decide whether some feasible allocation has \(C(p)\le B\).
Use \(m:=n\), and let \(L\) be the total binary input length, including the tree, values, masses, and threshold; state running times in \(m,\tau,L\), with \(\Delta\) fixed.
Is this pooled-supply decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard, on trees of bounded maximum degree?
For the discrete version, assigning a multiset of \(n\) nonnegative house values bijectively to the vertices is NP-hard on bounded-degree trees, and a polynomial-time \(O(\log n)\)-approximation is known ([source](https://arxiv.org/html/2307.12482v2)).
No result settling this exact continuous formulation was identified in the literature search.
The stated pooled-supply problem is in \(\mathrm P\): every valid instance has optimal cost \(\mathbf{0}\), so every allowed threshold \(B\ge 0\) gives a YES answer.
This holds even when \(m\ge 2\) and \(\tau\ge 2\). It follows from the explicit permission to pool supply across copies, without supply constraints within individual copies.
For each \(j\in\{1,\ldots,\tau\}\), define the constant configuration
\[
a^{(j)}(v)=j\qquad\text{for every }v\in V.
\]
Assign probabilities
\[
p_{a^{(j)}}=\nu_j,
\qquad
p_a=0\quad\text{for every other configuration }a.
\]
These are distinct configurations because \(V\ne\varnothing\). The probabilities are nonnegative and sum to one by the hypotheses on the masses.
For each type \(k\), its expected number of assigned houses is
\[
\sum_a p_a\,|\{v\in V:a(v)=k\}|
=\sum_{j=1}^{\tau}\nu_j\,m\,\mathbf 1_{\{j=k\}}
=m\nu_k.
\]
Thus every pooled-supply constraint holds exactly.
In each configuration receiving positive probability, the endpoints of every edge have identical house values. Consequently,
\[
C(p)
=\sum_{j=1}^{\tau}\nu_j
\sum_{\{u,v\}\in E}|h_j-h_j|
=0.
\]
Every allocation has nonnegative cost, since each summand in its cost is nonnegative. Therefore the minimum is exactly zero.
In fact, the allocation above is the unique optimal distribution for the given tree.
To prove this, suppose \(C(p)=0\). The configuration costs and probabilities are nonnegative, so every configuration \(a\) with \(p_a>0\) must have zero cost. Each of its edge costs must therefore vanish:
\[
h_{a(u)}=h_{a(v)}
\qquad\text{for every }\{u,v\}\in E.
\]
Because the values are strictly increasing, this implies \(a(u)=a(v)\). Connectivity then implies that \(a\) is constant on \(V\). For the single-vertex tree, every configuration is already constant.
Hence an optimal distribution is supported only on the configurations \(a^{(j)}\). Its supply constraint for type \(j\) becomes
\[
m\,p_{a^{(j)}}=m\nu_j.
\]
Since \(m>0\), necessarily \(p_{a^{(j)}}=\nu_j\), proving uniqueness.
On inputs satisfying the stated promises, the decision algorithm simply returns YES. Including reading the input, its running time is \(O(m+\tau+L)=O(L)\). An explicit optimal witness listing all \(\tau\) configurations can be produced in
\[
O\!\left(L+m\tau\left\lceil\log_2(\tau+1)\right\rceil\right)
\]
bit operations, using the input vertex order and copying the rational masses without arithmetic. The degree bound is unnecessary.
The cited discrete problem requires a bijection from vertices to a fixed multiset of houses. [The paper’s model](https://arxiv.org/html/2307.12482v2) imposes that requirement within the single graph. Here, a fraction \(\nu_j\) of copies may receive exclusively type \(j\), consuming exactly \(m\nu_j\) houses from the pooled supply. Thus the discrete hardness does not transfer. A nonzero optimum would require an additional constraint absent from the stated formulation.
⟨structured verdict parsed — rendered above⟩
The output fully resolves the stated problem. The zero-cost allocation is feasible under the explicit pooled-supply constraints, and nonnegativity proves its optimality. The uniqueness claim and polynomial running-time bounds also hold. No major or minor mathematical issues were found.
There is at least one type because the positive masses sum to \(1\). Each constant map \(a^{(j)}:V\to\{1,\ldots,\tau\}\) is an allowed configuration. Since \(V\ne\varnothing\), different type indices give distinct configurations, so assigning \(p_{a^{(j)}}=\nu_j\) is unambiguous. The remaining probabilities are zero. Nonnegativity and normalization follow directly from \(\nu_j>0\) and \(\sum_j\nu_j=1\).
In configuration \(a^{(j)}\), the number of vertices assigned type \(k\) is \(m\) when \(j=k\), and zero otherwise. Thus the displayed expectation equals \(m\nu_k\), exactly as required, for every supported type \(k\). This computation uses only pooled supply; the task explicitly imposes no supply constraints within individual copies. No integrality condition on \(m\nu_k\) is required.
Every edge in each positive-probability configuration has identical values at its endpoints, so every edge contribution is zero. Therefore the proposed allocation has cost \(0\). Every feasible allocation has nonnegative cost because probabilities and absolute differences are nonnegative. These two statements establish an attained minimum of exactly \(0\), rather than merely an infimum.
The configuration set is finite. Consequently, a zero sum of nonnegative weighted configuration costs implies that every configuration with positive probability has zero cost. Within such a configuration, each nonnegative edge contribution must vanish. Strictly increasing house values imply equality of type indices across each edge, and connectivity implies that the configuration is constant. For a single vertex, every configuration is constant without using an edge. The type-\(j\) supply equation then reduces to \(m p_{a^{(j)}}=m\nu_j\); division by \(m>0\) proves the claimed uniqueness.
Since the task promises \(B\ge0\), the optimal allocation meets every allowed threshold. Returning YES is therefore correct on every valid input. Reading the input takes \(O(L)\) bit operations. Explicit encoding gives \(m,\tau=O(L)\), so the stated \(O(m+\tau+L)=O(L)\) bound is justified. The witness contains \(m\tau\) type indices, each representable using \(\lceil\log_2(\tau+1)\rceil\) bits, plus the copied rational masses. This supports the stated witness-generation bound
\(O\!\left(L+m\tau\lceil\log_2(\tau+1)\rceil\right)\).
The decision claim is expressly restricted to promised inputs, so input validation is not an omitted requirement.
The cited paper defines the discrete allocation as a bijection between vertices and a prescribed multiset of houses, confirming the distinction asserted by the prover. [Tight Approximations for Graphical House Allocation](https://arxiv.org/html/2307.12482v2). The proposed distribution is permitted by the continuous task’s explicit constraints. Its validity holds for all supported positive masses, including instances with multiple vertices and multiple types; it does not depend on a special degenerate case. The degree bound is indeed unnecessary for the zero-cost construction.
None is required. All substantive claims are justified as written, and no external theorem is needed for the continuous conclusion.
⟨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.