A six-cycle mapped to a two-value template illustrates a feasible homomorphism. Minimum cost homomorphism adds a cost to each variable–value choice and seeks the least expensive assignment that preserves every constraint. Research source
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.
Citation
BibTeX
@inproceedings{takhanov2010minimumcosthomomorphism,
title = {A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem},
author = {Takhanov, Rustem},
year = {2010},
booktitle = {STACS 2010},
eprint = {0708.3226},
archivePrefix = {arXiv},
url = {https://arxiv.org/pdf/0708.3226}
}