最大独立集算法

7

我不相信存在一种算法,可以在二分图中找到最大独立顶点集,除了通过暴力方法找到所有可能的独立集合中的最大值。

我想知道如何编写伪代码来查找所有可能的顶点集。

假设有一个具有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)

有没有办法改进这个算法以更好地搜索所有可能性。我知道二分图的最大集合等于红色加蓝色减最大匹配数。这个问题出现在如果一开始选择了所有可能的红色,如果它们连接到所有其他可能的蓝色,那么我的集合只有一个蓝色和其余都是红色。

图的规模有多大?节点数和边数分别是多少?将图的补图输入标准的最大团算法可能是可行的。 - Aaron McDaid
2个回答

10
我不相信存在一种算法可以在双分图中找到最大独立顶点集,除了通过找到所有可能的独立集之间的最大值来使用暴力方法。
实际上是有的:找到最大独立集等价于找到最小顶点覆盖(通过取补集得到),Konig's theorem表明,在双分图中,最小顶点覆盖等价于最大匹配,并且可以在多项式时间内找到。至于找到所有匹配,似乎可能会有指数级别的数量。

顶点覆盖:对于所有的边(u,v),要么 u 在 C 中,要么 v 在 C 中。独立集:对于所有的边(u,v),要么 u 不在 I 中,要么 v 不在 I 中。如果你将 I 看作是 C 的补集,则这些条件是等价的。 - sdcvvc
谢谢提到顶点覆盖。我以前从未听说过它们。所以即使我是正确的,听到新想法仍然很好! - Aaron McDaid
“或”默认为包含或(||运算符),在独立集中也是一样的(要么u不在I中,要么v不在I中,要么u和v都不在I中)。也许你应该尝试理解正在发生的事情。顶点覆盖不是独立集并不矛盾,它的补集是独立的。 - sdcvvc
糟糕!我现在明白了。 我一直在想“互补图中的顶点覆盖”(即翻转边缘)。 你是对的。 (现在,除非您编辑答案,否则我无法upvote您的答案!) - Aaron McDaid
1
  1. 寻找最大匹配(例如 Hopcroft-Karp 算法)
  2. 使用维基百科上给出的 Konig 定理算法来获取顶点覆盖
  3. 输出不在覆盖中的顶点以获取独立集
- sdcvvc
显示剩余11条评论

1
正如Aaron McDaid在他现在已删除的答案中提到的,寻找最大独立集的问题等价于寻找最大团。这个等价性是指在一个图G中寻找最大独立集与在G的补图中寻找最大团是相同的。该问题被认为是NP完全的。
你提到的暴力解决方案需要O(n^2 2^n),但实际上有更好的解决方法。Robson在1986年发表了一篇名为“最大独立集算法”的论文,其中给出了一种算法,其时间复杂度为O(2^{c*n}),其中常数0如果您有一个二分图,需要注意的一点是,两侧都形成了独立集。在完全二分图K_{b,r}中,它被划分为B x R,其中|B|=b|R|=r,其中从B中的每个顶点到R中的每个顶点都有一条边,而B内部没有边,R内部也没有边,最大独立集是B,如果b>=r,否则是R

通常情况下,选择BR是不起作用的。sdcvvc指出了具有顶点{1,2,3,A,B,C}和边缘{A,1},{A,2},{A,3},{B,3},{C,3}的示例。在这种情况下,最大独立集是{1,2,B,C},它比任何一个分区{A,B,C}{1,2,3}都要大。

从较大的BR开始,并从那里继续可能会改进Robson算法,尽管我不确定这会有多大的差异。

或者,您可以在图的二分补充中使用Hopcroft-Karp算法来查找最大匹配,然后将匹配中使用的顶点作为独立集。这提供了一个多项式时间算法来解决问题。


我认为最后一段没有考虑到Konig定理是不正确的。例如,如果图是完全二分图,则其二分补图为空,Hopcroft-Karp算法将无法找到任何匹配,而最优解是选择所有蓝色(或红色)顶点。 - sdcvvc
PengOne,我删除了我的答案,因为一旦我理解了@sdcvvc的答案,我决定人们应该使用那个答案而不是我的。就我所知,它是正确的。 - Aaron McDaid
有没有Robson算法的软件实现? - simon

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接