二部图中的最大赋权独立集 [英] Maximum weighted independent set in bipartite graph

问题描述

给定的二部图。每个顶点都有一些整数值-权重。

是否可以在多项式时间内找到此图中的最大权重independent vertex set？

如果存在这样的解决方案，则此问题的算法是什么？

推荐答案

在任何图中，独立集的补集都是vertex cover，反之亦然，所以你的问题等价于寻找图中最小权的顶点覆盖。后者可以使用最大流技术解决：

引入一个超源S和一个超宿T。通过以其权重为容量的边将二部图左侧的节点连接到S。对右侧执行相同的操作，然后将T下沉。为原始图形的边分配无限容量。

现在求出所构造的网络的最小S-T割。切割的值是最小顶点覆盖的权重。要了解这一点，请考虑切割边：它们不可能是原始边，因为它们具有无限的容量。如果切割左侧边，则相当于将相应的左侧节点放入顶点覆盖中。如果而不是剪切左侧边缘，则需要从右侧相邻顶点剪切所有右侧边缘。

因此，要实际重建顶点覆盖，只需收集与切割边相邻的所有顶点，或者收集无法从S到达的左侧节点和可从S到达的右侧节点

。

这篇关于二部图中的最大赋权独立集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！