Parameterized Approximation of Max k-Weight CSP: A Dichotomy for Boolean Languages

We study {Max k-Weight CSP}: maximize the satisfied weight of Boolean constraints with nonnegative rational weights by setting at most k variables to $1$. Each constraint uses at most d distinct variables and a relation from a finite Boolean language $Γ$. This includes {Partial Vertex Cover}, {Densest k-Subgraph}, bounded-frequency {Maximum Coverage}, and cardinality-constrained {Max-SAT}. We completely classify the fixed finite languages admitting an efficient parameterized approximation scheme (EPAS) with parameter $k+d$. Only nonempty relations excluding the all-zero tuple matter. For such a relation, a coordinate is a unit witness if the tuple with a single $1$ in that coordinate is accepted, and a control otherwise. A relation is Direct if setting any selected control to $0$, with all other coordinates unchanged, preserves satisfaction. It is Rooted if every satisfying tuple has a selected unit witness such that keeping it, setting all other unit witnesses to $0$, and setting any subset of selected controls to $0$ preserves satisfaction. If all such relations are Direct, or all are Rooted, we give a deterministic (1-ε)-approximation for every rational ε∈(0,1) in time 2O(d+klog(1+dk/ε))ᵢₙO(1), where ᵢₙ is the total input length. The algorithms are uniform in d and give an EPAS parameterized by $k+d$ whenever relation membership is polynomial-time decidable. If neither condition holds, no EPAS exists unless FPT=W[1], even for unweighted instances where no two constraints involve the same set of variables.