Minimum cost homomorphism dichotomy for oriented cycles
type: Item
instance of: scholarly article
title: Minimum cost homomorphism dichotomy for oriented cycles
zbMATH Open document ID: 1188.05073
author: G. Gutin
author: Arash Rafiey
author: A. Yeo
published in: Graphs and Combinatorics
publication date: 2010-01-18T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 5659946
zbMATH Keywords: digraph
zbMATH Keywords: homomorphism
zbMATH Keywords: minimum cost
zbMATH Keywords: dichotomy
reviewed by: Wai-Kai Chen
MaRDI profile type: Publication
full work available at URL: s00373-009-0853-9
OpenAlex ID: W2154562890
cites work: Q4500916
cites work: Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
cites work: Minimum Cost Homomorphisms to Reflexive Digraphs
cites work: A dichotomy for minimum cost graph homomorphisms
cites work: Minimum cost and list homomorphisms to semicomplete digraphs
cites work: Minimum cost homomorphisms to semicomplete multipartite digraphs
cites work: Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
cites work: Level of repair analysis and minimum cost homomorphisms of graphs
cites work: On multiplicative graphs and the product conjecture
cites work: Q4780787
cites work: List homomorphisms and circular arc graphs
cites work: Q4432211
cites work: On the complexity of H-coloring
cites work: The Existence of Homomorphisms to Oriented Cycles
cites work: Approximation Results for the Optimum Cost Chromatic Partition Problem
cites work: Coloring of trees with minimum sum of colors
DOI: 10.1007/S00373-009-0853-9
description: scientific article; zbMATH DE number 5659946