Hell, Pavol; Mastrolilli, Monaldo; Nevisi, Mayssam Mohammadi; Rafiey, Arash Approximation of minimum cost homomorphisms. (English) Zbl 1365.05203 Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 587-598 (2012). Summary: Let \(H\) be a fixed graph without loops. We prove that if \(H\) is a co-circular arc bigraph then the minimum cost homomorphism problem to \(H\) admits a polynomial time constant ratio approximation algorithm; otherwise the minimum cost homomorphism problem to \(H\) is known to be not approximable. This solves a problem posed in an earlier paper. For the purposes of the approximation, we provide a new characterization of co-circular arc bigraphs by the existence of min ordering. Our algorithm is then obtained by derandomizing a two-phase randomized procedure. We show a similar result for graphs \(H\) in which all vertices have loops: if \(H\) is an interval graph, then the minimum cost homomorphism problem to \(H\) admits a polynomial time constant ratio approximation algorithm, and otherwise the minimum cost homomorphism problem to \(H\) is not approximable.For the entire collection see [Zbl 1246.68031]. Cited in 10 Documents MSC: 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) 05C62 Graph representations (geometric and intersection representations, etc.) 05C85 Graph algorithms (graph-theoretic aspects) 68W20 Randomized algorithms 68W25 Approximation algorithms PDFBibTeX XMLCite \textit{P. Hell} et al., Lect. Notes Comput. Sci. 7501, 587--598 (2012; Zbl 1365.05203) Full Text: DOI