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

We study the parameterized problem of satisfying “almost all” constraints of a given formula F over a fixed, finite Boolean constraint language Γ, with or without weights. More precisely, for each finite Boolean constraint language Γ, we consider the following two problems. In MIN SAT(T), the input is a formula F over Γ and an integer k, and the task is to find an assignment α : V(F) → 0,1 that satisfies all but at most k constraints of F, or determine that no such assignment exists. In WEIGHTED MIN SAT(Γ), the input additionally contains a weight function ω : F → ℤ+ and an integer W, and the task is to find an assignment α such that (1) α 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 Γ, either WEIGHTED MIN SAT(Γ) is FPT; or WEIGHTED MIN SAT(Γ) is W[1]-hard but MIN SAT(Γ) is FPT; or MIN SAT (Γ) is W[1]-hard. This generalizes recent work of Kim et al. (SODA 2021) which did not consider weighted problems, and only considered languages Γ that cannot express implications (u → 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 ℓ-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). * This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (M. Pilipczuk). Eun Jung Kim is supported by the grant from French National Research Agency under JCJC program (ASSK: ANR-18-CE40-0025-01). The full version of the paper can be accessed at https://arxiv.org/abs/2207.07422.