  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).
