For digraphs D and H, a homomorphism of D to H
is a mapping f : V(D)->V(H) such that uv in A(D)
implies f(u)f(v) in A(H). Suppose D and H are two
digraphs, and c_i(u), u in V (D), i in V (H), are nonnegative
real costs. The cost of the homomorphism
f of D to H is \Sigma_u in V (D) cf(u)(u). The minimum
cost homomorphism for a fixed digraph H, denoted
by MinHOM(H), asks whether or not an input digraph
D, with nonnegative real costs ci(u), u in V(D),
i in V(H), admits a homomorphism f to H and if it
admits one, find a homomorphism of minimum cost.
The minimum cost homomorphism problem seems
to offer a natural and practical way to model many optimization
problems such as list homomorphism problems,
retraction and precolouring extension problems,
chromatic partition optimization, and applied problems
in repair analysis.
Our interest is in proving a dichotomy for minimum
cost homomorphism problem: we would like
to prove that for each digraph H, MinHOM(H) is
polynomial-time solvable, or NP-hard. We say that
H is a digraph with some loops, if H has at least one
loop. For reflexive digraphs H (every vertex has a
loop) the complexity of MinHOM(H) is well understood.
In this paper, we obtain a full dichotomy for
MinHOM(H) when H is an oriented cycle with some
loops. Furthermore, we show that this dichotomy is a
remarkable progress toward a dichotomy for oriented
graphs with some loops.