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

Question

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

是否可以在多项式时间内找到该图中的最大加权独立顶点集？

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

Answer 1

在任何图中，独立集的补集是顶点覆盖，反之亦然，因此您的问题相当于在图中找到最小权重顶点覆盖。后者可以使用最大流量技术解决：

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

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

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

Answer 2

在我看来，这个问题的提出并不好。一方面，一个二分图已经由两个独立的集合组成。任何独立的集合都必须是这些集合的子集，并且对于正权重，它们通常必须具有较低的权重？

将二部图拆分为不连通的子集也很简单，并且对于大多数实际目的，二部图将很少有这些不连通的子集，因此您可以将它们相加。由于您可以在线性时间内找到所有独立子集，并且可以在线性时间内找到它们的权重，因此很明显您可以在 Nodes+edges 中以线性时间做到这一点，

这让我怀疑我误解了你的问题。

基本上，从你的二分图开始，选择一个节点，找到所有连接到它的节点。如果这不是整个图表，您已经找到了一个不连贯的子集，冲洗并重复。你可以随时加起来，所以整个想法对每个节点和边缘都需要一个恒定的时间操作 = N+E 中的线性时间。