On the approximation of minimum cost homomorphism to bipartite graphs

作     者：Mastrolilli, Monaldo Rafiey, Arash 

作者机构：IDSIA Switzerland 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2013年第161卷第4-5期

页      面：670-676页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Swiss National Science Foundation [200020-122110/1] Swiss National Science Foundation (SNF) [200020-122110] Funding Source: Swiss National Science Foundation (SNF) 

主　　题：Minimum cost homomorphism Approximation algorithm Min-max ordering 

摘      要：For a fixed target graph H, the minimum cost homomorphism problem, MinHOM(H), asks, for a given graph G with integer costs c(i)(u), u is an element of V (G), i is an element of V (H), and an integer k, whether or not there exists a homomorphism of G to H of cost not exceeding k. When the target graph H is a bipartite graph a dichotomy classification is known: MinHOM(H) is solvable in polynomial time if and only if H does not contain bipartite claws, nets, tents and any induced cycles C-2k for k = 3 as an induced subgraph. In this paper, we start studying the approximability of MinHOM(H) when H is bipartite. First we note that if H has as an induced subgraph C-2k for k = 3, then there is no approximation algorithm. Then we suggest an integer linear program formulation for MinHOM(H) and show that the integrality gap can be made arbitrarily large if H is a bipartite claw. Finally, we obtain a 2-approximation algorithm when H is a subclass of doubly convex bipartite graphs that has as special case bipartite nets and tents. Crown Copyright (C) 2011 Published by Elsevier B.V. All rights reserved.