Hardness of Approximation of Graph Partitioning into Balanced Complete Bipartite Subgraphs

For a graph G, a biclique edge partition SBP(G) is a collection of complete bipartite subgraphs {S 1, S 2, . . . , S q} such that each edge of G is contained in exactly one S i. This paper proves that the Minimum Balanced Complete Bipartite Partitioning Problem (BCBP) is NP-hard to approximate within a factor (1 + B) where B = 1/34544. BCBP seeks for SBP(G) such that each S i is a balanced complete bipartite graph. A balanced complete bipartite graph is a bipartite graph G(U,V, E) such that |U | = |V | and for all vertices u ∈ U and v ∈ V there is an edge uv ∈ E.