Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2023), Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints, in Nikhil Bansal, Viswanath Nagarajan, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM - Society for Industrial and Applied Mathematics : Philadelphia, p. 3218-3228. 10.1137/1.9781611977554.ch122
Type
Communication / ConférenceExternal document link
https://arxiv.org/abs/2207.07422Date
2023Conference title
elsevierConference date
2023Conference city
PhiladelphiaConference country
ITALYBook title
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Book author
Nikhil Bansal, Viswanath NagarajanPublisher
SIAM - Society for Industrial and Applied Mathematics
Published in
Philadelphia
Pages
3218-3228
Publication identifier
Metadata
Show full item recordAbstract (EN)
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).Subjects / Keywords
Computational Complexity; Data Structures and AlgorithmsRelated items
Showing items related by title and author.
-
Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2023) Communication / Conférence
-
Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2021) Communication / Conférence
-
Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2022) Communication / Conférence
-
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017) Article accepté pour publication ou publié
-
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2015) Communication / Conférence