理论计算机科学：这个问题与顶点覆盖有关吗？
Theoretical computer science: is this problem related to vertex cover?
我有以下问题似乎与顶点覆盖问题有一些相似之处。
我们有一个有向图 G=(V,E)，其中 |V|顶点和|E|边缘。假设一个顶点代表一个人，从顶点 A 到顶点 B 的边代表从 B 到 A 的信息路径，即如果给 B 一条信息，那么 A 也有一条信息。但是，如果另一条边从顶点 C 到顶点 A，则信息将不会到达 C，除非有一条从 C 到 B 的边，或者信息也直接提供给 A。
现在的问题是，通过向（最多）k vertices/persons 提供信息，我们最多可以达到多少 vertices/persons。我认为这与顶点问题密切相关，但我们只需要覆盖 k 个顶点而不是所有顶点。但它似乎仍然不太适合另一个问题。
谁能说出一个具有相似结构的著名问题？这将帮助我更好地接近它的近似算法。
编辑：我对这个问题的优化方面很感兴趣，但在我看来，最佳方法是选择一组尽可能大的相关人员，然后从所有人员中删除所选人员其他组连接的人并重复该过程。那么问题将在 P 中，但它实际上是 NP-hard。这个我没看到。
您在这里描述的内容与 dominating set 问题密切相关。支配集是一组节点，其中每个节点要么在集合中，要么在边缘的末端，而边缘的另一个端点在集合中。在你的情况下，你更恰当地看待有向图中的支配集问题，而你的图恰好有边反转。
已知此问题 NP-hard，因此您可能需要寻找近似算法。
我有以下问题似乎与顶点覆盖问题有一些相似之处。
我们有一个有向图 G=(V,E)，其中 |V|顶点和|E|边缘。假设一个顶点代表一个人，从顶点 A 到顶点 B 的边代表从 B 到 A 的信息路径，即如果给 B 一条信息，那么 A 也有一条信息。但是，如果另一条边从顶点 C 到顶点 A，则信息将不会到达 C，除非有一条从 C 到 B 的边，或者信息也直接提供给 A。
现在的问题是，通过向（最多）k vertices/persons 提供信息，我们最多可以达到多少 vertices/persons。我认为这与顶点问题密切相关，但我们只需要覆盖 k 个顶点而不是所有顶点。但它似乎仍然不太适合另一个问题。
谁能说出一个具有相似结构的著名问题？这将帮助我更好地接近它的近似算法。
编辑：我对这个问题的优化方面很感兴趣，但在我看来，最佳方法是选择一组尽可能大的相关人员，然后从所有人员中删除所选人员其他组连接的人并重复该过程。那么问题将在 P 中，但它实际上是 NP-hard。这个我没看到。
您在这里描述的内容与 dominating set 问题密切相关。支配集是一组节点，其中每个节点要么在集合中，要么在边缘的末端，而边缘的另一个端点在集合中。在你的情况下，你更恰当地看待有向图中的支配集问题，而你的图恰好有边反转。
已知此问题 NP-hard，因此您可能需要寻找近似算法。