Approximation of Minimum Cost Homomorphisms
Approximation of Minimum Cost Homomorphisms
复制标题
最小成本同态的近似
DOI：
10.1007/978-3-642-33090-2_51
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
A. Rafiey
中科院分区：
文献类型：
--
作者：
P. Hell;M. Mastrolilli;M. M. Nevisi;A. Rafiey
设H是一个不含环的固定图。我们证明了，如果H是一个共圆弧双图，那么H的最小费用同态问题允许一个多项式时间常数比近似算法;否则，最小费用同态问题是已知的H是不可近似的。这解决了一个问题提出了在较早的文件。为了逼近的目的，我们通过最小序的存在性给出了共圆弧偶图的一个新的刻画。我们的算法，然后通过去随机化一个两阶段的随机过程。对于所有顶点都有环的图H，我们给出了一个类似的结果：如果H是区间图，则H的最小代价同态问题允许多项式时间常数比逼近算法，否则H的最小代价同态问题是不可逼近的。
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.