Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints

Download PDF

We study the parameterized problem of satisfying ``almost all'' constraints of a given formula F over a fixed, finite Boolean constraint language \Gamma, with or without weights. More precisely, for each finite Boolean constraint language \Gamma, we consider the following two problems. In Min SAT(\Gamma), the input is a formula F over \Gamma and an integer k, and the task is to find an assignment \alpha \colon V(F) \to \{0,1\} that satisfies all but at most k constraints of F, or determine that no such assignment exists. In Weighted Min SAT(\Gamma), the input additionally contains a weight function w \colon F \to \mathbb{Z}_+ and an integer W, and the task is to find an assignment \alpha such that (1) \alpha satisfies all but at most k constraints of F, and (2) the total weight of the violated constraints is at most W. We give a complete dichotomy for the fixed-parameter tractability of these problems: We show that for every Boolean constraint language \Gamma, either Weighted Min SAT(\Gamma) is FPT; or Weighted Min SAT(\Gamma) is W[1]-hard but Min SAT(\Gamma) is FPT; or Min SAT(\Gamma) is W[1]-hard. This generalizes recent work of Kim et al. (SODA 2021) which did not consider weighted problems, and only considered languages \Gamma that cannot express implications (u \to v) (as is used to, e.g., model digraph cut problems). Our result generalizes and subsumes multiple previous results, including the FPT algorithms for Weighted Almost 2-SAT, weighted and unweighted \ell-Chain SAT, and Coupled Min-Cut, as well as weighted and directed versions of the latter. The main tool used in our algorithms is the recently developed method of directed flow-augmentation (Kim et al., STOC 2022).