Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2207.07422 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909586736283648 |
|---|---|
| author | Kim, Eun Jung Kratsch, Stefan Pilipczuk, Marcin Wahlström, Magnus |
| author_facet | Kim, Eun Jung Kratsch, Stefan Pilipczuk, Marcin Wahlström, Magnus |
| contents | 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 $α\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$(Γ$), 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 $α$ 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 \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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_07422 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | 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 Computational Complexity Data Structures and Algorithms 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 $α\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$(Γ$), 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 $α$ 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 \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). |
| title | Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2207.07422 |