Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM COMPLETE BIPARTITE SUBGRAPH COVER

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A complete bipartite subgraph cover for G, i.e., a collection $V_1,V_2,\ldots,V_k$ of subsets of V, such that each $V_i$ induces a complete bipartite subgraph of G and such that for each edge $\left<u,v\right>\in E$ there is some $V_i$ that contains both u and v.
• MEASURE: Cardinality of the complete bipartite subgraph cover, i.e., the number of subsets $V_i$.

  
  

• Good News: Approximable within $O(f(\vert E\vert))$ if MINIMUM CLIQUE PARTITION is approximable within $f(\vert V\vert)$ [221].
• Bad News: See MINIMUM CLIQUE PARTITION.
• Comment: Equivalent to MINIMUM CLIQUE PARTITION under ratio-preserving reduction [444].
• Garey and Johnson: GT18