2007/08/19 by Gregory Gutin, G. Gutin, Eun Jung Kim +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0708.2544
arxiv created 2007/08/19 · openalex publication_date 2007/08/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For digraphs D and H, a mapping f: V(D)\dom V(H) is a homomorphism of D to H if uv∈ A(D) implies f(u)f(v)∈ A(H). For a fixed digraph H, the homomorphism problem is to decide whether an input digraph D admits a homomorphism to H or not, and is denoted as HOMP(H). Digraphs are allowed to have loops, but not allowed to have parallel arcs. A natural optimization version of the homomorphism problem is defined as follows. If each vertex u ∈ V(D) is associated with costs ci(u), i ∈ V(H), then the cost of the homomorphism f is ∑u∈ V(D)cf(u)(u). For each fixed digraph H, we have the \em minimum cost homomorphism problem for H and denote it as MinHOMP(H). The problem is to decide, for an input graph D with costs ci(u), u ∈ V(D), i∈ V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost. In a recent paper, we posed a problem of characterizing polynomial time solvable and NP-hard cases of the minimum cost homomorphism problem for acyclic multipartite tournaments with possible loops (w.p.l.). In this paper, we solve the problem for reflexive multipartite tournaments and demonstrate a considerate difficulty of the problem for the whole class of multipartite tournaments w.p.l. using, as an example, acyclic 3-partite tournaments of order 4 w.p.l.\footnoteThis paper was submitted to Discrete Mathematics on April 6, 2007