2007/08/19 by E. J. Kim, Gregory Gutin, Kim, E. J. +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0708.2545
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 HOM(H). An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in \citegutinDAM154a. 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 MinHOM(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. Although a complete dichotomy classification of the complexity of MinHOM(H) for a digraph H remains an unsolved problem, complete dichotomy classifications for MinHOM(H) were proved when H is a semicomplete digraph \citegutinDAM154b, and a semicomplete multipartite digraph \citegutinDAM. In these studies, it is assumed that the digraph H is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in \citegutinRMS.\footnoteThis paper was submitted to SIAM J. Discrete Math. on October 27, 2006