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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.