algorithm - 最大独立集算法

Question

除了在所有可能的独立集合中寻找最大值的蛮力法之外，我认为不存在用于在二分图中寻找最大独立顶点集的算法。

我想知道找到所有可能的顶点集的伪代码。

假设给定一个具有 4 个蓝色顶点和 4 个红色顶点的二分图。目前我会

Start with an arbitrary blue,
  find all red that don't match this blue
  put all these red in Independent Set
  find all blue that dont match these red
  put these blue in Independent Set
  Repeat for next vertex in blue

Repeat all over again for all blue then all vertices in red.

我知道这种方式根本不会给我所有可能的独立集组合，因为在第一步之后我选择了所有不匹配的下一个颜色顶点，而不是遍历每一种可能性。

例如给定一个匹配的图

B  R
1  1
1  3 
2  1
2  3
3  1
3  3
4  2
4  4

Start with blue 1
  Choose red 2 and 4 since they dont match
  Add 2, 4 to independent Set
  Choose 2 and 3 from blue since they dont with 2 or 4 from red
  Add 2 and 3 from blue to independent set as well.
Independent Set = 1,2,3 from blue 2,4 from red
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set)

有没有办法改进这个算法以更好地搜索所有可能性。我知道 |二分图的最大集合| = |红色| + |蓝色| - |最大匹配|。

问题出现的可能性是，通过在第一个给定的蓝色中选择所有可能的红色，如果这些红色连接到所有其他可能的蓝色，那么我的集合永远只有所有 1 个蓝色和其余的红色。

Answer 1

I don't believe there exists an algorithm for finding the maximum independent vertex set in a bipartite graph other than the brute force method of finding the maximum among all possible independent sets.

有:求最大独立集等价于求最小顶点覆盖(对结果求补)，Konig's theorem指出二部图中的最小顶点覆盖等价于最大匹配，并且可以在多项式时间内找到。我不知道如何找到所有匹配项，但似乎可以成倍增加。