是否有一种有效的（比如 O(|V|^2) ）并且最好不过分复杂的算法来将二分图划分为尽可能少的诱导双团？顶点可以重复，以便包含所有边。
我尝试搜索它，但无法理解有关该主题的一些论文。
我将不胜感激任何帮助:)
在图论和组合优化的数学领域中，图 G = (V, E) 的 二分维数 或 biclique 覆盖数 是覆盖所需的最小 biclique 数（即完全二分子图） E 中的所有边。覆盖 G 中所有边的 biclique 集合称为 biclique 边缘覆盖，有时也称为 biclique 覆盖。 G 的二分维数通常用符号 d(G) 表示。
我希望帮助有效地找到一个 biclique 覆盖层，为输入二部图 G 实现 d(G)。
迭代贪婪：一种启发式方法，不能保证找到最优解
假设我们的输入二部图是 n 个顶点上的 G，我们使用“左”或“L”和“右”或“R”来引用其两个顶点集（因此所有边都有一个来自 L 的顶点和一个来自 L 的顶点） R）。
我们将用四个整数表示每个 biclique：
接下来，用 n 个大小为 1 的双簇表示 G：每个顶点一个。这里，left_members 或 right_members 之一将具有单个设置位；它的对侧邻居将精确地设置该顶点的邻居，并且它的同侧邻居将设置所有位。
洗牌双团
贪婪地合并bicliques：我们可以将biclique Y合并到biclique X中，如果：
我们按打乱顺序遍历 biclique，并将每个 biclique 合并到我们可以合并的第一个（按打乱顺序）biclique。
合并（X，Y）：
接下来，将合并的双团打乱，并将它们转换回其构成的 1 元素双团，但按此顺序。每个合并的 biclique 中各个 1-elt biclique 的顺序是无关紧要的。
迭代：继续上面的“贪婪合并...”步骤
每次迭代只能改进或保持封面尺寸不变。每个步骤都相当快，因此您应该能够通过快速语言的有效实现来相当快地获得大量迭代。
一个可能的改进是分层模拟退火。
在我用派系覆盖的随机图（非二分图）进行的实验中，几乎总能找到种子派系覆盖或相同大小的非常相似的覆盖，除了少数例外。
要查看这是否可能找到最佳解决方案，请尝试生成与您的具有相似特征（例如相似的边缘密度）的随机二部图，并使用已知解决方案作为种子。