On the approximation of minimum cost homomorphism to bipartite graphs

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.