Minimum cost and list homomorphisms to semicomplete digraphs (Q2492190)

The homomorphism problem for a digraph \(H\) is to determine whether a directed or undirected input graph \(D\) admits a homomorphism to \(H\). The list homomorphism problem for \(H\) is a generalization of the homomorphism problem for \(H\), where every vertex is assigned a set of possible colors. The paper obtains dichotomy classifications of the computational complexity of the list homomorphism and minimum cost homomorphism problems, when \(H\) is a semicomplete digraph, in which there is at least one arc between any two vertices. The dichotomy for the list homomorphism problem coincides with the one obtained by early researchers for the homomorphism problem when \(H\) is a semicomplete digraph in that both problems are polynomial solvable if \(H\) has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for the minimum cost homomorphism problem is different in that the problem is polynomial time solvable if \(H\) is acyclic or \(H\) is a cycle of length 2 or 3; otherwise, the problem is NP-hard.