A dichotomy for minimum cost graph homomorphisms (Q2427539)

Let \(G\) and \(H\) be two finite graphs with vertex sets \(V(G)\) and \(V(H)\), respectively. The authors consider graph homomorphisms \(f: G \to H\). Mapping a vertex \(u \in V(G)\) to a vertex \(i \in V(H)\) incurs a cost \(c_i(u)\). The minimum cost homomorphism problem consists in finding a homomorphism such that the sum of incurred costs is minimum. A graph where every vertex has a loop is called reflexive, a graph without loops is called irreflexive. The authors show that the minimum cost homomorphism problem is polynomial time solvable if each connected component of \(H\) is either a reflexive or an irreflexive proper interval graph. In all other cases the problem in NP-hard. This solves an open question raised in [\textit{G. Gutin, A. Rafiey, A. Yeo} and \textit{M. Tso}, Discrete Appl. Maths. 154, 890--897 (2006; Zbl 1138.05032)].