在给定的二分图中找到所有极大完全二分子图

Question

给定一个二分图，我们想列出所有最大完全二分子图。

例如，

顶点集 L = {A, B, C, D}

顶点集 R = {a, b, c, d, e}

边缘：A-a，A-b，B-a，B-b，C-c，C-d，D-c，D-d，D-e 最大的完全二分是：

{A,B}-{a,b}

{C,D}-{c,d}

{D} - {c,d,e}

我已经找到了一个暴力算法，O（2^n）。 我不知道是否有近似算法或随机算法。

- ColinBinWang

---

这个问题是NP完全问题。关于近似方法的问题最好在数学或理论计算机科学社区中提问，而不是在以编程为导向的社区中。 - n. m.

抱歉，我在数学社区发布了同样的帖子，但他们建议我来这里。 - ColinBinWang

Answer 1

你可以通过在二分图的每个部分之间添加边来将问题转化为查找最大团。

Bron-Kerbosch算法可用于列出图中的所有最大团（不一定是二分图）。它很容易实现，并且具有稍微更好的最坏时间复杂度O(3^(n/3))。此外，还有一种以图形退化为参数的可固定时间界限。

- Jack Cheng

---

具有集合A和B的二分图，且|A|>1或|B|>1时，永远不可能成为团。 - G. Bach

@G.Bach，你说得对。忘记提到转换，请查看编辑。 - Jack Cheng