A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem

Rustem Takhanov
In the constraint satisfaction problem ($CSP$), the aim is to find an assignment of values to a set of variables subject to specified constraints. In the minimum cost homomorphism problem ($MinHom$), one is additionally given weights $c_{va}$ for every variable $v$ and value $a$, and the aim is to find an assignment $f$ to the variables that minimizes $\sum_{v} c_{vf(v)}$. Let $MinHom\left( \Gamma \right)$ denote the $MinHom$ problem parameterized by the set of predicates allowed...