Answer: \(\mathrm{NP}\)-complete, hence \(\mathrm{NP}\)-hard.
Proposition 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor every ϕ ∈F, ϕ-CFD is NP-hard when restricted to instances where |A| = 2, and u1 = u2 = 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite graph \(G=(V,E)\), one agent type \t\ with \u_t(v)=1\ for every \v\, and rational per-capita supplies \(\rho_v)_{v\in V}\, decide whether there are nonnegative rational masses \lambda_{t,S})\ over connected integral bundles S\subseteq V)\ with finite support such that \sum_S\lambda_{t,S}=1\), \(\sum_{S\ni v}\lambda_{t,S}=\rho_v\)\ for every \v\, and support-wise envy-freeness: \(\lambda_{t,S},\lambda_{t,R}>0\) implies \(u_t(S)\ge u_t(R)\).
Let \(G=(V,E)\) be a finite simple undirected graph with \(m=|V|\ge 1\), and let \(\rho_v\in\mathbb{Q}\cap[0,1]\) be the per-capita supply of each vertex \(v\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass encoded as a binary rational; \(\tau\) counts supported types, not possible types. Here there is exactly one type \(t\), of mass \(1\), with additive unit valuations. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
An admissible integral bundle is a nonempty subset \(S\subseteq V\) such that \(G[S]\) is connected. Vertices are indivisible within each bundle; different bundles may overlap.
Decide whether there exist nonnegative rational masses \(\lambda_{t,S}\), with finite support over admissible bundles, satisfying \(\sum_S\lambda_{t,S}=1\) and \(\sum_{S\ni v}\lambda_{t,S}=\rho_v\) for every \(v\in V\). Supplies must be exhausted exactly; they need not sum to \(1\).
Require support-wise envy-freeness: for every ordered pair \(S,R\), if \(\lambda_{t,S}>0\) and \(\lambda_{t,R}>0\), then \(u_t(S)\ge u_t(R)\).
Is this decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For discrete agents, deciding whether all vertices can be partitioned into connected envy-free bundles is \(\mathrm{NP}\)-hard even for two agents with identical unit valuations. [Source](https://www.ijcai.org/proceedings/2021/0020.pdf)
No result settling the exact mass-allocation problem above was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, even when \(\tau=1\), the graph is connected and bipartite, and every supply belongs to \(\{1/2,1\}\).
The hardness proof below directly addresses the mass-allocation problem. It does not rely on transferring hardness from discrete partitions.
Write \(\lambda_S=\lambda_{t,S}\). Since valuations are additive and unit-valued, \(u_t(S)=|S|\).
If \(S\) and \(R\) both have positive mass, applying envy-freeness to both ordered pairs gives \(|S|\ge |R|\) and \(|R|\ge |S|\). Thus all supported bundles have a common cardinality \(k\). Exact exhaustion implies
\(\displaystyle \sum_{v\in V}\rho_v=\sum_{v\in V}\sum_{S\ni v}\lambda_S=\sum_S\lambda_S|S|=k.\)
Consequently, feasibility requires \(\sum_v\rho_v\) to be an integer in \(\{1,\ldots,m\}\), and every supported bundle must have that cardinality.
We also need the following observation: a vertex of supply \(1\) belongs to every supported bundle. Indeed,
\(\displaystyle \sum_{S:\,v\notin S}\lambda_S=1-\rho_v=0,\)
and all masses are nonnegative.
We reduce from the standard \(\mathrm{NP}\)-complete problem \(3\)-SAT. This is the only external hardness theorem used. [Karp’s original paper, reprinted](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Let the input formula be
\(\displaystyle \Phi=\bigwedge_{j=1}^{q}(\ell_{j,1}\lor\ell_{j,2}\lor\ell_{j,3}),\)
over variables \(x_1,\ldots,x_n\), with \(n\ge 1\). Introduce another variable \(z\). For each clause, require that the four literals
\(\displaystyle \ell_{j,1},\ell_{j,2},\ell_{j,3},z\)
include at least one true literal and at least one false literal. Call these the augmented requirements.
Claim. The original formula is satisfiable if and only if the augmented requirements are satisfiable.
Proof. Given a satisfying assignment of \(\Phi\), set \(z\) false. Every augmented requirement contains a true original literal and the false literal \(z\).
Conversely, suppose an assignment satisfies the augmented requirements. If \(z\) is true, complement every variable, including \(z\). Complementation reverses the truth value of every literal, including negated literals, so the property of containing both truth values is preserved. We may therefore assume \(z\) is false. Each augmented requirement then needs a true original literal, so every clause of \(\Phi\) is satisfied. \(\square\)
In particular, satisfying assignments of the augmented requirements occur in complementary pairs.
Put \(N=n+1\), and regard \(z\) as variable \(x_N\). Construct the following vertices:
Let \(\operatorname{vert}(x_i)=p_i\) and \(\operatorname{vert}(\neg x_i)=n_i\).
Add precisely these edges:
Repeated edges are retained only once, so the graph is simple.
Let \(F\) consist of the root, all guards, and all clause vertices. Set
\(\displaystyle \rho_v=1\quad(v\in F),\qquad \rho_{p_i}=\rho_{n_i}=1/2\quad(1\le i\le N).\)
There is exactly one supported type, of mass \(1\), with unit valuations.
The graph is bipartite, with sides \(F\) and the literal vertices. It is connected: every literal is adjacent to \(r\), every guard has literal neighbors, and each clause vertex has a neighbor representing \(z\) or \(\neg z\).
The construction has
\(\displaystyle |F|=1+N+2q,\qquad m=1+3N+2q,\qquad |E|\le 4N+8q.\)
Its total supply is
\(\displaystyle \sum_v\rho_v=|F|+N=:k.\)
The construction takes polynomial time; with an edge-list encoding, it uses \(O((n+q)\log(n+q))\) output bits and bit operations.
Suppose the allocation instance is feasible, and choose any supported bundle \(S\), which exists because the masses sum to \(1\).
By Section 1, \(F\subseteq S\) and \(|S|=k=|F|+N\). Hence \(S\) contains exactly \(N\) literal vertices.
For each variable, \(g_i\in S\). Its only neighbors are \(p_i,n_i\). If neither belonged to \(S\), then \(g_i\) would be isolated in \(G[S]\). Since \(r\in S\) and \(r\ne g_i\), this would contradict connectivity. Thus \(S\) contains at least one literal vertex from each of the \(N\) pairs. Having exactly \(N\) literal vertices, it contains exactly one from each pair.
Define an assignment \(A\) by declaring \(x_i\) true precisely when \(p_i\in S\).
The vertex \(c_j^+\) belongs to \(S\), and connectivity requires it to have a neighbor in \(S\). By its neighborhood definition, at least one of \(\ell_{j,1},\ell_{j,2},\ell_{j,3},z\) is true under \(A\).
Likewise, \(c_j^-\) must have a neighbor in \(S\). At least one of the complements of those four literals is true, meaning at least one of the original four literals is false.
Therefore \(A\) satisfies every augmented requirement. Section 2 implies that \(\Phi\) is satisfiable.
Suppose \(\Phi\) is satisfiable. Extend a satisfying assignment by setting \(z\) false, obtaining an assignment \(A\) satisfying every augmented requirement. Its complement \(\overline A\) also satisfies them.
Define
\(\displaystyle S_A=F\cup\{p_i:A(x_i)=1\}\cup\{n_i:A(x_i)=0\},\)
and define \(S_{\overline A}\) analogously.
Both bundles have cardinality \(|F|+N=k\). Both induce connected graphs:
Thus every vertex in either bundle has a path to \(r\) inside that bundle.
Assign mass \(1/2\) to each of \(S_A,S_{\overline A}\), and zero elsewhere. Every vertex of \(F\) occurs in both bundles, exhausting supply \(1\). Every literal vertex occurs in exactly one, exhausting supply \(1/2\). The masses sum to \(1\).
Finally, both supported bundles have cardinality \(k\), so support-wise envy-freeness holds.
This proves the required equivalence and establishes \(\mathrm{NP}\)-hardness.
We now prove membership in \(\mathrm{NP}\).
For any feasible instance, fix its common supported cardinality \(k\). Among feasible allocations, choose one with minimum support size \(s\), with bundles \(S_1,\ldots,S_s\) and positive masses \(\lambda_1,\ldots,\lambda_s\).
Associate each bundle with the column
\(\displaystyle a_j=(1,\mathbf 1_{S_j})\in\{0,1\}^{m+1}.\)
These columns are linearly independent. Otherwise, Gaussian elimination gives a nonzero rational vector \(d\) with \(\sum_jd_ja_j=0\). Its first-coordinate equation is \(\sum_jd_j=0\), so \(d\) has both positive and negative entries. Set
\(\displaystyle \varepsilon=\min_{j:d_j>0}\frac{\lambda_j}{d_j}.\)
Replacing each mass by \(\lambda_j-\varepsilon d_j\) preserves all allocation equations, keeps every mass nonnegative, and makes at least one mass zero. All remaining bundles still have cardinality \(k\), preserving envy-freeness. This contradicts minimum support. Therefore \(s\le m+1\).
Let \(A\) be the matrix of these columns and \(b=(1,\rho)\). Select \(s\) rows giving an invertible square matrix \(B\), and let \(b'\) be the corresponding entries of \(b\). The masses satisfy \(B\lambda=b'\).
Let \(D\) be the product of the denominators of the input supplies. Its bit length is \(O(L)\), and every entry of \(Db'\) is an integer between \(0\) and \(D\). By Cramer’s rule,
\(\displaystyle \lambda_j=\frac{\det C_j}{D\det B},\)
where \(C_j\) replaces column \(j\) of \(B\) by \(Db'\). Expanding determinants gives
\(\displaystyle |\det B|\le s!,\qquad |\det C_j|\le s!D.\)
Hence each mass has a rational encoding of length \(O(L+m\log(m+1))\).
A certificate listing the bundles and masses therefore has total length \(O(mL+m^2\log(m+1))\). Connectivity, common cardinality, nonnegativity, normalization, and all exhaustion equations can be checked exactly in \(\operatorname{poly}(m,\tau,L)\) bit operations, with \(\tau=1\).
Thus the problem belongs to \(\mathrm{NP}\).
The exact mass-allocation problem is \(\mathrm{NP}\)-complete. Consequently, an algorithm with running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\), even under the graph and supply restrictions stated above.
⟨structured verdict parsed — rendered above⟩
The proof establishes the claimed \(\mathrm{NP}\)-completeness. Both directions of the reduction and the polynomial-size rational certificate argument are correct. No major or minor issues require repair.
The reduction directly addresses rational mass allocations with overlapping bundles and exact exhaustion. It also establishes all claimed restrictions: one supported type, a connected simple bipartite graph, and supplies in \(\{1/2,1\}\).
Correct. Envy-freeness applies to both ordered pairs of any two supported bundles. Since utility equals cardinality, their cardinalities must coincide.
The total-supply identity is valid: the graph and allocation support are finite, so the sums may be interchanged. Normalization then makes total supply equal the common cardinality \(k\). Nonempty bundles give \(1\le k\le m\).
The supply-\(1\) observation is also correct. The total mass of bundles omitting such a vertex is zero, so no positive-mass bundle omits it.
Correct. The invoked external theorem is the standard \(\mathrm{NP}\)-completeness of \(3\)-SAT; the cited [Karp paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf) contains the bounded-clause satisfiability hardness result.
Both directions of the augmented-formula equivalence are valid:
Repeated literals and tautological clauses do not invalidate these arguments.
Correct. All edges join a vertex of \(F\) to a literal vertex, proving bipartiteness. Every literal reaches the root directly; every guard and clause vertex has a literal neighbor, proving connectivity. Removing repeated edges preserves all specified neighborhoods and ensures simplicity.
The counts are correct:
\[ |F|=1+N+2q,\qquad m=1+3N+2q. \]
Root and guard edges contribute \(4N\); the two clause vertices per clause contribute at most eight edges, giving the stated bound.
The supply sum is \(|F|+N\), since each literal pair contributes one unit. The construction and its edge-list encoding are polynomial in the source-instance size.
Correct. Normalization ensures that a supported bundle exists. Every such bundle contains all of \(F\) and exactly \(N\) literal vertices.
Each guard must have a selected literal neighbor: otherwise it is isolated while the distinct root also belongs to the bundle. Thus every variable pair contributes at least one literal vertex. The exact count forces precisely one from each pair.
Under the resulting assignment, connectivity of each positive clause vertex forces a true augmented literal. Connectivity of its negative counterpart forces a false augmented literal. Therefore all augmented requirements hold, and Section 2 applies.
There is no unsupported assumption that the allocation forms a partition.
Correct. The assignment and its complement select exactly one literal per variable. The connectivity justification accounts for every vertex category and supplies paths to the root inside each induced subgraph.
The bundles are distinct because \(N\ge1\). Giving each mass \(1/2\) exhausts every forced vertex’s supply \(1\) and every literal vertex’s supply \(1/2\). Normalization and rationality hold. Equal cardinalities establish envy-freeness for every ordered pair of supported bundles.
Correct. A minimum support size exists among feasible rational allocations. If its columns were dependent, their rational entries permit a nonzero rational dependence vector. Its coordinates sum to zero, so it has both signs.
The specified positive rational perturbation preserves every equality, keeps masses nonnegative, and eliminates at least one supported bundle. It also preserves common cardinality and hence envy-freeness. This contradicts minimality, proving \(s\le m+1\).
Column independence permits the stated invertible square submatrix. The denominator product has bit length \(O(L)\). Cramer’s rule and the determinant bounds are correct: each determinant term contains only binary entries, except for one entry bounded by \(D\) in the replaced-column case.
Consequently, the stated mass-encoding and total-certificate bounds hold. Exact rational arithmetic, connectivity checks, and cardinality checks take polynomial time in \(m,\tau,L\), with \(\tau=1\).
The membership argument does not require connectivity of the input graph or the restricted supplies used in the reduction. Infeasible total supplies cannot admit an accepted certificate. The singleton-graph case causes no exception to the argument.
The conclusion correctly says that a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\); it does not assert an unconditional separation.
None. No additional lemma, calculation, or clarification is needed to establish the claimed complexity classification.
⟨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.