Minimum cost homomorphism dichotomy for oriented cycles (Q844220)

It can be shown that if a reflexive digraph \(H\) has no Min-Max ordering, then \(\text{MinMax}(H)\) is NP-hard, and that if a semi-complete multipartite digraph \(H\) has neither Min-Max ordering nor \(k\)-Min-Max ordering, then \(\text{MinMax}(H)\) is NP-hard. The present paper shows that the same result as for the semi-compete multipartite digraphs holds for oriented cycles. In fact, it proves a graph-theoretic dichotomy for the complexity of \(\text{MinMax}(H)\) when \(H\) is an oriented cycle.