首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:The complexity of 3-colouring H -colourable graphs
  • 本地全文:下载
  • 作者:Andrei Krokhin ; Jakub Opršal
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-24
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 K 3 (and G is any graph with a triangle) and when G = K 3 (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 Bulín and the authors, with some ideas from algebraic topology.

  • 关键词:constraint satisfaction ; graph homomorphism ; promise problems
国家哲学社会科学文献中心版权所有