Covering the edges of bipartite graphs using K2,2 graphs

An optimization problem arising in the design of optical networks is shown here to be abstracted by the following model of covering the edges of a bipartite graph with a minimum number of 4-cycles, or K2,2: Given a bipartite graph G=(L,R,E) over the node set L∪R with E⊆{[u,v]:u∈L,v∈R}, and the implicit collection of all four-node cycles in the complete bipartite graph over L∪R. The goal is to cover all the edges in E with a sub-collection of graphs G1,G2,…,Gp, of minimum size, where each Gi is a subgraph of a cycle over four nodes — a 4-cycle. Since a subgraph of a 4-cycle can cover up to 4 edges, this covering problem is a special case of the unweighted 4-set cover problem. This specialization allows us to obtain an improved approximation guarantee. Whereas the currently best known approximation algorithm for the general unweighted 4-set cover problem has an approximation ratio of (where Hp≈lnp denotes the p-th harmonic number), we show that, for every ϵ>0, there is a polynomial time -approximation algorithm for our problem. Our analysis of the greedy algorithm shows that, when applied to covering a bipartite graph using copies of Kq,q bicliques, it returns a feasible solution whose cost is at most (Hq2−Hq+1)OPT+1 where OPT denotes the optimal cost, thus improving the approximation bound for unweighted q2-set cover by a factor of almost 2.