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.

enter image description here Is there any good (approximation) algorithms?

  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Jan 4 at 9:34
  • 1
    $\begingroup$ 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. $\endgroup$ – kivantium Jan 4 at 11:25
  • $\begingroup$ Do you have any good algorithm in the case of $K=2$? $\endgroup$ – Apass.Jack Jan 4 at 21:11
  • $\begingroup$ No. When $K=1$, there is an obvious algorithm (adding all edges), but when $K \geq 2$, I have no idea. $\endgroup$ – kivantium Jan 8 at 4:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.