Parameterized Approximation of Max k-Weight CSP: A Dichotomy for Boolean Languages
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
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles