About this paper

An algebraic classification of the computational complexity of the general minimum cost homomorphism problem.

The problem combines constraint satisfaction with costs for assigning values to variables. Algebraic methods identify the boundary between tractable cases and NP-hard cases, settling a general dichotomy conjecture.