Answer: \(\mathrm{NP}\text{-hard}\), and the decision problem is \(\mathrm{NP}\text{-complete}\)
Theorem 11 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet N1 ⊆N be the set of agents who vote 1 in some min-cost arborescence (i.e., MINSUM certificate). Then we can compute in polynomial time a min-cost ar- borescence where all agents in N1 vote 1. Moreover, a ∈N1 iff 1 is reachable from a along edges in E′ output by Fulker- son’s algorithm. On the positive side, Theorems 9 and 11 suggest bi- ased tie-breaking rules for MINMAX and MINSUM, which we denote by MINMAX1 and MINSUM1, selecting the col- lection of concrete votes (Xa)a∈N with the highest pos- sible number of ones.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many role types with rational masses, binary roots 0 and 1, and ranked delegation options between role nodes or canonical delegate offices, choose one option per role so the selected role graph is an arborescence, minimize the mass-weighted rank sum, and subject to optimality maximize the mass whose resolved vote is 1.
A finite set \(T\) of role types has rational masses \(\mu_t\ge 0\) summing to \(1\). Each type \(t\) has a finite ranked ballot \(B_t(0),\ldots,B_t(k_t)\), whose entries are constants \(0,1\), projections \(X_u\), or binary functions \(X_u\vee X_v\) and \(X_u\wedge X_v\), with referenced types distinct from \(t\).
A certificate chooses one rank \(c_t\) per type. It is consistent if there is an order of \(T\) such that, when type \(t\) is reached, substituting values already computed for earlier types makes \(B_t(c_t)\) a constant; assign that constant to \(X_t\). Its cost is \(\sum_{t\in T}\mu_t c_t\).
Target. Is deciding whether a consistent certificate has cost at most \(q\), equivalently computing the minimum cost, NP-hard or solvable in polynomial time?
Nearest known results. In the finite-agent unweighted setting, finding a minimum-sum consistent certificate is NP-hard, and is \(n^{1-\varepsilon}\)-factor inapproximable for every \(\varepsilon>0\), when binary disjunctions are permitted; the same holds when binary conjunctions are permitted. No result for exactly the rational-mass role-type version above was verified.
The rational-mass role-type decision problem is \(\mathrm{NP}\text{-complete}\). Consequently, computing a minimum-cost consistent certificate is \(\mathrm{NP}\text{-hard}\).
Hardness holds under all of the following restrictions:
and it also holds if every disjunction is replaced by a conjunction.
Thus rational masses and type aggregation do not yield a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
A witness consists of a rank \(c_t\) for every \(t\in T\), together with an ordering \(\sigma\) of \(T\).
Process the types in the order \(\sigma\). Since every ballot entry is a constant, a projection, or a binary Boolean function, one can determine in constant time whether substituting the already assigned variables makes the selected entry constant. Reject if this fails at any type.
Finally, compute \(\sum_{t\in T}\mu_t c_t\) using exact rational arithmetic and compare it with \(q\). The bit length of intermediate rational numbers is polynomial in the input length. Hence the decision problem belongs to \(\mathrm{NP}\).
We reduce from Directed Feedback Vertex Set restricted to digraphs of maximum outdegree at most \(2\). This restriction remains \(\mathrm{NP}\text{-complete}\); see the summary of Directed Feedback Vertex Set in [Gruber, *Digraph Complexity Measures and Applications in Formal Language Theory*](https://dmtcs.episciences.org/583/pdf).
We may assume that the input digraph is loop-free. Indeed, every vertex with a loop belongs to every feedback vertex set. Delete all such vertices and decrease the budget accordingly; if their number already exceeds the budget, output a fixed no-instance. This preserves maximum outdegree at most \(2\).
Let the resulting instance be a loop-free digraph \(G=(V,E)\), with \(n=|V|\geq 1\), and an integer \(k\). For \(v\in V\), write \(N^+(v)\) for its set of out-neighbors.
Create one type for every vertex:
Every ballot has ranks \(0\) and \(1\). Define \(B_v(1)=0\) for every \(v\). Define its rank-\(0\) entry according to its outdegree:
Because \(G\) is loop-free, every referenced type is distinct from \(v\). The construction has polynomial size.
For a certificate \(c\), define \(S(c)=\{v\in V:c_v=1\}\). Its cost is exactly \(|S(c)|/n\).
The certificate \(c\) is consistent if and only if \(G[V\setminus S(c)]\) is acyclic.
Suppose first that \(c\) is consistent, witnessed by an ordering \(\sigma\). By induction along \(\sigma\), every computed value is \(0\): rank-\(1\) entries and rank-\(0\) entries of sinks are \(0\), projections copy \(0\), and disjunctions of computed values equal \(0\).
Consider an edge \((v,u)\in E\) with \(v,u\notin S(c)\). Type \(v\) selects its rank-\(0\) entry, which contains \(X_u\). If \(u\) had not occurred before \(v\), then:
Thus \(u\) must precede \(v\). Every edge of \(G[V\setminus S(c)]\) therefore points from a later vertex to an earlier vertex in \(\sigma\). Such a graph cannot contain a directed cycle.
Conversely, suppose \(G[V\setminus S(c)]\) is acyclic. First place every vertex of \(S(c)\) in the order; their selected entries are the constant \(0\). Then order \(V\setminus S(c)\) so that for every edge \((v,u)\) inside \(V\setminus S(c)\), vertex \(u\) precedes \(v\). Such an order exists by reversing a topological ordering.
When \(v\notin S(c)\) is reached, every out-neighbor of \(v\) has already been assigned \(0\). Hence \(B_v(0)\) becomes the constant \(0\). The resulting order witnesses consistency. This proves the lemma.
By the lemma, \(S\subseteq V\) is a directed feedback vertex set if and only if the certificate defined by \(c_v=1\) precisely for \(v\in S\) is consistent. Moreover,
\(\sum_{v\in V}\mu_vc_v=|S|/n\leq k/n=q\)
if and only if \(|S|\leq k\).
Therefore \(G\) has a feedback vertex set of size at most \(k\) if and only if the constructed role-type instance has a consistent certificate of cost at most \(q\). This proves \(\mathrm{NP}\text{-hardness}\) using only binary disjunctions.
Use the same construction, but replace \(0\) by \(1\) and disjunction by conjunction:
Now every computed value is \(1\). A conjunction containing an uncomputed variable cannot become constant because all already computed operands equal \(1\). The preceding lemma and its proof therefore apply verbatim, establishing \(\mathrm{NP}\text{-hardness}\) for conjunction-only instances.
The decision problem is \(\mathrm{NP}\text{-complete}\), already for uniform masses and two-rank ballots. An exact polynomial-time optimization algorithm would decide whether the optimum is at most \(q\), so minimum-cost computation is \(\mathrm{NP}\text{-hard}\).
The role-type terminology does not alter the hardness because the formal model permits one distinct type per vertex or finite agent; no actual aggregation is required in the hard instances.
⟨structured verdict parsed — rendered above⟩
The reduction correctly identifies consistent certificates with directed feedback vertex sets. The disjunction and conjunction constructions are sound, the cost correspondence is exact, and the cited bounded-outdegree Directed Feedback Vertex Set hardness result is supported by the referenced source.
The argument establishes NP-completeness of the decision problem and NP-hardness of exact optimization, subject only to two routine edge-case clarifications.
The proposed witness—a rank \(c_t\) for every type and an ordering of \(T\)—is polynomial in the explicit input size.
For each selected entry, constancy after substituting previously computed variables can be checked in constant time because entries have depth at most one and are restricted to constants, projections, and binary Boolean operations.
The rational cost can also be computed in polynomial time. Adding explicitly encoded rational masses produces numerators and denominators whose bit lengths remain polynomial in the total input length.
There is one minor omission: the verifier should explicitly check that every guessed \(c_t\) satisfies \(0\leq c_t\leq k_t\). This is routine and does not affect the substance of the argument.
The cited Gruber paper explicitly states that Directed Feedback Vertex Set remains NP-complete for digraphs of maximum outdegree at most \(2\), referring in turn to Garey–Johnson Problem GT7. It states this both in the discussion following Theorem 17 and in its summary table. Thus the source problem used by the reduction is supported by the cited reference: [Gruber, pages 198–199 and summary](https://dmtcs.episciences.org/583/pdf).
The loop-removal preprocessing is correct: every looped vertex must belong to every directed feedback vertex set, and deleting all such vertices while reducing the budget preserves the answer and does not increase maximum outdegree.
However, the proof then assumes \(n\geq1\) without handling the case in which preprocessing deletes every vertex. If the reduced budget is nonnegative, that case is a yes-instance, but the construction \(q=k/n\) is undefined. An explicit fixed yes-instance mapping is required. This is a routine edge case rather than a substantive gap.
Each constructed ballot has exactly ranks \(0\) and \(1\), and every dependency is an out-neighbor of the corresponding vertex. Loop-freeness ensures that a ballot never references its own type.
Uniform masses satisfy
\[ \sum_{v\in V}\mu_v=n\cdot \frac1n=1. \]
For \(S(c)=\{v:c_v=1\}\), the cost calculation
\[ \sum_{v\in V}\mu_vc_v=\frac{|S(c)|}{n} \]
is correct.
The construction is polynomial in the graph size because maximum outdegree \(2\) permits every rank-\(0\) entry to be represented by one of the allowed ballot forms.
The induction that every assigned value is \(0\) is valid:
For an induced edge \((v,u)\) with \(v,u\notin S(c)\), if \(u\) were not earlier than \(v\), the selected projection or disjunction would still depend on \(X_u\). In the disjunction case, any other known operand has value \(0\), so it cannot force the expression to be constant. Thus \(u\) precedes \(v\).
It follows that every induced edge points backward in the certificate order, which excludes directed cycles. This direction is correct.
If \(G[V\setminus S(c)]\) is acyclic, placing all vertices in \(S(c)\) first assigns them value \(0\).
A reversed topological ordering of \(G[V\setminus S(c)]\) places every internal out-neighbor \(u\) of \(v\) before \(v\). Out-neighbors belonging to \(S(c)\) were already placed first. Hence every operand in \(B_v(0)\) has already been assigned \(0\), so the entry becomes the constant \(0\).
This establishes consistency. The lemma is therefore correct in both directions.
By the lemma, \(S(c)\) is a directed feedback vertex set exactly when \(c\) is consistent. Moreover,
\[ \frac{|S(c)|}{n}\leq\frac{k}{n} \]
is equivalent to \(|S(c)|\leq k\), since \(n>0\) in the constructed nontrivial case.
The reduction is therefore answer-preserving and proves NP-hardness.
The dual construction is valid. Every computed value is \(1\), and an expression \(X_u\wedge X_w\) cannot become constant while an uncomputed operand remains because every known operand has value \(1\). Thus exactly the same ordering characterization applies.
The phrase “apply verbatim” is slightly informal, but the required substitutions are explicitly stated and the symmetric argument is immediate.
Combining NP membership with the reduction gives NP-completeness of the decision problem. An exact polynomial-time optimization algorithm would decide whether the optimum is at most \(q\), so the claimed NP-hardness of minimum-cost computation follows.
⟨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.