Toward a Dichotomy for Approximation of $H$-coloring

Akbar Rafiey, Arash Rafiey, Thiago Santos

Given two (di)graphs G, H and a cost function $c:V(G)\times V(H)\to {\mathbb{Q}}_{\ge 0}\cup \{+\infty \}$, in the minimum cost homomorphism problem, MinHOM(H), goal is finding a hom…