A Tractable Class of Binary VCSPs via M-Convex Intersection
A Tractable Class of Binary VCSPs via M-Convex Intersection
复制标题
基于M-凸交集的一类可处理的二元VCSP
DOI：
10.1145/3329862
复制
发表时间：
2019
影响因子：
1.3
通讯作者：
Zivny Stanislav
中科院分区：
文献类型：
--
作者：
Hirai Hiroshi;Iwamasa Yuni;Murota Kazuo;Zivny Stanislav
人们对结构限制下（无限数量）Max-CSP 的复杂性知之甚少。已知可确保 Max-CSP 的可处理性的两个最通用的超图属性，β-无环性和有界（关联）MIM 宽度，是不可比较的，并导致截然不同的算法。我们引入超图的点分解框架，并使用它导出（结构限制的）Max-CSP 的可处理性的新充分条件，该条件概括了有界 MIM 宽度 和β-无环性。在此过程中，我们给出了有界 MIM 宽度的新表征，并讨论了与 Max-CSP 复杂性相关的其他超图属性，例如β-超树宽度。
The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs,β-acyclicity and bounded (incidence) MIM-width, are incomparable and lead to very different algorithms.We introduce the framework of point decompositions for hypergraphs and use it to derive a new sufficient condition for the tractability of (structurally restricted) Max-CSPs, which generalises both bounded MIM-width andβ-acyclicity. On the way, we give a new characterisation of bounded MIM-width and discuss other hypergraph properties which are relevant to the complexity of Max-CSPs, such asβ-hypertreewidth.