  For graphs $G$ and $H$, a mapping $f: V(G)\dom 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 {\em minimum cost homomorphism problem}, written as MinHOM($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. Minimum cost homomorphism problems
encompass (or are related to) many well studied optimization problems. We
describe a dichotomy of the minimum cost homomorphism problems for graphs $H$,
with loops allowed. When each connected component of $H$ 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.
Along the way, we prove a new characterization of the class of proper interval
bigraphs.
