×

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].

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
Full Text: DOI