Answer: Polynomial-time solvable: every valid input satisfies \(B=A\) for every admissible run, independently of all minimum-tree and admissible source-connecting choices.
Proposition 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor every problem (N, M, C) and every minimal tree t for (N, M, C), f P,t(N, M, C) = F(N, M, C).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), source set \(M\), positive rational masses \(\mu_t\) summing to \(1\), and a symmetric nonnegative rational cost matrix \(C\) on \(T\cup M\), treat each type as a cohort connected through a shared terminal with zero-cost within-type links. For each distinct positive cost \(\lambda_q\), let \(D^q_{uv}=1\) when \(c_{uv}\ge\lambda_q\) and \(0\) otherwise; let \(P_q\) be the components of its zero-cost graph, \(p_q\) the number containing a source, and \(S_q(t)\) the component containing \(t\). With \(\mu(S)=\sum_{u\in S\cap T}\mu_u\), compute each type's aggregate payment \(A_t=\mu_t\sum_q(\lambda_q-\lambda_{q-1})\left(p_q-1+\frac{\mathbf{1}[S_q(t)\cap M=\varnothing]}{\mu(S_q(t))}\right)\), where \(\lambda_0=0\); determine whether the mass-weighted painting procedure always returns this vector, independently of the minimum tree and source-connecting choices.
Let \(T\) and \(M\) be disjoint nonempty finite sets, with \(m=|M|\). A society is given by its support: the \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Each type is a cohort attached freely to one shared terminal. Connections form the complete undirected graph on \(T\cup M\), with symmetric nonnegative rational costs \(C\) and \(c_{uu}=0\); every cohort requires connection to all sources. Network cost is the sum of its edge costs, independent of masses.
Choose any minimum spanning tree \(H\). Define \(c^*_{uv}=\max_{e\in H[u,v]}c_e\) for distinct vertices and \(c^*_{uu}=0\). Order the components of the source-induced forest \(H[M]\); successively join the accumulated source component to the next by replacing a maximum-cost edge on their connecting path with the edge joining its source endpoints, valued using \(C^*\). An admissible source-connecting choice is such a sequence ending in a minimum spanning tree \(H^*\) for \(C^*\), of the original minimum cost, with \(H^*[M]\) a tree; all admissible orders and ties are allowed.
Define mass-weighted painting as follows. Initially every edge of \(H^*\setminus H^*[M]\) has unpaid balance \(c^*_e\); remove zero-balance edges. Each unfinished type assigns its entire mass to the first unpaid edge on its unique path to \(M\). If \(w_e\) is the assigned mass, advance every unpaid edge by the same amount \(\Delta\), the minimum unpaid balance, and charge each type assigned to \(e\) the aggregate amount \(\mu_t\Delta/w_e\). Remove completed edges and repeat. Finally charge type \(t\) an additional \(\mu_t\sum_{e\in H^*[M]}c^*_e\). Denote its total by \(B_t\).
List the distinct positive costs as \(\lambda_1<\cdots<\lambda_Q\), with \(\lambda_0=0\). Let \(D^q_{uv}=\mathbf1[c_{uv}\ge\lambda_q]\), let \(P_q\) be the components of its zero-cost graph, let \(p_q\) count components meeting \(M\), and let \(S_q(t)\) contain \(t\). Put \(\mu(S)=\sum_{u\in S\cap T}\mu_u\) and
\(A_t=\mu_t\sum_{q=1}^{Q}(\lambda_q-\lambda_{q-1})\left(p_q-1+\frac{\mathbf1[S_q(t)\cap M=\varnothing]}{\mu(S_q(t))}\right)\); an empty sum is zero.
Is deciding whether every admissible painting run on a given input satisfies \(B=A\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard? Does \(B=A\) hold for every input, independently of the minimum tree and admissible source-connecting choices?
For finite individual agents, equal-sharing painting coincides with the folk allocation for every minimum tree and admissible source-connecting choice. [Verified discrete identity](https://mpra.ub.uni-muenchen.de/94312/4/MPRA_paper_94312.pdf). No result settling this precise rational-mass version was located.
Result. The decision problem is polynomial-time solvable: every valid input satisfies \(B=A\) for every admissible run. The identity is independent of the original minimum spanning tree and all admissible source-connecting choices.
The proof below works for arbitrary positive real masses summing to \(1\), and thus includes the specified binary-rational masses. It establishes the mass version directly; the cited discrete identity appears as Proposition 2 of [Bergantiños and Navarro-Ramos](https://mpra.ub.uni-muenchen.de/94312/4/MPRA_paper_94312.pdf).
1. Threshold components of minimum spanning trees.
For a weighted graph \(G\) and a threshold \(a>0\), write \(G_{<a}\) for its subgraph consisting of edges with weight strictly less than \(a\).
We first prove a threshold property. If \(K\) is a minimum spanning tree of \(G\), then \(K_{<a}\) and \(G_{<a}\) have the same connected components.
Every component of \(K_{<a}\) lies inside a component of \(G_{<a}\). Suppose the partitions differ. Some path in \(G_{<a}\) then contains an edge \(uv\) whose endpoints lie in different components of \(K_{<a}\). The unique \(K\)-path between \(u\) and \(v\) contains an edge \(f\) of weight at least \(a\). Adding \(uv\) and deleting \(f\) produces a spanning tree of strictly smaller cost, because \(uv\) has weight less than \(a\). This contradicts minimality and proves the property.
Apply this to the original minimum spanning tree \(H\). By the definition of \(C^*\), for distinct vertices \(u,v\),
\(\displaystyle c^*_{uv}<a \quad\Longleftrightarrow\quad \text{every edge of }H[u,v]\text{ has cost less than }a.\)
Consequently,
\(\displaystyle c^*_{uv}<a \quad\Longleftrightarrow\quad u,v\text{ belong to the same component of the original graph }G_{<a}.\)
Thus the graph of edges satisfying \(c^*_{uv}<a\) has exactly the same components as \(G_{<a}\). Applying the threshold property again, now to any minimum spanning tree \(H^*\) for \(C^*\), gives
\(\displaystyle \operatorname{Comp}(H^*_{<\lambda_q})=P_q \qquad(q=1,\ldots,Q). \)
Here the weights on \(H^*\) are \(c^*\). The strict inequality agrees with the definition of \(P_q\), because \(D^q_{uv}=0\) precisely when \(c_{uv}<\lambda_q\).
Also, every edge weight of \(H^*\) belongs to \(\{0,\lambda_1,\ldots,\lambda_Q\}\): each \(c^*_{uv}\) is a maximum of original edge costs.
2. Painting advances according to edge costs alone.
Fix an arbitrary admissible \(H^*\). Contract its connected source subtree \(H^*[M]\) to one root \(r\). The resulting graph \(F\) is a tree with vertex set \(T\cup\{r\}\); its edges correspond exactly to \(H^*\setminus H^*[M]\). Retain their weights \(d_e=c^*_e\), and orient each edge toward \(r\).
Every unpaid edge has positive assigned mass. Indeed, its endpoint farther from \(r\) is a type \(t\). That edge is the first edge on the path from \(t\) toward \(r\), so whenever it is unpaid, \(t\) assigns its positive mass to it. Hence every denominator \(w_e\) used by painting is positive.
Let \(x\) be the cumulative advancement, meaning the sum of all previous increments \(\Delta\). At every stage:
This holds initially after removing zero-cost edges. If it holds before a stage, the next increment is
\(\displaystyle \Delta=\min_{e:\,d_e>x}(d_e-x), \)
so it holds after that stage as well.
In particular, completion times depend only on the edge costs. The masses affect how each advancement is shared, but do not affect the advancement schedule.
We may split a stage into smaller increments while keeping its assignments fixed: the charges are linear in \(\Delta\). Therefore we may calculate painting separately over the cost intervals from \(\lambda_{q-1}\) to \(\lambda_q\). After painting terminates, these intervals contribute zero.
3. The assigned mass at a threshold.
Fix \(q\). Throughout the interior of the interval from \(\lambda_{q-1}\) to \(\lambda_q\), the completed edges of \(F\) are precisely those with \(d_e<\lambda_q\). This follows because its edge weights belong to the listed cost levels.
Contract the components of \(F_{<\lambda_q}\). The resulting graph is again a rooted tree.
Its nonroot vertices correspond exactly to the components \(S\in P_q\) containing no source. To see this, recall from Section 1 that \(P_q\) is the component partition of \(H^*_{<\lambda_q}\). Contracting the source subtree identifies all source vertices with \(r\). It therefore joins all components meeting \(M\) into the root component, while leaving every component containing no source unchanged. A new connection caused by identifying sources necessarily passes through \(r\).
Let \(S\in P_q\) contain no source. In the contracted rooted tree, \(S\) has exactly one edge \(e_S\) toward the root. For every \(t\in S\), the path toward the root first traverses completed edges inside \(S\), then traverses \(e_S\). Thus every type in \(S\) assigns its mass to \(e_S\).
Moreover, no type outside \(S\) assigns mass to \(e_S\). A type in another nonroot component encounters that component’s own edge toward the root first, and a type in the root component is already finished. Consequently,
\(\displaystyle w_{e_S}=\sum_{t\in S}\mu_t=\mu(S).\)
A type whose component meets \(M\) belongs to the root component and contributes nothing during this interval.
It follows that the contribution of this interval to the nonsource painting charge of type \(t\) is
\(\displaystyle \mu_t(\lambda_q-\lambda_{q-1}) \frac{\mathbf 1[S_q(t)\cap M=\varnothing]}{\mu(S_q(t))}. \)
The denominator is positive whenever the indicator is \(1\), because that component contains \(t\) and \(\mu_t>0\). Summing the intervals, the nonsource charge is therefore
\(\displaystyle B_t^{\mathrm{off}} = \mu_t\sum_{q=1}^{Q}(\lambda_q-\lambda_{q-1}) \frac{\mathbf 1[S_q(t)\cap M=\varnothing]}{\mu(S_q(t))}. \)
4. The source-tree charge.
We next express the cost of \(H^*[M]\) using the same thresholds.
Two sources lie in the same component of \(H^*_{<\lambda_q}\) exactly when their unique \(H^*\)-path consists of edges of weight less than \(\lambda_q\). Because \(H^*[M]\) is connected, this unique path lies entirely in \(H^*[M]\). Hence \(p_q\) is exactly the number of components of the source forest \(H^*[M]_{<\lambda_q}\).
A tree on \(m\) vertices has \(m-1\) edges. A forest on those vertices with \(p_q\) components has \(m-p_q\) edges. Therefore,
\(\displaystyle \bigl|\{e\in H^*[M]:c^*_e\ge\lambda_q\}\bigr| =(m-1)-(m-p_q)=p_q-1. \)
Every source-tree edge weight is one of the listed levels or zero. Decomposing each edge weight into its successive level increments gives
\(\displaystyle \sum_{e\in H^*[M]}c^*_e = \sum_{q=1}^{Q}(\lambda_q-\lambda_{q-1})(p_q-1). \)
Thus the additional source charge of type \(t\) is
\(\displaystyle B_t^{\mathrm{src}} = \mu_t\sum_{q=1}^{Q}(\lambda_q-\lambda_{q-1})(p_q-1). \)
Combining the two charges proves
\(\displaystyle B_t = \mu_t\sum_{q=1}^{Q}(\lambda_q-\lambda_{q-1}) \left( p_q-1+ \frac{\mathbf 1[S_q(t)\cap M=\varnothing]}{\mu(S_q(t))} \right) =A_t. \)
If \(Q=0\), all original costs and all \(C^*\)-costs are zero. Both allocations are then zero, so the identity also holds in that case.
5. Universality and running time.
The proof applies to every minimum spanning tree for \(C^*\) whose source-induced subgraph is a tree. In particular, it applies to every admissible outcome of every initial minimum spanning tree. Its final expression depends only on the original threshold partitions and the masses, proving the requested independence.
On the stipulated domain of valid inputs, the decision algorithm always returns YES. Reading the input and returning that answer takes \(O(L)\) time, with \(O(1)\) additional decision work. This is polynomial in \(m,\tau,L\); no expansion of rational masses or enumeration of admissible choices is required.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes \(B=A\) for every admissible run on every valid input. I found no major or minor mathematical issues.
The threshold property is correctly proved. If the partitions of \(K_{<a}\) and \(G_{<a}\) differ, an edge of \(G_{<a}\) crosses two components of \(K_{<a}\). Its tree path contains an edge of weight at least \(a\), so the stated exchange strictly decreases the spanning-tree cost.
The subsequent applications satisfy the hypotheses:
Thus \(\operatorname{Comp}(H^*_{<\lambda_q})=P_q\) is justified. The strict threshold matches the definition of \(D^q\), including edges whose costs equal \(\lambda_q\).
Contracting the connected source subtree produces the asserted rooted tree on \(T\cup\{r\}\).
The positivity argument is valid: every unpaid edge has a type at its endpoint farther from the root, and that type encounters this unpaid edge first. Consequently, the type remains unfinished and assigns its positive mass to that edge. Hence \(w_e>0\).
The cumulative-advancement invariant follows from the specified rule, which advances every unpaid edge by the same \(\Delta\). The next completion therefore occurs at the next remaining edge-cost level, independently of masses.
Splitting stages at additional original cost levels is legitimate because assignments remain fixed between edge completions and charges are linear in \(\Delta\).
The identification of nonroot contracted components with source-free components of \(P_q\) is correct. Contracting the source subtree merges all source-containing threshold components into the root component and leaves source-free components unchanged.
For each source-free component \(S\), the rooted quotient tree has exactly one outgoing edge toward the root. The proof correctly checks both directions of the assignment claim:
Thus \(w_{e_S}=\mu(S)\), and the displayed interval charge follows directly from the painting rule. All denominators in the formula for a type \(t\) are positive, since \(S_q(t)\) contains \(t\) and \(\mu_t>0\).
Because \(H^*[M]\) is connected, the unique tree path between any two sources lies within it. Therefore its threshold forest has exactly \(p_q\) components.
The edge count \(p_q-1\) for source-tree edges of weight at least \(\lambda_q\) is correct. The level decomposition of their total cost is also correct, including zero-cost edges. Multiplying by \(\mu_t\) gives exactly the prescribed additional source charge.
Adding the two established charge expressions yields the stated \(A_t\).
The proof explicitly handles \(Q=0\). Its reasoning also covers \(m=1\), zero-cost edges, tied costs, and positive masses of arbitrary unequal sizes.
The argument applies to each admissible outcome individually and does not assume a particular initial minimum tree, source order, or tie resolution. Its final expression uses only the original threshold partitions and masses, establishing the claimed independence.
On the stipulated domain of valid inputs, returning YES is consequently correct. The stated \(O(L)\) running time for reading the input and returning YES is valid; neither mass expansion nor enumeration of choices is needed.
The cited discrete identity is not used as a premise. No external theorem is needed to complete the supplied argument, and no additional clarification is required.
⟨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.