Topology and Adjunction in Promise Constraint Satisfaction
Topology and Adjunction in Promise Constraint Satisfaction
复制标题
承诺约束满足中的拓扑和附加
DOI：
10.1137/20m1378223
复制
发表时间：
2023
影响因子：
1.6
通讯作者：
Krokhin A
中科院分区：
文献类型：
--
作者：
Krokhin A
图的近似着色问题，其复杂性在大多数情况下是未解决的，涉及到找到一个图的a-着色，保证是可着色的，其中。这个问题自然地推广到承诺图同态问题，并进一步承诺约束满足问题。这些问题的复杂性最近已经通过代数方法进行了研究。本文介绍了两种分析Promise CSP复杂性的新方法：一种是基于拓扑的方法，另一种是基于邻接的方法。我们应用这些技术，再加上以前介绍的代数方法，获得新的无条件NP-硬度结果的一个重要类的近似图着色和承诺图同态问题。
The approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a-coloring of a graph that is promised to be-colorable, where. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems.