The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

For digraphs DD and HH, a mapping f:V(D)→V(H)f:V(D)→V(H) is a homomorphism of DD to HH if uv∈A(D)uv∈A(D) implies f(u)f(v)∈A(H)f(u)f(v)∈A(H). For a fixed digraph HH, the homomorphism problem is to decide whether an input digraph DD admits a homomorphism to HH or not, and is denoted as HOM(HH).An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) [13]. If each vertex u∈V(D)u∈V(D) is associated with costs ci(u),i∈V(H)ci(u),i∈V(H), then the cost of the homomorphism ff is ∑u∈V(D)cf(u)(u)∑u∈V(D)cf(u)(u). For each fixed digraph HH, we have the minimum cost homomorphism problem for  HH and denote it as MinHOM(HH). The problem is to decide, for an input graph DD with costs ci(u),u∈V(D),i∈V(H)ci(u),u∈V(D),i∈V(H), whether there exists a homomorphism of DD to HH and, if one exists, to find one of minimum cost.Although a complete dichotomy classification of the complexity of MinHOM(HH) for a digraph HH remains an unsolved problem, complete dichotomy classifications for MinHOM(HH) were proved when HH is a semicomplete digraph Gutin, Rafiey and Yeo (2006) [10], and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) [12] and [11]. In these studies, it is assumed that the digraph HH is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) [9].