The Complexity of Boolean Surjective General-Valued CSPs
The Complexity of Boolean Surjective General-Valued CSPs
复制标题
布尔满射通用值 CSP 的复杂性
DOI：
10.1145/3282429
复制
发表时间：
2018
影响因子：
0.7
通讯作者：
Zivny Stanislav
中科院分区：
文献类型：
--
作者：
Fulla Peter;Uppman Hannes;Zivny Stanislav
有值约束满足问题（VCSPs）是具有（Q∪{∞}）值目标函数作为定值函数和的离散优化问题。在布尔满射vcsp中，变量采用frommd ={0,1}的标签，并且需要使用来自md的两个标签进行最优分配。例子包括图中的经典全局最小割问题和编码理论中研究的最小距离问题。我们建立了一个二分定理，从而给出了布尔满射vcsp关于精确可解的完全复杂度分类。我们的工作推广了由Creignou和hsambrard得到的{0，∞}值约束语言（对应于满射决策csp）的二分法。对于Q≥0值满射vcsp的最大化问题，我们还建立了关于逼近性的二分定理。与布尔满射（决策）csp的情况不同，出现了一种新的可处理的语言类别，它在非满射设置中是微不足道的。这个新发现的易于处理的类有一个有趣的数学结构，与低落和沮丧有关。我们的主要贡献是确定这类并证明它位于可处理性的边缘。我们证明的关键部分是一个多项式时间算法，用于枚举广义最小切问题的所有近最优解，这可能是独立的兴趣。
Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a (Q ∪ {∞ })-valued objective function given as a sum of fixed-arity functions. In Boolean surjective VCSPs, variables take on labels fromD= {0,1}, and an optimal assignment is required to use both labels fromD. Examples include the classicalglobal Min-Cutproblem in graphs and theMinimum Distanceproblem studied in coding theory.We establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs with respect to exact solvability. Our work generalises the dichotomy for {0, ∞}-valued constraint languages (corresponding to surjective decision CSPs) obtained by Creignou and Hébrard. For the maximisation problem of Q≥0-valued surjective VCSPs, we also establish a dichotomy theorem with respect to approximability.Unlike in the case of Boolean surjective (decision) CSPs, there appears a novel tractable class of languages that is trivial in the non-surjective setting. This newly discovered tractable class has an interesting mathematical structure related to downsets and upsets. Our main contribution is identifying this class and proving that it lies on the borderline of tractability. A crucial part of our proof is a polynomial-time algorithm for enumerating all near-optimal solutions to a generalised Min-Cut problem, which might be of independent interest.