我有以下问题，似乎与顶点覆盖问题有一些相似之处。
我们有一个有向图 G=(V,E) 和 |V| 顶点和 |E| 边缘。让我们假设一个顶点代表一个人，而从顶点 A 到顶点 B 的一条边代表从 B 到 A 的信息路径，即如果给 B 一条信息，那么 A 也有它。但是，如果另一条边从顶点 C 到顶点 A，则信息将不会到达 C，除非存在从 C 到 B 的边，或者如果信息也直接提供给 A。
现在的问题是，通过向（最多）k 个顶点/人提供信息，我们可以达到的最大顶点/人数是多少。我认为这与顶点问题密切相关，但我们只需要覆盖 k 个顶点而不是全部。但它似乎仍然不太适合另一个问题。
谁能说出一个具有相似结构的众所周知的问题？这将帮助我更好地接近它的近似算法。
编辑：我对这个问题的优化方面很感兴趣，但在我看来，最佳方法是选择一组尽可能大的有联系的人，然后从所有其他有联系的人集中删除选定的人人并重复这个过程。那么问题就出在 P 中，但它实际上是 NP 难的。这个我没看到。