The Complexity of 3-Colouring H-Colourable Graphs
The Complexity of 3-Colouring H-Colourable Graphs
复制标题
三色 H 可色图的复杂性
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Jakub Opršal
中科院分区：
文献类型：
--
作者：
A. Krokhin;Jakub Opršal
我们研究图同态问题的可满足实例近似的复杂性。对于固定图 H，H 着色问题是确定给定图是否与 H 同态。根据 Hell 和 Nešetřil 的结果，这个问题对于任何非二分图 H 来说都是 NP 困难的。在承诺约束满足问题的背景下，Brakensiek 和 Guruswami 推测这个硬度结果扩展到承诺图同态，如下所示：修复任何非二分图 H 和另一个图 G 从 H 到 G 的同态，从给定的 H 可着色图中找到 G 的同态是 NP 困难的。可以说，这个猜想的两个最重要的特殊情况是当 H 固定为 3 个顶点上的完全图时（并且 G 是任何具有三角形的图）以及当 G 是 3 个顶点上的完全图时（并且 H 是任何 3 色图）。前一种情况相当于众所周知的困难的近似图着色问题。在本文中，我们证实了后一种情况的 Brakensiek-Guruswami 猜想。我们的证明依赖于保证约束满足的通用代数方法的新颖组合，该方法是由 Barto、Bulín 和作者最近开发的，并结合了代数拓扑的一些想法。
We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite graph H. In the context of promise constraint satisfaction problems, Brakensiek and Guruswami conjectured that this hardness result extends to promise graph homomorphism as follows: fix any non-bipartite graph H and another graph G with a homomorphism from H to G, it is NP-hard to find a homomorphism to G from a given H-colourable graph. Arguably, the two most important special cases of this conjecture are when H is fixed to be the complete graph on 3 vertices (and G is any graph with a triangle) and when G is the complete graph on 3 vertices (and H is any 3-colourable graph). The former case is equivalent to the notoriously difficult approximate graph colouring problem. In this paper, we confirm the Brakensiek-Guruswami conjecture for the latter case. Our proofs rely on a novel combination of the universal-algebraic approach to promise constraint satisfaction, that was recently developed by Barto, Bulín and the authors, with some ideas from algebraic topology.
DOI：
--
发表时间：
2017
期刊：
--
影响因子：
--
作者：
A. Krokhin;Stanislav Živný
通讯作者：
A. Krokhin;Stanislav Živný
影响因子：
1.3
作者：
Brakensiek, Joshua;Guruswami, Venkatesan
通讯作者：
Guruswami, Venkatesan
DOI：
10.1145/3313276.3316300
发表时间：
2019
期刊：
--
影响因子：
--
作者：
Bulín J
通讯作者：
Bulín J