2024/10/24 by Aditya Anand, Euiwoong Lee, Anand, Aditya +2 · 1 citation
Computer Science · #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2410.19066
Given a fixed arity k ≥ 2, Min-k-CSP on complete instances involves a set of n variables V and one nontrivial constraint for every k-subset of variables (so there are \binomnk constraints). The goal is to find an assignment that minimizes unsatisfied constraints. Unlike Max-k-CSP that admits a PTAS on dense or expanding instances, the approximability of Min-k-CSP is less understood. For some CSPs like Min-k-SAT, there's an approximation-preserving reduction from general to dense instances, making complete instances unique for potential new techniques. This paper initiates a study of Min-k-CSPs on complete instances. We present an O(1)-approximation algorithm for Min-2-SAT on complete instances, the minimization version of Max-2-SAT. Since O(1)-approximation on dense or expanding instances refutes the Unique Games Conjecture, it shows a strict separation between complete and dense/expanding instances. Then we study the decision versions of CSPs, aiming to satisfy all constraints; which is necessary for any nontrivial approximation. Our second main result is a quasi-polynomial time algorithm for every Boolean k-CSP on complete instances, including k-SAT. We provide additional algorithmic and hardness results for CSPs with larger alphabets, characterizing (arity, alphabet size) pairs that admit a quasi-polynomial time algorithm on complete instances.