August 13, 2025Open Access

Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints

Key Points

Weighted min sat for any Boolean constraint language is either fixed-parameter tractable or W[1]-hard, revealing fundamental complexity differences.
The results build on previous works by generalizing dichotomies for both weighted and unweighted constraint satisfaction problems.
The main technique used is flow-augmentation, a method that has shown promising results in handling constraint optimization problems.
This study provides insights for both theoretical advancements and practical applications in solving computational problems.

Abstract

. 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

Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints

Key Points

Abstract

Cite This Study

Also Consider

Also Consider