Correspondence Homomorphisms to Reflexive Graphs

Correspondence homomorphisms are a common generalization of homomorphisms and of correspondence colourings. For a fixed reflexive target graph H, the problem is to decide whether an input graph G, with each edge labeled by a pair of permutations of V(H), admits a homomorphism to H 'corresponding' to the labels. We classify the complexity of this problem as a function of H. It turns out that there is dichotomy-each of the problems is polynomial or NP-complete. While most graphs H yield NP-complete problems, there is an interesting polynomial case when the problem can be solved by Gaussian elimination. We also classify the complexity of the analogous correspondence list homomorphism problems.