Answer: \(\mathrm{NP}\)-hard; \(\mathrm{W}[1]\)-hard and in \(\mathrm{XP}\) parameterized by \(w\). Not \(\mathrm{FPT}\) in \(w\) alone unless \(\mathrm{FPT}=\mathrm{W}[1]\); \(\mathrm{FPT}\) parameterized by \((w,D)\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe number of messages passed in DPOP in solving a SCP is 2m, (n −1) and (n −1) for phases one, two and three respectively, where n and m are the number of nodes and edges in the DCOP model with replicated variables. The maximal number of utility values computed by any node in DPOP is O(Dw+1), and the largest UTIL message has O(Dw+1) entries, where w is the induced width of the centralized problem graph.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given public finite-domain decision variables, public constraints defining a feasible set, and a finite support \(\mathcal{T}\) of complete participant types, each with a scope and rational utility table, and binary-rational masses \(\mu_t\) summing to one, find a feasible assignment maximizing \(\sum_{t\in\mathcal{T}}\mu_t u_t(x_{S_t})\) and report its exact welfare.
Input: \(m\geq 1\) public variables \(X_j\) with explicitly listed nonempty finite domains \(d_j\), and public hard constraints given by scopes and explicit tables of allowed tuples. Their feasible set \(F\subseteq\prod_j d_j\) is promised nonempty.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types. Masses satisfy \(\sum_t\mu_t=1\).
Each complete type \(t\) specifies a scope \(S_t\subseteq\{1,\ldots,m\}\) and an explicit table \(u_t:\prod_{j\in S_t}d_j\to\mathbb{Q}\); utilities may have either sign. Find any \(x^*\in\arg\max_{x\in F}\sum_t\mu_tu_t(x_{S_t})\) and report its exact rational welfare.
For the structural parameter, join variables sharing any constraint or utility scope into cliques, and supply a DFS forest of the resulting graph. Define \(w\) as the maximum number of ancestors adjacent to a vertex or any descendant of that vertex. Put \(D=\max_j|d_j|\), and let \(L\) be the total input bit length. State running times in \(m,\tau,L,D,w\).
Is this support-mass welfare optimization problem in \(\mathrm{P}\), or is it NP-hard?
If it is NP-hard, is it FPT parameterized by \(w\) alone, with \(D\) unrestricted?
For finite-agent social choice, DPOP bounds each node’s utility computations and largest utility message by \(O(D^{w+1})\), using the centralized graph’s width; fixed public utility weights are also admitted ([Petcu–Faltings–Parkes](https://doi.org/10.1613/jair.2500)).
General discrete DCOP optimization is NP-hard ([Fioretto et al.](https://arxiv.org/abs/1702.06915)); related CSP is \(\mathrm{W}[1]\)-hard parameterized by primal treewidth with unrestricted domains ([Samer–Szeider](https://www.ac.tuwien.ac.at/files/pub/SamerSzeider10a.pdf)). No source located states the exact support-mass bit-complexity classification asked here.
The problem is NP-hard, even with Boolean domains, no hard constraints, equal positive masses, and utilities taking values in \(\{0,1\}\).
With unrestricted \(D\), it is \(\mathrm{W}[1]\)-hard parameterized by the supplied DFS width \(w\). Consequently, it is not FPT in \(w\) alone unless \(\mathrm{FPT}=\mathrm{W}[1]\).
Nevertheless, an optimizer and its exact rational welfare can be computed in
\(O\!\left(L^3+(m+\tau+L)D^{w+1}L^2\right)\)
bit operations. Thus the problem is in XP parameterized by \(w\), and is FPT parameterized by \((w,D)\).
The proofs below preserve the nonempty-feasibility promise throughout.
Write each mass as \(\mu_t=a_t/b_t\), and each utility-table entry as \(u_t(z)=p_{t,z}/q_{t,z}\), with positive denominators. Define
\(Q=\left(\prod_t b_t\right)\left(\prod_t\prod_{z\in\prod_{j\in S_t}d_j}q_{t,z}\right).\)
Every denominator occurs explicitly in the input. Therefore \(\log_2 Q\leq O(L)\). Moreover, \(b_tq_{t,z}\) divides \(Q\), because its two factors occur separately in the defining product. Consequently,
\(c_t(z)=Q\mu_tu_t(z)=a_tp_{t,z}\,\dfrac{Q}{b_tq_{t,z}}\)
is an integer.
Let \(C(x)=\sum_t c_t(x_{S_t})\). Since \(Q>0\), maximizing \(C(x)\) is equivalent to maximizing welfare, and the exact welfare of any assignment is \(C(x)/Q\).
All relevant integers have \(O(L)\) bits. Indeed, the largest absolute utility entry is at most \(2^{O(L)}\), and for any subset \(I\) of types and any choices of their table entries,
\(\left|\sum_{t\in I}Q\mu_tu_t(z_t)\right|\leq Q\max_{t,z}|u_t(z)|\sum_{t\in I}\mu_t\leq Q\max_{t,z}|u_t(z)|.\)
Here positivity of the masses and \(\sum_t\mu_t=1\) justify the last inequality. This bound also applies to partial sums used by the algorithm.
Using ordinary integer multiplication and division, constructing \(Q\) and all scaled tables takes \(O(L^3)\) bit operations: there are \(O(L)\) explicitly encoded entries, and each operation involves \(O(L)\)-bit integers. No expansion into a finite population is required.
Reduce from the standard NP-complete problem 3-SAT. We may restrict to formulas with at least one variable and one clause, delete tautological clauses and duplicate clauses, and regard each remaining clause as involving at most three distinct variables. The excluded trivial cases are decidable directly, so this restriction retains NP-hardness.
Let the resulting formula have variables \(Y_1,\ldots,Y_m\) and \(q\) clauses.
Construct the welfare instance as follows:
Each utility table has at most eight entries. Distinct non-tautological clauses give distinct complete types: a clause is determined by its scope and its unique falsifying assignment. Thus this is a valid support list with \(\tau=q\).
For every assignment \(x\),
\(\sum_t\mu_tu_t(x_{S_t})=\dfrac{\text{number of clauses satisfied by }x}{q}.\)
It follows that the maximum welfare equals \(1\) if and only if the formula is satisfiable. The construction has polynomial bit length. Its interaction graph and a DFS forest can also be constructed in polynomial time.
Every constructed instance has nonempty \(F\). Therefore an algorithm returning the exact optimum welfare would decide 3-SAT, proving the claimed NP-hardness.
For completeness, the corresponding threshold question—whether some feasible assignment has welfare at least a given binary rational \(K\)—has polynomially verifiable witnesses. One checks the listed constraints and evaluates welfare using exact arithmetic from Section 1. Hence the threshold version is NP-complete, with hardness already holding on promised-feasible instances.
We give a direct parameterized reduction from Clique, avoiding any assumption that hardness for primal treewidth automatically transfers to the supplied DFS parameter.
The source problem asks whether a simple undirected graph \(G=(V,E)\) has a clique of size \(k\), parameterized by \(k\). Its \(\mathrm{W}[1]\)-completeness is a standard theorem, also stated in [Samer–Szeider, Section 1.1](https://www.ac.tuwien.ac.at/files/pub/SamerSzeider10a.pdf). We restrict to \(k\geq2\) and \(n=|V|\geq1\); excluded cases are directly decidable and can be mapped to fixed yes or no instances.
Create \(m=k\) variables, each with domain \(V\), and impose no hard constraints. For each pair \(1\leq i<j\leq k\), create a type with scope \(\{i,j\}\) and table
\(u_{ij}(a,b)=\begin{cases}1,&a\neq b\text{ and }\{a,b\}\in E,\\0,&\text{otherwise}.\end{cases}\)
Set \(\tau=\binom{k}{2}\) and give every type mass \(1/\tau\). All tables are explicitly listed, with \(n^2\) entries each.
Every utility is at most \(1\), so welfare is at most \(1\). Equality holds precisely when every selected pair consists of distinct adjacent vertices. Hence
\(\max_{x\in F}\sum_{i<j}\mu_{ij}u_{ij}(x_i,x_j)=1\quad\Longleftrightarrow\quad G\text{ has a }k\text{-clique}.\)
This remains valid when all entries of some table are zero: the interaction graph is defined by declared scopes. Since every variable pair is a scope, the interaction graph is \(K_k\).
Supply the DFS path \(X_1,X_2,\ldots,X_k\), rooted at \(X_1\). This is a valid DFS tree of \(K_k\). At \(X_i\), every one of its \(i-1\) strict ancestors is adjacent to \(X_i\) itself. Therefore its separator has size \(i-1\), and the supplied width is exactly
\(w=k-1.\)
The output length is at most
\(O\!\left(kn\log(n+1)+k^2n^2\bigl(\log(n+1)+\log(k+1)\bigr)\right).\)
Thus the construction takes \(f(k)n^{O(1)}\) time and bounds the target parameter solely by \(k\). It is an FPT reduction, proving \(\mathrm{W}[1]\)-hardness parameterized by \(w\).
In particular, an optimizer running in \(f(w)L^c\) time, with constant \(c\) independent of \(w\), would yield an FPT algorithm for Clique. The non-FPT conclusion therefore has the usual explicit assumption \(\mathrm{FPT}\neq\mathrm{W}[1]\).
Use the scaled integer tables from Section 1. For a vertex \(v\), let \(T_v\) be the vertices in its DFS subtree, including \(v\), and define
\(A_v=\{a:\ a\text{ is a strict ancestor of }v\text{ and is adjacent to some vertex of }T_v\}.\)
By definition, \(|A_v|\leq w\). Set \(B_v=A_v\cup\{v\}\), so \(|B_v|\leq w+1\).
Every edge of an undirected graph joins comparable vertices in a DFS forest. Indeed, if one endpoint is discovered first, DFS finishes exploring its reachable undiscovered neighbors before returning from it; the other endpoint must therefore become its descendant if it was not already discovered.
This yields three facts needed by the algorithm.
Its vertices form a clique, so every pair is comparable. They therefore lie on one ancestor chain. Assign the constraint or utility to the deepest vertex \(v\). Every other scope vertex is an ancestor adjacent to \(v\), and hence belongs to \(A_v\). The scope is contained in \(B_v\).
An ancestor of \(c\) is either \(v\) or an ancestor of \(v\). In the latter case, adjacency to a vertex of \(T_c\subseteq T_v\) puts it in \(A_v\).
Such an edge would join incomparable vertices. Consequently, no constraint or utility scope meets two different child subtrees.
Empty-scope utilities contribute a constant \(C_0\). Empty-scope constraints can be checked immediately; the feasibility promise ensures they are satisfied.
For an assignment \(s\) to \(B_v\), define \(H_v(s)\) to be the sum of scaled utilities assigned to \(v\), unless a constraint assigned to \(v\) is violated, in which case set \(H_v(s)=-\infty\).
For an assignment \(a\) to \(A_v\), let \(M_v(a)\) be the maximum contribution of utilities whose assigned vertices lie in \(T_v\), over assignments to \(T_v\) satisfying all constraints assigned there, conditional on \(a\). If no such assignment exists, set \(M_v(a)=-\infty\).
This definition needs no additional outside variables. If a scope assigned inside \(T_v\) contains a vertex outside \(T_v\), that vertex is an ancestor of \(v\) adjacent to a vertex of \(T_v\), and thus lies in \(A_v\).
The recurrence is
\(M_v(a)=\max_{b\in d_v}\left[H_v(a\cup\{v\mapsto b\})+\sum_{c\text{ child of }v}M_c\!\left((a\cup\{v\mapsto b\})|_{A_c}\right)\right].\)
Its correctness follows by induction from the leaves. After fixing \(a\) and \(b\), every child message has its required separator assignment because \(A_c\subseteq B_v\). Distinct child subtrees share no variable and participate in no common factor, so their feasible assignments can be chosen independently and their objective contributions add. Conversely, every feasible subtree assignment restricts to such child assignments and satisfies the factors assigned to \(v\). These two directions establish equality in the recurrence.
For the set \(R\) of forest roots, the optimum scaled welfare is
\(C^*=C_0+\sum_{r\in R}M_r(\varnothing).\)
The promise ensures this is finite. Store an attaining value \(b\) for every finite message entry. Starting at the roots and following these choices reconstructs a feasible optimizer \(x^*\). Its exact welfare is \(C^*/Q\), which can be reduced to lowest terms in polynomial time.
Let \(h\) be the number of hard constraints; explicit encoding gives \(h=O(L)\).
At vertex \(v\), the recurrence examines at most \(D^{|B_v|}\leq D^{w+1}\) assignments. Each examination evaluates its locally assigned factors and accesses one message per child. Each factor has exactly one assigned vertex, and the forest has at most \(m-1\) child edges. Therefore the total number of factor evaluations, message accesses, additions, and comparisons is
\(O\!\left((m+\tau+h)D^{w+1}\right).\)
Index domain values and sort the explicit tables for deterministic lookup. Keys and numerical values have \(O(L)\) bits, so each lookup, projection, or arithmetic operation can conservatively be implemented in \(O(L^2)\) bit operations. Graph construction, separator construction, indexing, and integer scaling fit within \(O(L^3)\) preprocessing. This proves the stated bound
\(O\!\left(L^3+(m+\tau+L)D^{w+1}L^2\right).\)
Each message has at most \(D^w\) entries and uses \(O(D^wL)\) bits, including stored maximizing choices.
Because domains are explicitly listed, \(D=O(L)\), and also \(m,\tau=O(L)\). The running time is therefore \(L^{w+O(1)}\), establishing XP in \(w\). For fixed \(D\), it has the form \(f(w)L^{O(1)}\); with both \(w\) and \(D\) parameterized, it has the form \(f(w,D)L^{O(1)}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. Both hardness reductions are valid, the dynamic program uses the supplied DFS width correctly, and the stated bit-operation bound accounts for exact rational arithmetic. I found no major or minor mathematical issues.
The proof treats \(\tau\) as the number of explicitly listed positive-mass types. It does not expand rational masses into a population or assume that all possible types are listed.
Negative utilities are permitted throughout the arithmetic analysis and dynamic program. Restricting utilities to \(\{0,1\}\) in the reductions is legitimate for proving hardness of the general problem.
The conclusion about parameterization by \(w\) alone is appropriately conditional on \(\mathrm{FPT}\neq\mathrm{W}[1]\).
The definition of \(Q\) includes every explicitly encoded mass denominator and utility-entry denominator. Consequently, its bit length is \(O(L)\).
The divisibility assertion \(b_tq_{t,z}\mid Q\) is correct even when the two denominators share prime factors: they occur as separate factors in the product defining \(Q\). Thus every \(c_t(z)\) is an integer, and multiplication by the positive common denominator preserves all welfare comparisons.
The magnitude bound is valid:
\[
\left|\sum_{t\in I}Q\mu_tu_t(z_t)\right|
\leq Q\max_{t,z}|u_t(z)|\sum_{t\in I}\mu_t
\leq Q\max_{t,z}|u_t(z)|.
\]
It uses precisely the promised positivity and normalization of the masses. It also applies to finite dynamic-programming values and their partial sums, since those aggregate contributions from subsets of types. Infeasible values are represented separately by \(-\infty\).
There are \(O(L)\) explicitly encoded rational entries. Ordinary arithmetic on \(O(L)\)-bit integers therefore supports the claimed \(O(L^3)\) preprocessing bound. Reporting and reducing \(C^*/Q\) also has polynomial bit complexity.
The preprocessing of 3-SAT preserves satisfiability. Formulas left with no clauses are directly decidable, so restricting the nontrivial reduction to \(q\geq1\) does not compromise hardness.
Each clause utility has an explicit Boolean table with at most eight entries. After the stated normalization, distinct non-tautological clauses have distinct scopes or distinct falsifying assignments, so the construction genuinely lists \(\tau=q\) distinct complete types.
The masses are positive binary rationals and sum to \(1\). For every assignment, welfare is exactly the fraction of satisfied clauses. Hence optimum welfare equals \(1\) exactly for satisfiable formulas.
There are no hard constraints, so every constructed instance satisfies the nonempty-feasibility promise. Constructing the interaction graph and a DFS forest takes polynomial time.
The threshold membership claim is also justified: a complete assignment is a polynomial-size witness, explicit allowed tables can be checked in polynomial time, and welfare can be evaluated and compared with the rational threshold exactly. Thus the stated threshold NP-completeness conclusion is supported.
The source theorem is stated precisely enough for this use: Clique, parameterized by requested clique size \(k\), is \(\mathrm{W}[1]\)-complete. The cited [Samer–Szeider paper, Section 1.1](https://www.ac.tuwien.ac.at/files/pub/SamerSzeider10a.pdf) explicitly states this theorem.
For \(k\geq2\) and \(n\geq1\), the construction has nonempty domains and positive normalized masses. Every pair utility is at most \(1\), so welfare reaches \(1\) exactly when all selected vertices are pairwise distinct and adjacent. This is precisely a \(k\)-clique. The same equivalence holds when \(k>n\), in which case neither condition can hold.
Types for different variable pairs are distinct because their declared scopes differ, including when their numerical tables are identical.
The interaction graph is \(K_k\), regardless of whether some utilities are identically zero. The supplied path is a valid DFS tree. At its \(i\)-th vertex, the separator contains exactly its \(i-1\) strict ancestors, giving \(w=k-1\).
The explicit table sizes and displayed output-length bound are consistent with \(f(k)n^{O(1)}\) construction time. The target parameter depends only on \(k\). Consequently, the parameterized hardness claim and the conditional exclusion of an \(f(w)L^c\)-time optimizer follow.
The proof correctly uses the undirected DFS property that every graph edge joins ancestor-comparable vertices.
Since each scope induces a clique, every nonempty scope lies on one ancestor chain and has a unique deepest vertex. Assigning the factor there puts its entire scope inside \(B_v\).
The inclusion \(A_c\subseteq B_v\) follows from the ancestor relation and \(T_c\subseteq T_v\). Distinct child subtrees have no edges between them, so no declared factor can intersect two such subtrees.
Empty scopes are handled correctly: utilities contribute constants, and the feasibility promise excludes an unsatisfied empty-scope constraint. Singleton scopes, isolated vertices, and multiple forest roots are covered by the same definitions.
The definition of \(M_v(a)\) conditions on all outside variables that can appear in factors assigned within \(T_v\). The proof correctly establishes that these variables belong to \(A_v\).
Once \(a\) and the value of \(v\) are fixed, every child receives a complete separator assignment. Child subproblems have disjoint remaining variables and no shared factors, so their feasible assignments combine independently.
The two directions of the recurrence justification are present: every feasible subtree assignment yields admissible child assignments, and admissible child assignments combine with satisfied local factors into a feasible subtree assignment. This validates the induction, including leaves and infeasible separator assignments.
Root components combine independently. The feasibility promise ensures their optimum messages are finite. Stored maximizing choices reconstruct a feasible assignment attaining \(C^*\), and \(C^*/Q\) is its exact welfare.
Each vertex examines at most \(D^{w+1}\) assignments. Each nonempty factor is assigned once, and each child edge contributes one message access per examined assignment at its parent. Summing these costs gives the stated
\[
O\!\left((m+\tau+h)D^{w+1}\right)
\]
operation count.
With explicit tables and domain indexing, the conservative \(O(L^2)\) bit cost per lookup, projection, arithmetic operation, or comparison is sufficient. Graph construction, separators, table indexing, scaling, and the remaining polynomial overhead fit within \(O(L^3)\). Thus the claimed bound
\[
O\!\left(L^3+(m+\tau+L)D^{w+1}L^2\right)
\]
is supported.
The message-size bound \(O(D^wL)\) includes the integer values and stored choices. Explicit encoding gives \(D,m,\tau=O(L)\), yielding XP in \(w\), and the displayed runtime yields FPT in \((w,D)\).
No additional clarification is needed to verify the mathematical classification or the algorithmic bounds.
⟨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.