For graphs G and H, a mapping f: V(G) -> V(H) is a
homomorphism of G to H if uv in E(G) implies f(u)f(v) in E(H). If,
moreover, each vertex u in V(G) is associated with costs c_i(u), i in
V(H), then the cost of the homomorphism f is \sum_{u in
V(G)}c_{f(u)}(u). For each fixed graph H, we have the minimum cost
homomorphism problem, written as MinHOMP(H). The problem is to decide,
for an input graph G with costs c_i(u), u in V(G), i in V(H),
whether there exists a homomorphism of G to H and, if one exists, to
find one of minimum cost.
The minimum cost homomorphism problem generalises as diverse problems as
chromatic numbers, maximum independent set, list
homomorphism, and many more. We will also give some other motivation why
this is an interesting problem, such as applications in military
logistics. We will then discuss a dichotomy of the minimum cost
homomorphism problems for graphs H, with and without loops allowed. In
fact if each connected component of H is either a reflexive proper
interval graph or an irreflexive proper interval bigraph, then the
MinHOMP(H) is polynomial time solvable. In all other cases the
MinHOMP(H) is NP-hard.
We will also state and discuss results for minimum cost homomorphisms in
directed graphs. No dichotomy is yet known for directed graphs, but
several partial results are known. We finally state some open problems.