2007/12/05 by A. Gupta, Arvind Gupta, Gupta, A. +12
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Finite Group Theory Research #Limits and Structures in Graph Theory #cs.DM
paper · pdf · doi:10.48550/arxiv.0712.0804
arxiv created 2007/12/05 · openalex publication_date 2007/12/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For digraphs G and H, a homomorphism of G to H is a mapping f: V(G)\dom V(H) such that uv∈ A(G) implies f(u)f(v)∈ A(H). If, moreover, each vertex u ∈ V(G) is associated with costs ci(u), i ∈ V(H), then the cost of a homomorphism f is ∑u∈ V(G)cf(u)(u). For each fixed digraph H, the minimum cost homomorphism problem for H, denoted MinHOM(H), can be formulated as follows: Given an input digraph G, together with costs ci(u), u∈ V(G), i∈ V(H), decide 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 such as the minimum cost chromatic partition and repair analysis problems. We focus on the minimum cost homomorphism problem for locally semicomplete digraphs and quasi-transitive digraphs which are two well-known generalizations of tournaments. Using graph-theoretic characterization results for the two digraph classes, we obtain a full dichotomy classification of the complexity of minimum cost homomorphism problems for both classes.