Minimum cost homomorphism dichotomy for oriented cycles (Q844220)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum cost homomorphism dichotomy for oriented cycles |
scientific article |
Statements
Minimum cost homomorphism dichotomy for oriented cycles (English)
0 references
18 January 2010
0 references
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.
0 references
digraph
0 references
homomorphism
0 references
minimum cost
0 references
dichotomy
0 references
0 references