Answer: The existential threshold problem is $\mathrm{NP}$-hard under polynomial-time many-one reductions, already for $\tau=3$ and edgewise constant densities. The optimum $W^*$ is attained, has the exact congestion-price characterization proved above, and $W^*/\kappa$ admits certified finite rational approximation with the stated running-time bounds.
Theorem 3.1 — class: algorithmic
Given a finite connected graph \(G\), finite valuation-type set \(T\), type distribution \(\mu\), and per-capita capacity \(\kappa\), assign each type-conditioned unit of population mass a connected bundle \(B\subseteq G\) so that \(\ell(x)=\sum_t\mu_t\Pr[B\ni x\mid t]\leq\kappa\) almost everywhere, maximizing \(W=\min_{t:\mu_t>0}\operatorname{ess\,inf}_{B\sim t}v_t(B)\); determine whether \(W\geq w\) and characterize or compute the optimum \(W/\kappa\).
Let \(G\) be a finite connected undirected multigraph without loops, with \(m\geq1\) edges, each represented by \([0,1]\); let \(\lambda\) be edgewise Lebesgue measure. A bundle is a nonempty connected finite union of closed edge intervals; vertices and endpoints may be shared.
A society is given by its support: \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts listed types, not possible types. Type \(t\) has a nonnegative piecewise-constant density \(f_t\), with binary-rational breakpoints and heights, defining \(v_t(B)=\int_B f_t\,d\lambda\) and satisfying \(v_t(G)=1\).
The inputs also include binary-rational capacity \(\kappa>0\) and threshold \(w\in[0,1]\). Let \(K\) count all listed density segments and \(L\) be the total input bit length; state running times in \(m,\tau,K,L\).
An allocation assigns each type a Borel probability distribution \(P_t\) over bundles, using the Borel structure induced by their finite endpoint descriptions. Feasibility means \(\ell(x)=\sum_t\mu_tP_t\{B:x\in B\}\leq\kappa\) for \(\lambda\)-almost every \(x\); unused capacity is allowed.
Define \(W(P)=\min_t\operatorname{ess\,inf}_{B\sim P_t}v_t(B)\) and \(W^*=\sup_{P\text{ feasible}}W(P)\).
Is deciding whether a feasible allocation satisfies \(W(P)\geq w\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? How can the optimal normalized welfare \(W^*/\kappa\) be characterized or computed?
For finitely many agents, a constructive connected allocation guarantees welfare \(1/(2n-1)\), tightly even for identical valuations on a star ([finite-agent guarantee](https://epubs.siam.org/doi/full/10.1137/22M1500502)).
Exact connected egalitarian optimization for finitely many agents is already \(\mathrm{NP}\)-hard on an interval ([optimization hardness](https://arxiv.org/abs/1205.3982)). No result settling this distributional mass-capacity problem was located.
I interpret the decision problem as asking whether there exists a feasible allocation $P$ satisfying $W(P)\ge w$. Checking an arbitrary supplied Borel distribution would require an additional representation convention.
Under this interpretation, the decision problem is $\mathrm{NP}$-hard under polynomial-time many-one reductions, already with exactly three listed types and densities constant on each edge. The reduction below directly establishes this; it does not rely on the fractional Steiner-tree packing oracle reduction in the notes.
The optimal welfare is attained. It admits an exact congestion-price characterization, and its normalized value can be approximated to certified additive accuracy by finite rational allocations. The approximation algorithm has running time
$$ 2^{O(K+m+m\tau/(\kappa\varepsilon))} \operatorname{poly}(m,\tau,K,L,E) $$
when $0<\kappa<1$ and $\varepsilon\in(0,1]$ has bit length $E$.
Equip $G$ with its shortest-path metric. Write $\mathcal B$ for the space of bundles.
Lemma. Every bundle intersects each edge in at most two closed interval components. If a bundle contains a graph vertex, its intersection with an edge consists of a possibly empty prefix and a possibly empty suffix.
Proof. A connected set containing no graph vertex lies in one component of $G$ with its vertices removed. Such a component is an edge interior, where a connected compact set is an interval.
Now suppose that $B$ contains a graph vertex. Fix an interior point $x\in B$ on an edge. If there were omitted points on both sides of $x$, the portion of $B$ between those omitted points would be a nonempty subset both open and closed relative to $B$, separated from every graph vertex. This contradicts connectedness. Thus either the entire edge segment from $x$ to its first endpoint belongs to $B$, or the entire segment to its second endpoint belongs to $B$. Closedness gives the asserted prefix-suffix description. $\square$
This argument applies to every nonempty compact connected subset of $G$, so every such subset is a bundle. Consequently, $\mathcal B$ is compact in the Hausdorff metric: the hyperspace of nonempty compact subsets of a compact metric space is compact, and connectedness is preserved under Hausdorff limits. For the latter assertion, a disconnected limit would have two nonempty compact parts with positive separation; sufficiently close approximating sets would lie in two disjoint neighborhoods and meet both, contradicting their connectedness.
A bundle is path connected. Indeed, it is a finite union of closed intervals; connectedness forces the intersection graph of those intervals, after identifying shared graph vertices, to be connected.
We will also use the following consequence:
If a bundle contains specified graph vertices, its fully included edges contain a connected subgraph spanning those vertices.
To see this, subdivide at the bundle’s interval endpoints. The bundle becomes a connected finite graph. A path between original graph vertices can pass from one original vertex to another only by traversing a whole original edge.
Choose an orientation of each edge. A canonical description records, for each edge, either no component, one interval $[a_1,b_1]$, or two intervals with
$$ 0\le a_1\le b_1<a_2\le b_2\le1. $$
Included graph vertices are represented consistently on every incident edge, including by degenerate intervals when necessary. These descriptions are unique.
For any fixed vector of component counts, the valid descriptions form a Borel subset of a finite-dimensional Euclidean space. Endpoint consistency is expressed by finitely many endpoint equalities and inequalities. Connectedness is determined by connectivity of the finite intersection graph of the described intervals, hence is likewise a Borel condition.
The description-to-bundle map is continuous on each component-count stratum, because changing interval endpoints by a small amount changes their union by a small Hausdorff distance. It is therefore a Borel bijection from a standard Borel description space onto the compact metric space $\mathcal B$. A Borel bijection between standard Borel spaces has a Borel inverse. Thus the endpoint-description and Hausdorff Borel structures agree. See [Berberian, *Borel Spaces*, Proposition 3.2.5](https://web.ma.utexas.edu/mp_arc/c/02/02-156.pdf).
Moreover,
$$ \{(B,x)\in\mathcal B\times G:x\in B\} $$
is closed: if $B_i\to B$ in Hausdorff distance and $x_i\to x$ with $x_i\in B_i$, then $x\in B$. Bundle membership is therefore jointly measurable, which justifies the load function and all applications of Tonelli’s theorem below.
Lemma. For every bounded measurable function $g$ on $G$, the function
$$ B\longmapsto \int_B g\,d\lambda $$
is continuous on $\mathcal B$.
Proof. Let $d=d_H(B,C)$. Outside the edge portions within coordinate distance $d$ of a graph vertex, a point at graph distance at most $d$ from another bundle must be within coordinate distance $d$ of that bundle on the same edge.
An edge intersection has at most two interval components. Its coordinate $d$-neighborhood adds at most $4d$ of length. Applying this in both directions contributes at most $8md$ outside the vertex neighborhoods. The vertex neighborhoods have total length at most $2md$. Hence
$$ \lambda(B\mathbin{\triangle}C)\le10md, $$
and therefore
$$ \left|\int_Bg\,d\lambda-\int_Cg\,d\lambda\right| \le10m\|g\|_\infty d. $$
$\square$
In particular, each input valuation $v_t$ is continuous.
For $a\in[0,1]$, define
$$ \mathcal B_t(a)=\{B\in\mathcal B:v_t(B)\ge a\}. $$
This is nonempty and compact: it contains $G$. Welfare at least $a$ is equivalent to $P_t(\mathcal B_t(a))=1$ for every type.
Capacity is equivalent to the family of inequalities
$$ \sum_t\mu_t\int_{\mathcal B} \left(\int_Bh\,d\lambda\right)dP_t(B) \le \kappa\int_Gh\,d\lambda \qquad \text{for every continuous }h\ge0. $$
The forward implication follows from Tonelli’s theorem. For the converse, if $\ell>\kappa$ on a set of positive measure, then $\ell\ge\kappa+\rho$ on some positive-measure set for some $\rho>0$. Approximation of its indicator in $L^1(\lambda)$ by nonnegative continuous functions contradicts the tested inequalities. Here $0\le\ell\le1$, so the approximation also controls the tested load.
By the preceding continuity lemma, each tested constraint is closed under weak convergence of the distributions. The varying-threshold support condition is closed as well, since it is equivalent to
$$ \int_{\mathcal B}(a-v_t(B))_+\,dP_t(B)=0. $$
Probability measures on a compact metric space form a compact space in the weak topology. Thus the feasible pairs
$$ (a,P)\in[0,1]\times\prod_t\operatorname{Prob}(\mathcal B) $$
form a compact set. This set is nonempty because singleton bundles give welfare zero and consume no capacity almost everywhere.
It follows that $W^*$ is attained.
The source problem asks whether a connected unweighted graph $H$ has a tree spanning a terminal set $R$, using at most $b$ edges. We need only instances satisfying
$$ |R|\ge2,\qquad 1\le b\le |E(H)|. $$
Here is a direct proof of hardness under these restrictions.
Start from Vertex Cover, whose decision problem is $\mathrm{NP}$-complete. See [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). We may restrict to simple graphs $J$ having $n$ vertices, $p\ge1$ edges, and a bound $1\le k\le n$: excluded cases are directly decidable and can be mapped to fixed restricted YES or NO instances.
Construct $H$ with:
Set
$$ R=\{o\}\cup\{a_e:e\in E(J)\}, \qquad b=p+k. $$
The graph is connected and has
$$ r_0=n+2p $$
edges, with $b\le r_0$.
A vertex cover $S$ gives a terminal-spanning tree with $p+|S|$ edges: use the root edges to $S$, and join each $a_e$ to one endpoint of $e$ in $S$.
Conversely, suppose a terminal-spanning tree uses $s$ vertices corresponding to vertices of $J$. It has $p+1+s$ vertices, hence $p+s$ edges. Each terminal $a_e$ has a neighbor among those $s$ vertices, so they form a vertex cover. Thus a tree with at most $p+k$ edges gives a cover of size at most $k$.
This proves the required source hardness.
Let $(H,R,b)$ be a source instance, and let $r$ be the smallest power of two at least $r_0=|E(H)|$. Add $r-r_0$ pendant padding edges at a fixed vertex of $H$. Call the resulting $r$ edges the pool edges.
Next attach:
All added leaves are distinct. Write $q=|R|$. The allocation graph has
$$ m=r+q+1. $$
Choose positive dyadic numbers $\rho_1,\ldots,\rho_q$ summing to one. Explicitly, if $j=\lceil\log_2q\rceil$, take
$$ \rho_i=2^{-j}\quad(i<q), \qquad \rho_q=1-(q-1)2^{-j}. $$
Set
$$ w=\frac1r, \qquad \alpha=\frac1{4r}, \qquad \kappa=\frac{1+\alpha(b-1)}{2r}, $$
and define
$$ \gamma=r\kappa, \qquad \beta=r\kappa-\alpha b. $$
Create exactly three types:
| Type | Mass | Density |
|---|---:|---|
| Main | $\alpha$ | $w\rho_i$ on marker $i$, $1-w$ on $D$, zero elsewhere |
| Filler | $\beta$ | $1/r$ on every pool edge, zero elsewhere |
| Blocker | $\gamma$ | $1$ on $D$, zero elsewhere |
Each valuation is normalized:
$$ v_{\mathrm{main}}(G) =w\sum_i\rho_i+(1-w)=1, $$
$$ v_{\mathrm{filler}}(G)=r\cdot\frac1r=1, \qquad v_{\mathrm{blocker}}(G)=1. $$
The masses sum to one because
$$ \alpha+\beta+\gamma = \alpha+2r\kappa-\alpha b =1. $$
They are strictly positive. Indeed, $b\le r$ and
$$ \beta=\frac{1-\alpha(b+1)}2>0, \qquad \gamma>0. $$
Also,
$$ \alpha=\frac1{4r}\le\frac1{2r}\le\kappa. $$
Since $r$ is a power of two, all masses, heights, $\kappa$, and $w$ are dyadic. No internal density breakpoints are needed.
The construction has
$$ \tau=3,\qquad K=3m $$
when one segment is listed for every type-edge pair. Connectedness of $H$ gives $q\le r_0+1$, so $m=O(r_0)$. Every numerical datum has bit length $O(\log r_0)$. The construction therefore takes polynomial time and produces polynomial input length.
Suppose $T\subseteq H$ spans $R$ and has $s\le b$ edges.
Give the main type the deterministic bundle consisting of $T$ and all marker edges. It is connected and has main-type value exactly $w$.
Partition $D$ into the $r$ closed intervals
$$ \left[\frac{i-1}{r},\frac{i}{r}\right], \qquad i=1,\ldots,r, $$
and let the blocker choose each with probability $1/r$. Every interval has blocker value $w$. Away from partition endpoints, blocker load is
$$ \frac{\gamma}{r}=\kappa. $$
For a pool edge $e$, define its residual capacity after the main allocation by
$$ c_e=\kappa-\alpha\,\mathbf1_{\{e\in T\}}. $$
These quantities are nonnegative, and their sum is
$$ C=\sum_e c_e =r\kappa-\alpha s \ge r\kappa-\alpha b =\beta>0. $$
Let the filler choose the whole pool edge $e$ with probability $c_e/C$. Every such bundle has filler value $1/r=w$. Its load contribution on $e$ is
$$ \beta\frac{c_e}{C}\le c_e. $$
Thus pool-edge capacity is respected. Marker-edge load is $\alpha\le\kappa$, and dummy-edge load equals $\kappa$ almost everywhere. All three types receive value at least $w$.
Suppose an allocation is feasible with welfare at least $w$.
Every blocker bundle satisfies
$$ \lambda(B\cap D)=v_{\mathrm{blocker}}(B)\ge w $$
almost surely. Therefore, by Tonelli’s theorem,
$$ \kappa \ge \int_D\ell\,d\lambda \ge \gamma\,\mathbb E_{\mathrm{blocker}}\lambda(B\cap D) \ge \gamma w =\kappa. $$
Equality throughout forces every other type’s expected dummy-edge consumption to be zero. Since $\alpha>0$,
$$ \lambda(B\cap D)=0 \qquad \text{for almost every main bundle}. $$
Consequently, almost every main bundle satisfies
$$ w \le v_{\mathrm{main}}(B) = w\sum_i\rho_i\lambda(B\cap\text{marker }i) \le w. $$
Every $\rho_i$ is positive, and each marker has length one. Equality therefore forces full-length inclusion of every marker. Because the bundle is closed, it contains each entire closed marker edge: omitting any point would omit a relatively open subset of positive length.
In particular, almost every main bundle contains all terminals. Its fully included edges contain a terminal-spanning connected subgraph, by Section 2.1. Marker edges, padding edges, and $D$ are pendant and cannot connect distinct vertices of $H$. Removing them leaves a terminal-spanning connected subgraph of $H$, hence a terminal-spanning tree.
Let $s_{\min}$ be the minimum number of edges in such a tree. Every main bundle under consideration has pool-edge length at least $s_{\min}$.
Every filler bundle satisfies
$$ v_{\mathrm{filler}}(B) =\frac{\lambda(B\cap\text{pool})}{r} \ge w=\frac1r, $$
so its pool-edge length is at least one.
Integrating capacity over the $r$ pool edges now gives
$$ r\kappa \ge \int_{\text{pool}}\ell\,d\lambda \ge \alpha s_{\min}+\beta. $$
Using $\beta=r\kappa-\alpha b$ and $\alpha>0$, we obtain
$$ s_{\min}\le b. $$
All capacity arguments above use integrated almost-everywhere inequalities, so shared endpoints and exceptional null sets cause no difficulty.
We have proved the exact equivalence
$$ (H,R,b)\text{ is YES} \quad\Longleftrightarrow\quad \text{the constructed allocation instance is feasible at }w. $$
Thus the existential threshold problem is many-one $\mathrm{NP}$-hard, already with $\tau=3$ and edgewise constant densities. A polynomial-time decision algorithm would imply $\mathrm P=\mathrm{NP}$.
For $a\in[0,1]$, define the least necessary congestion
$$ c(a)= \min_{\substack{P_t\in\operatorname{Prob}(\mathcal B_t(a))\\t=1,\ldots,\tau}} \operatorname*{ess\,sup}_{x\in G} \sum_t\mu_tP_t\{B:x\in B\}. $$
The minimum exists. Indeed, the distribution domain is compact, and essential maximum load is a supremum of continuous tested-load functionals, hence is lower semicontinuous.
Define normalized continuous prices by
$$ \mathcal H= \left\{h\in C(G):h\ge0,\ \int_Gh\,d\lambda=1\right\}, $$
and let
$$ \phi_t(a,h)= \min_{B\in\mathcal B_t(a)}\int_Bh\,d\lambda. $$
The bundle minimum exists by compactness and continuity.
Theorem.
$$ \boxed{ c(a)= \sup_{h\in\mathcal H} \sum_t\mu_t\phi_t(a,h). } $$
Proof. For an allocation $P$, put
$$ F(P,h)= \sum_t\mu_t\int_{\mathcal B_t(a)} \left(\int_Bh\,d\lambda\right)dP_t(B). $$
Its essential maximum load equals $\sup_{h\in\mathcal H}F(P,h)$. The upper bound is immediate. For the lower bound, choose a positive-measure set on which the load exceeds any prescribed number below its essential supremum, approximate its indicator by nonnegative continuous functions in $L^1(\lambda)$, and normalize their integrals.
For fixed $h$, minimizing $F(P,h)$ independently over the type distributions gives
$$ \min_P F(P,h)=\sum_t\mu_t\phi_t(a,h). $$
Thus the displayed supremum is at most $c(a)$.
For the reverse inequality, fix $b<c(a)$. For every $P$, some $h\in\mathcal H$ satisfies $F(P,h)>b$. Continuity in $P$ and compactness give finitely many prices $h_1,\ldots,h_d$ such that
$$ \max_iF(P,h_i)>b \qquad\text{for every }P. $$
The set
$$ S=\{(F(P,h_1),\ldots,F(P,h_d)):P\} $$
is compact and convex, and is disjoint from
$$ O=\{y\in\mathbb R^d:y_i\le b\text{ for every }i\}. $$
Choose a closest pair $s_0\in S$, $o_0\in O$, and put $\theta=s_0-o_0$. Such a pair exists because $S$ is compact and projection onto $O$ is continuous. Its distance is positive. Coordinatewise projection gives
$$ (o_0)_i=\min\{(s_0)_i,b\}, \qquad \theta_i\ge0. $$
Minimality, applied along the segment from $s_0$ to any $s\in S$, gives
$$ \theta\cdot(s-s_0)\ge0. $$
For every coordinate with $\theta_i>0$, we have $(o_0)_i=b$. Therefore
$$ \theta\cdot s \ge \theta\cdot s_0 = b\sum_i\theta_i+\|\theta\|_2^2. $$
The price
$$ h=\frac{\sum_i\theta_i h_i}{\sum_i\theta_i} $$
belongs to $\mathcal H$ and satisfies
$$ \min_PF(P,h) \ge b+\frac{\|\theta\|_2^2}{\sum_i\theta_i} >b. $$
Letting $b$ increase to $c(a)$ proves the reverse inequality. $\square$
Consequently,
$$ \boxed{ a\text{ is feasible} \quad\Longleftrightarrow\quad c(a)\le\kappa \quad\Longleftrightarrow\quad \sum_t\mu_t\phi_t(a,h)\le\kappa \text{ for every }h\in\mathcal H. } $$
Together with attainment, this gives the exact normalized-welfare characterization
$$ \boxed{ \frac{W^*}{\kappa} = \frac1\kappa \max\left\{ a\in[0,1]: \sup_{h\in\mathcal H} \sum_t\mu_t \min_{\substack{B\in\mathcal B\\v_t(B)\ge a}} \int_Bh\,d\lambda \le\kappa \right\}. } $$
This is a variational characterization; it does not assert polynomial-time solvability of the bundle-minimization problems.
Threshold zero is always feasible. If $\kappa\ge1$, giving $G$ to every type proves $W^*=1$, so the normalized optimum is exactly $1/\kappa$.
Fix a rational absolute welfare tolerance $\delta\in(0,1]$.
Subdivide at every input density breakpoint, producing $S\le K+m$ common atoms. For an atom $I$, write
$$ g_I=\max_t f_t|_I, \qquad \eta=\frac{\delta}{2m}, $$
and subdivide it into
$$ q_I=\max\left\{1,\left\lceil\frac{g_I\lambda(I)}{\eta}\right\rceil\right\} $$
equal cells. Every cell has value at most $\eta$ for every type.
Since
$$ \sum_Ig_I\lambda(I) \le \sum_t\int_Gf_t\,d\lambda =\tau, $$
the number $N$ of cells satisfies
$$ N\le K+m+\frac{2m\tau}{\delta}. $$
All grid coordinates and cell values are rational.
Lemma. There is a Borel map $R$ from bundles to connected unions of whole grid cells or grid singletons such that
$$ \lambda(R(B)\setminus B)=0 $$
and, simultaneously for all types,
$$ v_t(R(B))\ge v_t(B)-\delta. $$
Proof. If $B$ contains original graph vertices, retain all wholly contained cells and all original vertices in $B$. The fully included original edges connect those vertices, by Section 2.1, and remain intact under rounding. Every other retained cell belongs to a prefix or suffix attached to that connected part. Thus the result is connected and nonempty.
If $B$ contains no original vertex, it is an interval in one edge interior. Its wholly contained cells, when present, form an interval. If there are none, use a fixed grid singleton.
On each original edge, at most two cells are partly included and lose positive length. Each has value at most $\eta$, so total value loss is at most
$$ 2m\eta=\delta. $$
Any added point is a grid vertex, hence belongs to a fixed finite null set.
The rule is Borel: it depends only on finitely many original-vertex membership tests and whole-cell containment tests. The former are closed tests; the latter are closed because, for a fixed compact cell $C$, the condition $C\subseteq B$ is closed in the Hausdorff topology. $\square$
Applying $R$ to distributions preserves capacity outside that fixed finite null set. Let $W_{\mathrm{grid}}$ denote the optimum restricted to grid bundles. Original admissibility and rounding of an optimal allocation yield
$$ \boxed{ W_{\mathrm{grid}}\le W^*\le W_{\mathrm{grid}}+\delta. } $$
Enumerate every connected nonempty subset of cells, and every grid singleton. There are at most
$$ 2^N+N+1 $$
configurations, since the connected subdivided graph has at most $N+1$ vertices.
For threshold $a$, introduce $z_{t,C}$ only when $v_t(C)\ge a$. This variable represents the population mass of type $t$ receiving $C$. Feasibility is exactly
$$ z_{t,C}\ge0, \qquad \sum_Cz_{t,C}=\mu_t \quad(t=1,\ldots,\tau), $$
$$ \sum_{\substack{t,C\\j\subseteq C}}z_{t,C}\le\kappa \quad(j=1,\ldots,N). $$
These constraints are sufficient because configuration membership is constant on each cell interior; shared endpoints are null. They are necessary by integrating the constant cell-interior loads.
The grid optimum is one of the finitely many configuration values, or zero: for any distribution on a finite configuration space, welfare is the minimum value among its positive-probability type-configuration pairs. Sorting all candidate values and binary-searching with exact rational LP feasibility therefore computes $W_{\mathrm{grid}}$ exactly.
Rational linear programming is polynomial-time in its explicitly listed dimensions and coefficient bit length. Here the dimensions are at most $\tau(2^N+N+1)$ variables and $N+\tau$ constraints, and all rational arithmetic has bit length polynomial in $L$, the bit length $D$ of $\delta$, and the other input parameters. The resulting running time is
$$ \boxed{ 2^{O(K+m+m\tau/\delta)} \operatorname{poly}(m,\tau,K,L,D). } $$
A basic feasible solution uses at most $N+\tau$ nonzero type-configuration variables. Thus the algorithm outputs an explicit finite rational allocation attaining the certified lower bound.
For normalized additive accuracy $\varepsilon\in(0,1]$, when $\kappa<1$, take $\delta=\kappa\varepsilon$. Then
$$ \boxed{ \frac{W_{\mathrm{grid}}}{\kappa} \le \frac{W^*}{\kappa} \le \frac{W_{\mathrm{grid}}}{\kappa}+\varepsilon, } $$
with running time
$$ \boxed{ 2^{O(K+m+m\tau/(\kappa\varepsilon))} \operatorname{poly}(m,\tau,K,L,E). } $$
This computes the optimum to certified accuracy. It need not decide an exact threshold equality $W^*=w$.
There is an additional exact finite reduction when $w=1$.
A closed bundle of type-$t$ value one must contain every closed common atom on which $f_t$ is positive. Otherwise its relatively open complement in that atom would have positive measure and lose positive value.
Apply the rounding rule above using the common atoms themselves as cells. It retains every positive-density atom, remains connected, and never increases consumption almost everywhere. Thus threshold one is feasible exactly when the corresponding whole-atom configuration LP is feasible.
This gives running time
$$ 2^{O(K+m)}\operatorname{poly}(m,\tau,K,L). $$
It also gives membership in $\mathrm{NP}$ for this restricted threshold problem. A basic feasible solution has at most $S+\tau$ positive variables. Its matrix has entries in $\{0,1,-1\}$; after clearing the rational right-hand-side denominators, Cramer’s rule and the Hadamard determinant bound give polynomial-bit rational masses. The selected configurations, connectivity, masses, values, and capacities are all polynomial-time verifiable.
Randomization does not remove the star obstruction.
Let $n\ge2$, let $G$ be a star with $m=2n-1$ unit spokes, and take one type with density $1/m$ everywhere and capacity $\kappa=1/n$.
Choosing each whole spoke with probability $1/m$ is feasible and gives welfare $1/m$.
Suppose welfare were strictly greater than $1/m$. Almost every bundle would have length greater than one, so it would contain the center and positive prefixes on at least two spokes. For each spoke $e$, let $p_e$ be the probability of receiving a positive prefix on it.
At distance $x>0$ from the center, membership probability increases to $p_e$ as $x$ decreases to zero. Choose a decreasing sequence of such points outside the capacity-exceptional null set. Capacity and continuity from below of probability give $p_e\le\kappa$.
Every sampled bundle uses at least two positive prefixes, so
$$ 2\le\sum_ep_e\le m\kappa=\frac{2n-1}{n}<2, $$
a contradiction. Therefore
$$ W^*=\frac1{2n-1}, \qquad \frac{W^*}{\kappa}=\frac{n}{2n-1}. $$
Thus normalized welfare depends on the graph and valuations; the price characterization and finite approximation apply without presupposing a universal closed formula.
⟨structured verdict parsed — rendered above⟩
The output resolves the intended existential decision problem: its reduction establishes $\mathrm{NP}$-hardness, and its congestion-price formula characterizes the optimal normalized welfare. The attainment and approximation arguments are sound. I found one minor imprecision in the discussion of arithmetic bit lengths; it does not invalidate the stated running-time bounds.
The prover explicitly interprets the question as existence of a feasible allocation with $W(P)\ge w$. This matches the evident optimization and complexity question in USER_TASK. Its qualification about checking a supplied, arbitrarily represented Borel distribution is appropriate.
The output claims hardness, rather than membership in $\mathrm{NP}$ for the general problem. Its restricted membership claim at threshold $1$ is separately justified. These claims are internally consistent.
The bounded-component lemma is valid. A connected compact subset avoiding all original vertices lies within one edge interior and is an interval. If it contains an original vertex, an interior component separated from both endpoints of its edge would disconnect the subset. Consequently, each edge intersection consists of at most two components, attached to its endpoints when original vertices are present.
This also justifies identifying bundles with nonempty compact connected subsets of $G$. The hyperspace compactness theorem applies because the metric graph is compact, and the supplied argument correctly shows that connectedness survives Hausdorff limits.
Path connectedness follows from the finite interval representation. The consequence concerning fully included edges is valid: a path connecting original graph vertices must traverse entire original edges between successive original vertices. This consequence is sufficient both for the hardness reduction and for rounding.
The canonical descriptions include degenerate intervals and require consistent representations of shared vertices. With these conventions, uniqueness and the Borel conditions are justified. There are finitely many component-count strata, each a Borel subset of a Euclidean space, so the description space is standard Borel. The target is compact metric, hence also standard Borel. The stated Borel-bijection theorem therefore applies with its hypotheses satisfied; the cited proposition has the stated content. [Berberian, Proposition 3.2.5](https://web.ma.utexas.edu/mp_arc/c/02/02-156.pdf).
Joint membership is closed under the indicated convergences. Thus the load function is measurable and the subsequent uses of Tonelli are justified.
The continuity estimate is valid. Away from the coordinate neighborhoods of original vertices, a path of length at most $d$ cannot leave the current edge. Enlarging at most two interval components contributes at most $4d$ per edge in each direction. The remaining vertex neighborhoods contribute at most $2md$. Therefore the stated bound
$$ \lambda(B\mathbin{\triangle}C)\le 10md $$
supports continuity for every bounded measurable integrand. The input densities satisfy the required boundedness.
Continuous nonnegative test functions characterize the almost-everywhere capacity constraint. In the converse argument, the bound $0\le\ell\le1$ makes the stated $L^1$ approximation sufficient.
Each tested constraint is closed under weak convergence. The varying support restriction is correctly expressed by
$$ \int_{\mathcal B}(a-v_t(B))_+\,dP_t(B)=0. $$
Its integrand is jointly continuous in the threshold and bundle, so the restriction is closed. Compactness of probability measures on the compact metric bundle space applies. Singleton allocations establish nonemptiness, including at threshold zero. The conclusion that $W^*$ is attained follows.
The reduction from Vertex Cover is correct. A cover supplies the described tree with $p+|S|$ edges. Conversely, a terminal-spanning tree using $s$ original vertices has exactly $p+s$ edges, and those original vertices cover every edge of the Vertex Cover instance.
The source restrictions are satisfied: the constructed graph is connected, there are at least two terminals, and
$$ 1\le p+k\le n+2p. $$
Mapping the excluded, directly decidable cases to fixed restricted instances is a routine detail, rather than a substantive gap.
The numerical identities check:
$$ \beta=\frac{1-\alpha(b+1)}2,\qquad \alpha+\beta+\gamma=1,\qquad \gamma w=\kappa. $$
Since $1\le b\le r$ and $\alpha=1/(4r)$, all three masses are positive and $\alpha\le\kappa$. The power-of-two choice makes the constructed numerical data dyadic. All three valuations are normalized, including the marker weights.
Padding, markers, and the dummy edge preserve connectedness and introduce no loops. The graph size, segment count, and numerical encoding lengths are polynomial in the source size.
In the forward allocation, blocker load equals $\kappa$ almost everywhere on the dummy edge. Filler probabilities are well defined because
$$ C=r\kappa-\alpha s\ge\beta>0. $$
Their load on each pool edge is at most its residual capacity. Marker load is permitted because $\alpha\le\kappa$. Every assigned bundle is connected and reaches threshold $w$.
The dummy-edge inequality chain is correct. Equality forces the main type’s expected dummy-edge length to vanish, hence its dummy-edge length vanishes almost surely.
The main valuation then reaches threshold only by obtaining full length on every marker, because all marker weights are strictly positive. Closedness upgrades full-measure inclusion to inclusion of each entire closed marker.
Consequently, almost every main bundle contains all terminals. Its fully included original edges supply a terminal-spanning subgraph. The added edges are pendant, so they cannot provide connections between distinct original vertices. The resulting lower bound of $s_{\min}$ on main-type pool consumption is justified.
Filler bundles consume at least one unit of pool length almost surely. Integrated capacity therefore gives
$$ r\kappa\ge\alpha s_{\min}+\beta, $$
which, with the constructed value of $\beta$, yields $s_{\min}\le b$. All these arguments tolerate the permitted shared endpoints and null exceptional sets.
The exact equivalence required for a polynomial-time many-one reduction is established. The claimed hardness already for three listed types and edgewise constant densities follows.
The distribution domain is nonempty, compact, and convex. Essential maximum load is the supremum of the normalized continuous tested loads, by the supplied indicator-approximation argument. Hence the congestion objective is lower semicontinuous and attains its minimum.
For fixed price, minimizing over probability distributions gives the minimum bundle price separately for each type. Compactness and continuity justify those bundle minima.
The reverse inequality is also valid. Compactness supplies finitely many prices covering the distribution domain. Their load-vector image is compact and convex and is disjoint from the coordinatewise lower orthant at level $b$. The closest-pair calculation correctly produces nonnegative separating weights, with a strictly positive sum. Their normalized combination belongs to $\mathcal H$ and has minimum tested load strictly greater than $b$.
Thus the price identity, threshold characterization, and formula for $W^*/\kappa$ follow. The threshold-zero and $\kappa\ge1$ cases are correctly handled.
The grid bound follows from
$$ \sum_I g_I\lambda(I)\le\tau $$
and the stated ceiling bound. Every cell has value at most $\eta$ for every type.
For a bundle containing original vertices, retaining whole cells preserves the fully included edges connecting those vertices. Remaining retained cells attach through prefixes or suffixes. For a bundle without original vertices, retained cells form an interval; the fallback singleton is admissible.
At most two partially included cells per original edge contribute lost value, giving the stated simultaneous loss bound $\delta$. Added points lie in a fixed finite grid set. The map is Borel by its finite closed containment and membership tests, and its pushforward preserves capacity away from that fixed null set.
Therefore
$$ W_{\mathrm{grid}}\le W^*\le W_{\mathrm{grid}}+\delta $$
is justified.
The configuration count is valid: a connected subdivided graph with $N$ edges has at most $N+1$ vertices. The configuration LP exactly expresses the restricted allocation problem on cell interiors.
On the finite configuration space, welfare is determined by positive-probability type-configuration pairs. Searching the listed valuation thresholds therefore computes the grid optimum exactly. Standard rational LP complexity, applied to the explicitly enumerated dimensions, supports the exponential running-time bounds. The basic-feasible-solution support bound of $N+\tau$ is correct.
Minor issue: The phrase “all rational arithmetic has bit length polynomial in $L$, the bit length $D$ of $\delta$, and the other input parameters” is too broad. Bounds for LP intermediate and output arithmetic also depend on the generated LP dimensions, which need not be polynomial in the original encoding length.
Minimum clarification: Specify that the polynomial bound concerns the grid coordinates and LP input coefficients, and that rational LP arithmetic is polynomial in the explicitly generated dimensions and coefficient encoding lengths. Those dimensions are already accounted for in the displayed exponential running time.
At threshold one, closedness forces inclusion of every positive-density common atom. The rounding argument preserves those atoms, so the finite LP equivalence is valid. Here the number of cells is polynomially bounded by $K+m$; the basic-solution support and determinant bounds consequently give a polynomial-size certificate. The restricted $\mathrm{NP}$ membership claim follows.
The uniform whole-spoke allocation is feasible since $1/(2n-1)\le1/n$.
Welfare strictly exceeding $1/(2n-1)$ forces bundle length greater than one. Such bundles contain the center and positive prefixes on at least two spokes. Along each spoke, membership events increase toward the event of a positive prefix as the coordinate decreases to zero. Choosing coordinates outside the exceptional null set correctly yields $p_e\le\kappa$.
The contradiction
$$ 2\le\sum_e p_e\le(2n-1)/n<2 $$
is valid. Both the optimal welfare and its normalized value are established.
There are no blocking mathematical issues. The minor arithmetic clarification is expositional and leaves the hardness result, attainment, characterization, and certified approximation intact.
⟨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.