最佳答案
在任何图中,独立集的补集是vertex cover反之亦然,所以你的问题相当于在图中找到最小权重顶点覆盖。后者可以使用最大流技术解决:
引入一个 super 源 S 和一个 super 汇 T。通过将其权重作为容量的边将二分图左侧的节点连接到 S。对右侧做同样的事情并下沉 T。为原始图的边分配无限容量。
现在在构建的网络中找到最小的 S-T 割。切割的值是最小顶点覆盖的权重。要了解为什么这是真的,请考虑切割边:它们不可能是原始边,因为它们具有无限容量。如果切割左侧边,则对应于将相应的左侧节点放入顶点覆盖中。如果我们不切割左侧边,我们需要从右侧的相邻顶点切割所有右侧边。
因此,要实际重建顶点覆盖,只需收集所有与切边相邻的顶点,或者从 S 中不可达的左侧节点和可达的右侧节点来自 S.
关于algorithm - 二部图中的最大加权独立集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24204747/