algorithm - 二部图中的最大加权独立集

标签 algorithm graph-algorithm independent-set

给定二分图。每个顶点都有一些整数值——权重。

是否有可能找到最大权重 independent vertex set在这张图中多项式时间内?

如果存在这样的解,这个问题的算法是什么?

最佳答案

在任何图中,独立集的补集是vertex cover反之亦然,所以你的问题相当于在图中找到最小权重顶点覆盖。后者可以使用最大流技术解决:

引入一个 super 源 S 和一个 super 汇 T。通过将其权重作为容量的边将二分图左侧的节点连接到 S。对右侧做同样的事情并下沉 T。为原始图的边分配无限容量。

现在在构建的网络中找到最小的 S-T 割。切割的值是最小顶点覆盖的权重。要了解为什么这是真的,请考虑切割边:它们不可能是原始边,因为它们具有无限容量。如果切割左侧边,则对应于将相应的左侧节点放入顶点覆盖中。如果我们切割左侧边,我们需要从右侧的相邻顶点切割所有右侧边。

因此,要实际重建顶点覆盖,只需收集所有与切边相邻的顶点,或者从 S 中可达的左侧节点和可达的右侧节点来自 S.

关于algorithm - 二部图中的最大加权独立集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24204747/

相关文章:

algorithm - 算法符号确认分析

java - 使用Python查找图中两个顶点(节点)之间的所有路径

algorithm - 图中的独立集

算法:如何找到树中独立集的数量?

c# - 顺时针排序点列表

algorithm - 找到最小成本路径的有效算法

java - 在用户社交网络中找到前 k 个喜欢

algorithm - 最大独立集算法

c# - HashSet 的两个总和问题不适用于重复项

python - 使用 Python 实现用于字符串匹配的 Knuth-Morris-Pratt (KMP) 算法