“感染”整个图的最小顶点集的算法

Question

我的问题是关于用被视为感染的最小顶点集感染整个图。问题是这样的。对于（不一定简单）有向图中的顶点 A，如果对于(A, B) 形式的所有入边（它是有向图，因此 A 将指向 B）B 也被感染，则 A 将被感染。如果我们举一个具体的例子：

在这种情况下，如果顶点 E、A 被感染：

迭代 1：

顶点 F、D 被感染，因为指向它们的唯一顶点是 E，并且 E 被感染。

迭代 2：

当顶点 A 和 D 都被感染时，顶点 B 也被感染。

迭代 3：

最后，由于迭代 2 中顶点 B 被感染，顶点 C 也被感染。

在这种情况下，我选择的感染集 {E, A} 能够感染整个图。显然，这并不总是可能的，就像 {B} 的受感染集一样（顶点 A 最终不会被感染，因为 B 没有指向它，因此无法到达它）或{A} 的感染集（顶点 B 没有被感染，因为它在 D 中有一个完全健康的父节点）。

我真的很想找到一种算法，可以找到最小的受感染顶点集，这些顶点最终将在任意次数的迭代后感染整个图。这样的东西已经存在了吗？

---

澄清一下，对于自循环的顶点，它必须位于感染集中，因为这是它被感染的唯一方式。

btilly 给出了关于该问题如何是 NP 困难的回应。那么有人可以建议一个好的近似算法吗？它不需要太高效。毕竟我只需要运行一次，尽管是在一个大图表上。它有大约 750,000 个节点，每个节点大约有 10 条边。

Answer 1

这个问题是NP困难的。

作为最小感染集一部分的顶点分为两个桶。第一个桶是没有传入边的所有节点。第二个桶是使图成为非循环的最小节点集。（如果你留下了一个循环，那么该循环中的东西就不会被感染。相反，如果你没有留下任何循环，那么很容易通过归纳证明整个图最终都被感染了。）

非常重要的是，如果您能够解决这个问题，那么就很容易采取解决方案，从中删除没有传入边的节点，然后留下最小的反馈顶点集。这将给出一种算法来解决任意图的 NP 难题。

（是的，是的，我知道维基百科文章到处都说 NP 完全。这是错误的。问题“是否存在大小的反馈顶点集k”是 NP 完全。问题“最小的反馈顶点集是什么” “是 NP 困难的，因为给定一个声明的最小集，你没有多项式算法来验证没有最小集更短。也就是说，决策问题是 NP 完全问题，而优化问题是 NP 困难问题。）