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

arXiv:2610.39751 · cs.DS · Submitted 2026-10-29 · Read on arXiv

cs.DS

Submitted: 2026-10-29

Updated: 2026-10-29

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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.

Abstract

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-epsilon) -approximation for every rational epsilon in(0,1) in time 2 O(d+k (1+dk/epsilon)) in O(1), where in 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 =, even for unweighted instances where no two constraints involve the same set of variables.

Related papers