# Decomposition of a bipartite graph into complete bipartite graphs by adding the smallest number of edges

A bipartite graph $$G$$ and an integer $$K$$ is given. I want to decompose $$G$$ into $$K$$ complete bipartite graphs by adding the smallest number of edges.

Below is an example of decomposition when $$K=2$$. The red line indicates an added edge.

Is there any good (approximation) algorithms?

• How about decomposing $G$ into complete bipartite (1,1) graphs? That is, graph of just two vertices and one edge? There is no need to add any edge. – Apass.Jack Jan 4 at 9:34
• If $G$ is decomposed into $K_{1,1}$, the number of decomposed graphs is the number of edges in $G$. The number of decomposed graphs is specified by $K$, so your approach does not work when $K$ and the number of edges are different. – kivantium Jan 4 at 11:25
• Do you have any good algorithm in the case of $K=2$? – Apass.Jack Jan 4 at 21:11
• No. When $K=1$, there is an obvious algorithm (adding all edges), but when $K \geq 2$, I have no idea. – kivantium Jan 8 at 4:07