×

The dichotomy of minimum cost homomorphism problems for digraphs. (English) Zbl 1261.05035

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.

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)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link