Minimum cost homomorphisms to semicomplete multipartite digraphs

For digraphs DD and HH, a mapping f:V(D)→V(H)f:V(D)→V(H) is a homomorphism of  DDto  HH if uv∈A(D)uv∈A(D) implies f(u)f(v)∈A(H)f(u)f(v)∈A(H). For a fixed directed or undirected graph HH and an input graph DD, the problem of verifying whether there exists a homomorphism of DD to HH 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,HD,H and a cost ci(u)ci(u) for each u∈V(D)u∈V(D) and i∈V(H)i∈V(H). The cost of a homomorphism ff of DD to HH is ∑u∈V(D)cf(u)(u)∑u∈V(D)cf(u)(u). Let HH be a fixed digraph. The minimum cost homomorphism problem for HH, MinHOMP(HH), is stated as follows: For input digraph DD and costs ci(u)ci(u) for each u∈V(D)u∈V(D) and i∈V(H)i∈V(H), verify whether there is a homomorphism of DD to HH 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 HH is a semicomplete digraph. In this paper we extend the classification to semicomplete kk-partite digraphs, k≥3k≥3, and obtain such a classification for bipartite tournaments.