Minimum cost homomorphisms to semicomplete multipartite digraphs

For digraphs D and H, a mapping f : V (D) → V (H) is a homomorphism ofD toH if u v ∈ 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 recently by the authors and M. Tso. Suppose we are given a pair of digraphs D, H and a cost c_i (u) for each u ∈ V (D) and i ∈ V (H). The cost of a homomorphism f of D to H is ∑_{u ∈ V (D)} c_{f (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 c_i (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 MinHOMP (H)when H is 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.