The complexity of 3-colouring $H$-colourable graphs

Abstract

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.

arXiv commentTo appear in FOCS 2019

References in corpus (2)

• Algebraic approach to promise constraint satisfaction
• Improved hardness for H-colourings of G-colourable graphs

Cited by in corpus (9)

• Algebraic approach to promise constraint satisfaction
• The complexity of promise SAT on non-Boolean domains
• Improved hardness for H-colourings of G-colourable graphs
• CLAP: A New Algorithm for Promise CSPs
• Conditional Dichotomy of Boolean Ordered Promise CSPs
• Local consistency as a reduction between constraint satisfaction problems
• Beyond PCSP (1-in-3,NAE)
• Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
• Injective hardness condition for PCSPs