2005/07/06 by G. Gutin, Gutin, G., A. Rafiey +3
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.cs/0507017
8 pages
arxiv created 2005/08/24 · arxiv updated 2009/12/01
The following optimization problem was introduced in \citegutinDAM, where it was motivated by a real-world problem in defence logistics. Suppose we are given a pair of digraphs D,H and a positive 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). For a fixed digraph H, the minimum cost homomorphism problem for H, MinHOMP(H), is stated as follows: For an 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 exists, find such a homomorphism of minimum cost. We obtain dichotomy classifications of the computational complexity of the list homomorphism problem and MinHOMP(H), when H is a semicomplete digraph (a digraph in which every two vertices have at least one arc between them). Our dichotomy for the list homomorphism problem coincides with the one obtained by Bang-Jensen, Hell and MacGillivray in 1988 for the homomorphism problem when H is a semicomplete digraph: both problems are polynomial solvable if H has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for \MiP is different: 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.