  In a valued constraint satisfaction problem (VCSP), the goal is to find an
assignment of labels to variables that minimizes a given sum of functions. Each
function in the sum depends on a subset of variables, takes values which are
rational numbers or infinity, and is chosen from a fixed finite set of
functions called a constraint language. The case when all functions take only
values 0 and infinity is known as the constraint satisfaction problem (CSP). It
is known that any CSP with fixed constraint language is polynomial-time
equivalent to one where the constraint language contains a single binary
relation (i.e. a digraph). A recent proof of this by Bulin et al. gives such a
reduction that preserves most of the algebraic properties of the constraint
language that are known to characterize the complexity of the corresponding
CSP. We adapt this proof to the more general setting of VCSP to show that each
VCSP with a fixed finite (valued) constraint language is equivalent to one
where the constraint language consists of one $\{0,\infty\}$-valued binary
function (i.e. a digraph) and one finite-valued unary function, the latter
problem known as the (extended) Minimum Cost Homomorphism Problem for digraphs.
We also show that our reduction preserves some important algebraic properties
of the (valued) constraint language.
