Gutin, Gregory, Rafiey, A. and Yeo, Anders (2006) Minimum Cost and List Homomorphisms to Semicomplete Digraphs. Discrete Applied Mathematics, 154 (6).
Full text access: Open
For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uvA(D) implies f(u)f(v)A(H). Let H be a fixed directed or undirected graph. The homomorphism problem for H asks 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 xV(D) is assigned a set Lx of possible colors (vertices of H). The following optimization version of these decision problems generalizes the list homomorphism problem and was introduced in Gutin et al. [Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math., to appear], 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 integral cost ci(u) for each uV(D) and iV(H). The cost of a homomorphism f of D to H is . For a fixed digraph H, the minimum cost homomorphism problem for H is stated as follows: for an input digraph D and costs ci(u) for each uV(D) and iV(H), verify whether there is a homomorphism of D to H and, if one exists, find such a homomorphism of minimum cost. We obtain dichotomy classifications of the computational complexity of the list homomorphism and minimum cost homomorphism problems, when H is a semicomplete digraph (digraph in which there is at least one arc between any two vertices). 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 the minimum cost homomorphism problem 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.
This is a Submitted version This version's date is: 2006 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/73ebe366-5bdd-dd81-f313-9f9fac85722d/3/
Deposited by Research Information System (atira) on 25-Jul-2012 in Royal Holloway Research Online.Last modified on 25-Jul-2012