Hell, Pavol; Rafiey, Arash The dichotomy of minimum cost homomorphism problems for digraphs. (English) Zbl 1261.05035 SIAM J. Discrete Math. 26, No. 4, 1597-1608 (2012). Summary: The minimum cost homomorphism problem has arisen as a natural and useful optimization problem in the study of graph (and digraph) coloring and homomorphisms: it unifies a number of other well studied optimization problems. It was shown by G. Gutin et al. [Discrete Appl. Math. 154, No. 6, 890–897 (2006; Zbl 1138.05032); SIAM J. Discrete Math. 22, No. 4, 1624–1639 (2008; Zbl 1184.05042); Graphs Comb. 25, No. 4, 521–531 (2009; Zbl 1188.05073)] that the minimum cost problem for homomorphisms to a digraph \(H\) that admits a so-called extended Min-Max ordering is polynomial time solvable, and these authors conjectured that for all other digraphs \(H\) the problem is NP-complete. In a companion paper [the authors, SIAM J. Discrete Math. 26, No. 4, 1576–1596 (2012; Zbl 1261.05034)], we gave a forbidden structure characterization of digraphs that admit extended Min-Max orderings. In this paper, we apply this characterization to prove Gutin’s conjecture. Cited in 2 ReviewsCited in 6 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) 05C75 Structural characterization of families of graphs 05C85 Graph algorithms (graph-theoretic aspects) Keywords:minimum cost homomorphisms; Min-Max orderings; dichotomy Citations:Zbl 1138.05032; Zbl 1184.05042; Zbl 1188.05073; Zbl 1261.05034 PDFBibTeX XMLCite \textit{P. Hell} and \textit{A. Rafiey}, SIAM J. Discrete Math. 26, No. 4, 1597--1608 (2012; Zbl 1261.05035) Full Text: DOI arXiv Link