2005/09/28 by G. Gutin, Gregory Gutin, Arash Rafiey +6 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.DM #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.cs/0509091
arxiv created 2005/09/28 · openalex publication_date 2005/09/28 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For digraphs D and H, a mapping f: V(D)\dom V(H) is a \em homomorphism of D to H if uv∈ A(D) implies f(u)f(v)∈ A(H). For a fixed directed or undirected graph H and an input graph D, the problem of verifying whether there exists a homomorphism of D to H has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced very recently by the authors and M. Tso. Suppose we are given a pair of digraphs D,H and a positive integral cost ci(u) for each u∈ V(D) and i∈ V(H). The cost of a homomorphism f of D to H is ∑u∈ V(D)cf(u)(u). Let H be a fixed digraph. The minimum cost homomorphism problem for H, MinHOMP(H), is stated as follows: For input digraph D and costs ci(u) for each u∈ V(D) and i∈ V(H), verify whether there is a homomorphism of D to H and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of \MiP for H being a semicomplete digraph. In this paper we extend the classification to semicomplete k-partite digraphs, k≥ 3, and obtain such a classification for bipartite tournaments.