On the approximation of minimum cost homomorphism to bipartite graphs

For a fixed target graph HH, the minimum cost homomorphism problem, MinHOM(H), asks, for a given graph GG with integer costs ci(u)ci(u), u∈V(G)u∈V(G), i∈V(H)i∈V(H), and an integer kk, whether or not there exists a homomorphism of GG to HH of cost not exceeding kk. When the target graph HH is a bipartite graph a dichotomy classification is known: MinHOM(H) is solvable in polynomial time if and only if HH does not contain bipartite claws, nets, tents and any induced cycles C2kC2k for k≥3k≥3 as an induced subgraph.In this paper, we start studying the approximability of MinHOM(H) when HH is bipartite. First we note that if HH has as an induced subgraph C2kC2k for k≥3k≥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 HH is a bipartite claw. Finally, we obtain a 2-approximation algorithm when HH is a subclass of doubly convex bipartite graphs that has as special case bipartite nets and tents.

► We study the approximation of minimum cost homomorphism to a bipartite graph HH, MinHOM(H). ► It is hard to find a constant approximation for MinHOM(H) when HH is not a circular arc graph. ► We use the ILP formulation of MinHOM(H) and obtain a 2-approximation algorithm for a class of bipartite graphs.