寻找最小集合的算法，使其“感染”整个图形

Question

寻找最小集合的算法，使其“感染”整个图形

algorithmgraph-theory

14

我的问题是关于用最小的顶点集感染整个图的问题。问题大致如下：对于有向图中的一个顶点A，如果对于形如(A,B)的所有入边（有向图中A指向B），B也被感染了，那么A将被感染。如果我们拿一个具体的例子来说：

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

第一轮迭代：由于唯一指向F和D的顶点是E且E已被感染，因此顶点F和D也被感染。

第二轮迭代：由于顶点A和D都被感染，因此顶点B也被感染。

第三轮迭代：由于顶点B在第二轮迭代中被感染，所以最终顶点C也被感染。

在这种情况下，我选择的感染集合{E，A}能够感染整个图。显然，这并不总是可能的，例如感染集合为{B}（由于B没有指向A，因此无法到达A），或者感染集合为{A}（由于D是B的父节点且健康，因此B没有被感染）。

我真的想找到一种算法，能够找到最小的感染顶点集合，在任意次迭代后能够感染整个图。这样的算法是否已经存在？

为了澄清，对于自环的顶点，它必须在感染集合中，因为这是唯一能使其被感染的方式。

btilly回答了问题的NP难度。那么有人能提供一个好的近似算法吗？它不需要太高效。毕竟，我只需要在大型图上运行一次。它有大约750,000个节点，每个节点大约有10条边。

- Nathan Kim

7

@NathanKim，这是一个非常好的问题！ - ravenspoint

我认为你想要一种类似于拓扑排序的方法，但是可以打破循环。 - Neil

1

拓扑排序可以解决它，但除了所有入边的要求。 - ravenspoint

如果图形没有有向循环并选择起始点，则执行拓扑排序非常简单。对于有向循环，我想到的与@btilly相同。 - Neil

9

这个问题正在Meta Stack Overflow上讨论。 - E net4

显示剩余5条评论

2个回答

2

问题在于每个节点的所有源节点都必须被感染才能感染一个节点。因此，现实情况是每条边都必须携带感染。所以 -

- LOOP over the roots ( nodes with only out edges )
    Add root to solution
    Mark all edges reachable from root
    If every edge marked
         STOP
 - LOOP over every node that has unmarked out edges
       Add node to solution
       Mark all edges reachable from node
       If every edge marked
             STOP
 - LOOP over disconnected nodes
       Add node to solution
 STOP

请注意，这并不总是提供最优解。它提供了一个成功的方案，可以感染每个节点。暴力优化：将算法放置在枚举节点顺序的循环中，并在解决方案改进时保留它。

- ravenspoint

如果你的图没有叶子节点，这个方法就不起作用了。而且，它也不能保证感染，就像 OP 示例中的 A 节点一样。 - nonDucor

是的，它不会感染B，因为B还有另一个未被感染的节点（D）。 - nonDucor

2

错过了所有入边都必须被感染的要求。 - ravenspoint

我已经调整了所有边缘需求的算法。 - ravenspoint

1

@ravenspoint 你最终会得到一个解决方案。它不一定是最小的可能性。我们被要求提供最小的可能性。这是一个更难的问题。 - btilly

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

这个问题是NP难问题。

包含在这个最小感染集中的顶点可以分为两组。第一组是没有入边的所有节点。第二组是使图变成无环图的最小节点集。（如果你留下一个环，那么环中的东西将不会被感染。相反，如果你没有留下环，那么可以通过归纳法容易证明整个图将被感染。）

非常重要的是，如果你能够解决这个问题，那么就可以轻松地从解决方案中移除没有入边的节点，然后剩下的就是最小反馈顶点集。这将提供一种算法来解决任意图的NP难问题。

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