最大权独立集的相关概念

独立集： 给定一个一般图 $G(V, E)$，选出图中的某一个点集，使得选出的所有点之间不存在边，则将这个点集称为原图的 独立集

最大权独立集： 给定一个有向图 $G(V, E)$，每个点上有一个非负权值，而图中权值和最大的独立集称为 最大权独立集

如何求最大权独立集：

最大权独立集和最小权点覆盖集问题一样，在一般情况下都是一个 NP 完全问题（NPC 问题），只能用爆搜来解决，但是在二分图中却具有非常高效的特殊做法。

结论：最大权点独立集 $=$ 所有点的总权值 $-$ 最小权点覆盖集

若整个点集是 $V$，点覆盖集是 $V_1$，那么补集就是 $V_2 = V - V_1$。

这里有一个性质，任意一个点覆盖集的补集都一定是独立集。这里进一步证明这个性质。可以用反证法，假设点覆盖集 $V_1$ 的补集 $V_2$ 不是独立集，说明 $V_2$ 中存在两个点 $u, v$ 之间存在一条边 $(u, v)$。由于 $V_1$ 同样是 $V_2$ 的补集，说明 $V_1$ 中一定不包含 $u, v$ 这两个点，那么 $(u, v)$ 这条边的两个点就都不在 $V_1$ 中，即 $V_1$ 不是一个点覆盖集，与条件矛盾，反证得出任意一个点覆盖集的补集都是一个独立集。

以上性质反过来，任意一个独立集的补集都一定是点覆盖集。同样用反证法，假设独立集 $V_2$ 的补集 $V_1$ 不是点覆盖集，就必然存在一条边 $(u, v)$，使得这条边的两个点 $u, v$ 都不在 $V_1$，即一定在 $V_2$ 中，也就说明 $V_2$ 中存在两个点 $u, v$ 之间是有边的，所以 $V_2$ 就不是一个独立集，反证得出任意一个独立集的补集都是一个点覆盖集。

可以发现独立集和点覆盖集之间是存在补集这样一个对应关系的，然后看一下两者之间的数量关系，数量关系就非常明显了，因为 $V_1$ 和 $V_2$ 互为补集，所以两个集合的权值总和就等于所有点的权值和，即 $w(V_1) + w(V_2) = w(V)$，而 $w(V)$ 是一个固定值，因此想让 $w(V_2)$ 取最大，$w(V_1)$ 就必然取到最小，因此要想求最大全独立集，只需要求一下最小权点覆盖集，最小权点覆盖集的补集就是最大权独立集，由此得证结论。