Covering by Complete Bipartite Subgraphs

Input

Bipartite graph $G = (V, E)$, positive integer $K \leq |E|$.

Question

Are there $k \leq K$ subsets $V_1, V_2, \dots, V_k$ of $V$ such that each $V_i$ induces a complete bipartite subgraph of $G$ and such that for each edge $\{u, v\} \in E$ there is some $V_i$ that contains both $u$ and $v$?

Classes

• NP-complete

Proofs

NP-complete

Transformation from Partition into Cliques (Orlin, 1977).

Reducible from

• Partition into Cliques

References

• Orlin, J. (1977). Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proceedings), 80(5), 406–424. https://doi.org/10.1016/1385-7258(77)90055-5