论文标题
承诺限制满意度的拓扑和邻接
Topology and adjunction in promise constraint satisfaction
论文作者
论文摘要
在大多数情况下，其复杂性尚未解决，涉及到$ c $颜色的图形颜色，该图的复杂性尚未解决，该图被保证为$ k $ - 颜色，其中$ c \ geq k $。这个问题自然而然地承诺图形同态问题，并进一步保证限制满意度问题。这些问题的复杂性最近通过代数方法研究了。在本文中，我们介绍了两种新技术来分析Promise CSP的复杂性：一个是基于拓扑结构，另一个基于辅助。我们将这些技术与先前引入的代数方法一起应用，以获得一类重要类别的近似图颜色的新无条件的NP硬度结果，并承诺图形同构问题。
The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a $c$-colouring of a graph that is promised to be $k$-colourable, where $c\geq k$. This problem naturally generalises 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 analyse 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 colouring and promise graph homomorphism problems.
