最大独立集算法

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

我不相信存在一种算法,用于在二分图中找到最大独立顶点集,而不是在所有可能的独立集中找到最大值的强力方法.

有:找到最大独立集相当于找到最小顶点覆盖(通过取结果的补码),Konig定理指出二分图中的最小顶点覆盖等价于最大匹配,并且可以在多项式中找到时间.我不知道找到所有的匹配,但似乎可能有指数多.