A dichotomy for minimum cost graph homomorphisms

For graphs GG and HH, a mapping f:V(G)→V(H) is a homomorphism of GG to HH if uv∈E(G)uv∈E(G) implies f(u)f(v)∈E(H)f(u)f(v)∈E(H). If, moreover, each vertex u∈V(G)u∈V(G) is associated with costs ci(u),i∈V(H)ci(u),i∈V(H), then the cost of the homomorphism ff is ∑u∈V(G)cf(u)(u)∑u∈V(G)cf(u)(u). For each fixed graph HH, we have the minimum cost homomorphism problem  , written as MinHOM(H). The problem is to decide, for an input graph GG with costs ci(u),u∈V(G),i∈V(H)ci(u),u∈V(G),i∈V(H), whether there exists a homomorphism of GG to HH and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well-studied optimization problems. We prove a dichotomy of the minimum cost homomorphism problems for graphs HH, with loops allowed. When each connected component of HH is either a reflexive proper interval graph or an irreflexive proper interval bigraph, the problem MinHOM(H) is polynomial time solvable. In all other cases the problem MinHOM(H) is NP-hard. This solves an open problem from an earlier paper.