2007/08/18 by Arvind Gupta, Pavol Hell, Gupta, Arvind +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.CC #cs.DM
paper · pdf · doi:10.48550/arxiv.0708.2514
openalex publication_date 2007/08/18 · arxiv created 2007/10/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For digraphs G and H, a homomorphism of G to H is a mapping f: V(G)\dom V(H) such that uv∈ A(G) implies f(u)f(v)∈ A(H). If moreover each vertex u ∈ V(G) is associated with costs ci(u), i ∈ V(H), then the cost of a homomorphism f is ∑u∈ V(G)cf(u)(u). For each fixed digraph H, the \em minimum cost homomorphism problem for H, denoted MinHOM(H), is the following problem. Given an input digraph G, together with costs ci(u), u∈ V(G), i∈ V(H), and an integer k, decide if G admits a homomorphism to H of cost not exceeding k. We focus on the minimum cost homomorphism problem for \em reflexive digraphs H (every vertex of H has a loop). It is known that the problem MinHOM(H) is polynomial time solvable if the digraph H has a \em Min-Max ordering, i.e., if its vertices can be linearly ordered by < so that i<j, s<r and ir, js ∈ A(H) imply that is ∈ A(H) and jr ∈ A(H). We give a forbidden induced subgraph characterization of reflexive digraphs with a Min-Max ordering; our characterization implies a polynomial time test for the existence of a Min-Max ordering. Using this characterization, we show that for a reflexive digraph H which does not admit a Min-Max ordering, the minimum cost homomorphism problem is NP-complete. Thus we obtain a full dichotomy classification of the complexity of minimum cost homomorphism problems for reflexive digraphs.