. 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 (\ (\) ), 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 \ (w F Z_+\) 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 \ (W1\) -hard but Min SAT (\ (\) ) is \ (FPT\) ; or Min SAT (\ (\) ) is \ (W1\) -hard. This generalizes recent work of Kim et al. in SODA 2021, SIAM, Philadelphia, 2021, pp. 149–168, 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 E. J. Kim et al. , in STOC 2022, ACM, 2022, pp. 938–947. Keywordsflow-augmentationconstraint satisfaction problemsfixed-parameter tractabilityMSC codes68Q1768Q2568Q2768W40
Kim et al. (Wed,) studied this question.