2006/02/10 by Gregory Gutin, G. Gutin, P. Hell +9
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.AI #cs.DM
paper · pdf · doi:10.48550/arxiv.cs/0602038
openalex publication_date 2006/02/10 · arxiv created 2006/02/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For graphs G and H, a mapping f: V(G)\dom V(H) is a homomorphism of G to H if uv∈ E(G) implies f(u)f(v)∈ E(H). If, moreover, each vertex u ∈ V(G) is associated with costs ci(u), i ∈ V(H), then the cost of the homomorphism f is ∑u∈ V(G)cf(u)(u). For each fixed graph H, we have the \em minimum cost homomorphism problem, written as MinHOM(H). The problem is to decide, for an input graph G with costs ci(u), u ∈ V(G), i∈ V(H), whether there exists a homomorphism of G to H and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well studied optimization problems. We describe a dichotomy of the minimum cost homomorphism problems for graphs H, with loops allowed. When each connected component of H is either a reflexive proper interval graph or an irreflexive proper interval bigraph, the problem MinHOM(H) is polynomial time solvable. In all other cases the problem MinHOM(H) is NP-hard. This solves an open problem from an earlier paper. Along the way, we prove a new characterization of the class of proper interval bigraphs.