Inapproximability of the Minimum Biclique Edge Partition Problem
For a graph G, a biclique edge partition S-BP(G) is a collection of bicliques (complete bipartite subgraphs) B-i such that each edge of G is contained in exactly one B-i. The Minimum Biclique Edge Partition Problem (MBEPP) asks for S-BP(G) with the minimum size. In this paper, we show that for arbitrary small epsilon > 0, (6053/6052 - epsilon)-approximation of MBEPP is NP-hard.
inapproximability biclique edge partition np-hard