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

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1

We study the parameterized problem of satisfying ``almost all'' constraints of a given formula $F$ over a fixed, finite Boolean constraint language $\hat{I}“$, with or without weights. M…