Answer: \(\mathrm{P}\): exact optimization and the strict threshold decision are possible in \((\tau^4+L)^{O(1)}\) bit time.
Theorem 13 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-hard to determine whether the value of the optimal coalition structure exceeds an input k.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed weighted network whose edge roles \(a\) have endpoints and weights \(w_a\), and a population distribution \(\mu\) over those roles, maximize total team value over simple source-to-target paths \(r\). For each path let \(q(r)=\min_{a\in r}w_a\), and let \(x_r\ge 0\) be the mass of teams assigned to \(r\). Find an optimal \(x\) for \(\max \sum_r q(r)x_r\), subject to \(\sum_{r\ni a}x_r\le \mu_a\) for every role \(a\).
Let the input network be a finite undirected graph \(G=(V,E)\), with distinct terminals \(s,t\), \(m=|E|\) edge roles, and positive binary-rational weights \(w_a\). Parallel edges are distinct roles; the network is part of the input.
A society is given by its support: the list of the \(\tau\) roles with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. Set omitted masses to zero and require \(\sum_{a\in E}\mu_a=1\).
Let \(R\) contain all simple \(s\)-to-\(t\) paths and define \(q(r)=\min_{a\in r}w_a\). An assignment gives each path a real team mass \(x_r\geq0\), consuming \(x_r\) mass of every role on that path; unused population mass contributes zero value.
Define \(\operatorname{OPT}=\max\{\sum_{r\in R}q(r)x_r:\sum_{r\ni a}x_r\leq\mu_a\text{ for every }a\in E,\ x_r\geq0\}\), with value zero when \(R\) is empty. Let \(L\) be the total binary input length, including an input threshold \(K\in\mathbb{Q}_{\geq0}\).
Is deciding whether \(\operatorname{OPT}>K\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), \(|V|\), and \(L\).
For indivisible edge agents, maximizing the sum of coalition values—each coalition worth its strongest contained path, or zero—is \(\mathrm{NP}\)-hard, and admits a polynomial-time \(O(\log m)\)-approximation ([source](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p589.pdf)).
No result settling this exact continuous formulation was identified in the literature search.
Deciding whether \(\operatorname{OPT}>K\) is in \(\mathrm{P}\). In fact, the exact optimum can be computed by a polynomial-size rational linear program.
The proof below uses continuous flows with shared edge capacities. It does not assume an integral optimum.
Let \(S=\{a\in E:\mu_a>0\}\), so \(|S|=\tau\).
If a path \(r\) contains an edge \(a\notin S\), its capacity constraint implies
\(\displaystyle 0\le x_r\le\sum_{r'\ni a}x_{r'}\le\mu_a=0.\)
Consequently, deleting all edges outside \(S\) preserves the optimum. If loops are allowed, they can also be deleted because a simple path cannot use them. No renormalization of the remaining masses is needed.
Retain only the endpoints of remaining edges together with \(s,t\). Write \(H\) for this graph and \(h\) for its number of vertices. Then
\(\displaystyle h\le\min\{|V|,2\tau+2\}.\)
Parallel edges remain distinct roles throughout.
If \(H\) contains no \(s\)-to-\(t\) path, then \(\operatorname{OPT}=0\), and the answer is negative because \(K\ge0\). Henceforth suppose such a path exists.
Let
\(\displaystyle \lambda_1<\lambda_2<\cdots<\lambda_d\)
be the distinct weights of the remaining edges. Thus \(d\le\tau\). For each \(k\), define the threshold graph
\(\displaystyle H_k=(V(H),E_k),\qquad E_k=\{a\in E(H):w_a\ge\lambda_k\}.\)
Every path in \(H_k\) has quality at least \(\lambda_k\).
For each threshold \(k\), replace every edge \(a=\{u,v\}\in E_k\) by two directed arcs, retaining the identity of \(a\). Let \(A_k\) be this directed arc set.
Introduce nonnegative variables \(f_{k,a,u\to v}\) and \(f_{k,a,v\to u}\) for these arcs, and a nonnegative variable \(z_k\) for the flow value in layer \(k\).
Define \(b(s)=1\), \(b(t)=-1\), and \(b(v)=0\) at every other vertex. Impose flow conservation:
\(\displaystyle \sum_{\alpha\in\delta_k^+(v)}f_{k,\alpha} -\sum_{\alpha\in\delta_k^-(v)}f_{k,\alpha} =b(v)z_k \qquad(k=1,\ldots,d,\ v\in V(H)). \)
Here \(\delta_k^+(v)\) and \(\delta_k^-(v)\) denote the outgoing and incoming arcs at \(v\) in \(A_k\).
All layers share each role’s capacity:
\(\displaystyle \sum_{k:\,a\in E_k} \bigl(f_{k,a,u\to v}+f_{k,a,v\to u}\bigr) \le\mu_a \qquad(a=\{u,v\}\in E(H)). \)
Maximize
\(\displaystyle \sum_{k=1}^{d}\lambda_k z_k.\)
Call this linear program \(P\).
It is feasible: all variables can be zero. Every arc variable is at most its role’s mass, hence at most \(1\). Conservation at \(s\) also gives
\(\displaystyle 0\le z_k \le\sum_{\alpha\in\delta_k^+(s)}f_{k,\alpha} \le\sum_{a\in E(H)}\mu_a \le1. \)
Thus its feasible region is bounded and closed, and its optimum is attained.
Take any feasible assignment \((x_r)\). Its positive-mass paths lie in \(H\).
Every such path has quality equal to one of the thresholds. Assign \(r\) to the unique layer \(k\) satisfying \(q(r)=\lambda_k\), and send \(x_r\) units along its directed orientation from \(s\) to \(t\).
These flows satisfy conservation. Their aggregate consumption of role \(a\) is exactly
\(\displaystyle \sum_{r\ni a}x_r\le\mu_a,\)
so they satisfy the shared capacities. Moreover,
\(\displaystyle \sum_k\lambda_k z_k =\sum_r q(r)x_r. \)
Therefore
\(\displaystyle \operatorname{OPT}\le\operatorname{OPT}(P).\)
Take any feasible solution of \(P\). We first justify the required decomposition for one layer \(k\).
Add a distinguished artificial arc \(t\to s\) carrying \(z_k\) units. Conservation now holds at every vertex, including \(s,t\), so the augmented flow is a nonnegative circulation.
Circulation decomposition. Every nonzero nonnegative circulation on a finite directed multigraph decomposes into finitely many simple directed cycles with nonnegative masses.
To prove this, start from a positive-flow arc and continue following positive-flow arcs. Whenever a vertex is reached along a positive-flow arc, conservation guarantees a positive-flow outgoing arc. Finiteness forces a repeated vertex; the segment between the first repetition is a simple directed cycle. Subtract the minimum flow on its arcs. The remainder is a nonnegative circulation, and at least one positive-flow arc disappears. Repetition terminates after at most the initial number of positive-flow arcs.
Apply this decomposition to the augmented layer:
The masses of the retained paths sum to \(z_k\), because the cycle decomposition accounts for all \(z_k\) units on the artificial arc. Their consumption of each original directed arc is at most its original flow.
After forgetting orientations, each retained path is a simple path in \(H_k\), with its edge-role identities preserved. Hence its quality is at least \(\lambda_k\).
Perform this construction in every layer and aggregate masses assigned to identical paths. For each role \(a=\{u,v\}\), the resulting assignment satisfies
\(\displaystyle \sum_{r\ni a}x_r \le \sum_{k:\,a\in E_k} \bigl(f_{k,a,u\to v}+f_{k,a,v\to u}\bigr) \le\mu_a. \)
It is therefore feasible for the original problem. Its value is at least the layered objective:
\(\displaystyle \sum_r q(r)x_r \ge\sum_k\lambda_k z_k. \)
Taking an optimal solution of \(P\) gives
\(\displaystyle \operatorname{OPT}\ge\operatorname{OPT}(P).\)
Combining both directions proves
\(\displaystyle \boxed{\operatorname{OPT}=\operatorname{OPT}(P)}.\)
The inequality in the second direction is intentional: a path extracted from layer \(k\) may have quality strictly greater than its credited threshold \(\lambda_k\). This only improves the original assignment.
The formulation has
\(\displaystyle N=2\sum_{k=1}^{d}|E_k|+d \le2d\tau+d \)
variables, at most \(\tau\) shared-capacity inequalities, and \(dh\) conservation equations. Nonnegativity contributes another \(N\) inequalities. Therefore
\(\displaystyle N=O(d\tau),\qquad C=O(d\tau+dh+\tau). \)
Before removing isolated vertices, these bounds are \(O(\tau^2)\) variables and \(O(\tau^2+\tau|V|)\) constraints. After the support restriction and vertex removal, both are \(O(\tau^2)\), since \(h\le2\tau+2\).
All constraint-matrix coefficients belong to \(\{-1,0,1\}\). The nonzero right-hand sides are input masses, and the nonzero objective coefficients are distinct input weights. Consequently, even a dense encoding of \(P\) has total binary length
\(\displaystyle B=O(\tau^4+L).\)
The rational linear-programming theorem provides an algorithm that returns an exact rational optimal solution in time polynomial in the LP’s binary encoding length. This applies here because \(P\) is explicitly represented, has rational coefficients, is feasible, and is bounded. Exact rational optimization, including recovery of an optimal rational solution, is discussed in [Trevisan’s linear-programming notes, Sections 2.4–2.5](https://lucatrevisan.github.io/cs261/lecture05.pdf).
Compute its rational objective value \(v^*\), then compare it exactly with the rational input \(K\), using integer cross multiplication with positive denominators. The optimal solution and objective have polynomial encoding length, so this comparison also takes polynomial bit time. In particular, equality with \(K\) is handled exactly.
A valid total bit-time bound, including preprocessing, is
\(\displaystyle (\tau^4+L)^{O(1)}. \)
Since \(\tau\le m\), this also gives the requested bound
\(\displaystyle (m+\tau+|V|+L)^{O(1)}. \)
The graph preprocessing uses \(O(m+|V|)\) graph operations if the full graph is scanned, followed by \(O(\tau\log\tau)\) rational weight comparisons. The optimization stage depends on unsupported edges and discarded vertices only through the input-reading cost.
Finally, the cited hardness result concerns partitions of indivisible edge agents, as stated in [*Cooperative Weakest Link Games*](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p589.pdf). Such a partition restricts role sharing. The continuous formulation permits fractional sharing, and the proof above establishes polynomial-time exact optimization for that formulation.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The layered linear program is equivalent to the stated continuous problem, and the exact decision procedure runs in polynomial bit time. I found no major or minor issues requiring repair.
For every unsupported role \(a\), nonnegativity and its zero capacity force \(x_r=0\) for every path containing \(a\). Deleting unsupported edges therefore preserves the optimum.
Deleting loops is valid under the stipulated simple-path definition. Removing isolated vertices other than the terminals preserves all relevant paths, and the bound \(h\le\min\{|V|,2\tau+2\}\) is correct. If supported loops were deleted, the retained edge count can be smaller than \(\tau\); all subsequent bounds remain valid upper bounds.
The disconnected case is handled correctly: the optimum is zero, so the strict comparison is false for every permitted \(K\ge0\). Distinct terminals ensure that every relevant path contains an edge and therefore has a well-defined minimum weight.
Every retained path’s quality equals one of the distinct retained edge weights. Consequently, its designated layer exists uniquely, and every edge on that path belongs to that layer.
The two directed arcs representing an undirected edge retain its role identity. Summing both orientations across all layers correctly enforces the original role capacity. In particular, parallel edges remain separate capacity resources.
The conservation equations have the correct signs at both terminals. Nonnegative \(z_k\) excludes flows with negative credited value.
The zero solution is feasible. Every arc variable is bounded by its role capacity, which is at most one.
Conservation at \(s\) gives \(z_k\) as outgoing flow minus incoming flow. Since incoming flow is nonnegative, the stated outgoing-flow bound follows. After loop deletion, each retained edge contributes at most one outgoing arc at \(s\), so the bound by total retained population mass is valid.
Thus every variable is bounded. The feasible region is closed and nonempty, establishing attainment of the LP optimum.
Orienting each simple path from \(s\) to \(t\) gives the required conservation equations. Assigning it to the layer corresponding to its actual quality preserves its objective contribution exactly.
Because each simple path uses a role at most once, aggregate directed-arc consumption equals the original path consumption. The shared capacities therefore hold, proving \(\operatorname{OPT}\le\operatorname{OPT}(P)\).
Adding the distinguished arc \(t\to s\) with flow \(z_k\) cancels both terminal imbalances and produces a nonnegative circulation.
The supplied circulation-decomposition argument is valid for finite directed multigraphs and real flows. Following positive-flow arcs cannot stop, and stopping at the first repeated vertex produces a simple directed cycle. Subtracting its minimum arc flow preserves conservation and eliminates at least one positive-flow arc. Hence termination is finite; rationality or integrality is unnecessary.
A simple cycle containing the distinguished arc yields a simple \(s\)-to-\(t\) path upon its removal. Distinguishing that arc also handles any existing parallel \(t\to s\) arc correctly. The retained cycle masses sum exactly to \(z_k\), and discarding other cycles only reduces capacity consumption. When \(z_k=0\), no retained paths are required.
Forgetting orientations preserves vertex simplicity and role identity. Each extracted path lies in its threshold graph and has quality at least its credited threshold. Aggregation across layers therefore preserves feasibility and gives value at least the LP objective. This proves the reverse inequality and establishes exact equivalence.
The variable and constraint counts are correct. With \(d\le\tau\) and \(h\le2\tau+2\), both are \(O(\tau^2)\). Converting conservation equations to inequalities changes these bounds only by a constant factor.
A dense constraint matrix consequently requires \(O(\tau^4)\) bits: its entries have constant encoding length. Each nonzero mass and each selected objective weight occurs once in the respective vectors, so their combined encoding length is \(O(L)\). Thus \(B=O(\tau^4+L)\) is valid.
The invoked rational-LP theorem is stated sufficiently precisely, and its hypotheses—explicit rational data, feasibility, and boundedness—are verified. The cited [Trevisan notes, Sections 2.4–2.5](https://lucatrevisan.github.io/cs261/lecture05.pdf) support polynomial-time exact optimization and polynomial-size rational optimal solutions.
Exact cross multiplication handles the strict threshold, including equality. The bounds \((\tau^4+L)^{O(1)}\) and \((m+\tau+|V|+L)^{O(1)}\) are valid. The preprocessing counts appropriately distinguish graph operations and rational comparisons from total bit time.
The cited [coalition-structure result](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p589.pdf) concerns partitions of edge agents. The prover correctly distinguishes that restriction from fractional role sharing. Its continuous complexity conclusion follows independently from the verified LP equivalence.
No additional clarification is needed.
⟨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.