Complexity of correspondence H-colourings

Abstract Correspondence homomorphisms generalize standard homomorphisms as well as correspondence colourings (also known as DP-colourings). For a fixed target graph H , we study the problem of deciding whether an input graph G , with each edge labelled by a pair of permutations of V ( H ) , admits a homomorphism to H ‘corresponding’ to the labels. Homomorphisms to H are called H -colourings, and we employ the similar term correspondence H -colourings for correspondence homomorphisms to H . We classify the complexity of this problem as a function of the fixed graph H . It turns out that there is dichotomy — each of the problems is polynomial-time solvable or NP-complete. While most graphs H yield NP-complete problems, there are interesting cases of graphs H for which the problem can be solved in polynomial time by Gaussian elimination. We also classify the complexity of the analogous correspondence list homomorphism problems, and also the complexity of a bipartite version of both problems. We give detailed proofs for the case when H is reflexive, and, for the record, sketch the remaining proofs.