论文标题

流程授权III:布尔CSP的复杂性二分法参数,由不满意的约束数量

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

论文摘要

我们研究了在固定的有限布尔约束语言$γ$中,给定公式$ f $的参数化问题,具有或没有权重。更确切地说,对于每种有限的布尔约束语言$γ$,我们考虑以下两个问题。在Min Sat $(γ)$中,输入是$γ$的公式$ f $和一个整数$ k $,其任务是找到一个任务$α\ colon v(f)\ to \ {0,1 \} $,但最满足所有满足$ f $的$ k $约束,或确定没有此类$ f $的$ k $约束。在加权最小的SAT $(γ$)中,输入还包含一个权重函数$ w \ colon f \ to \ mathbb {z} _+$和一个整数$ w $,而任务是找到一项任务$α$,这样(1)$α$最多可满足$ f $ f $ f $ f $和(2)的约束。我们为这些问题的固定参数障碍提供了完整的二分法:我们表明,对于每种布尔约束语言$γ$,加权的min sat $(γ)$都是fpt;或加权的最小SAT $(γ)$是w [1] - hard,但最小sat $(γ)$是fpt;或min sat $(γ)$是w [1] -hard。这概括了Kim等人的最新工作。 (SODA 2021)不考虑加权问题,并且仅考虑了无法表达含义$(u \ to V)$的语言$γ$(如使用模型Digraph削减问题)。我们的结果概括并包含多个先前的结果,包括加权的FPT算法,几乎是2个sat,加权且未加权的$ \ ell $链链,以及耦合的min-cut,以及后者的加权和定向版本。我们算法中使用的主要工具是最近开发的定向流动效能方法(Kim等,STOC 2022)。

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

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源