2

I have the following problem that seems to share some similarities to the vertex cover problem.

We have a directed graph G=(V,E) with |V| vertices and |E| edges. Let us imagine that a vertex represents a person and that an edge from vertex A to vetrex B represents an information path from B to A, i.e. if B is given a piece of information then A also has it. However, if another edge goes from vertex C to vertex A, then the information will not reach C unless there is an edge from C to B or if the information is given directly to A also.

Now the question is what the maximum number of vertices/persons are that we can reach by giving information to (at most) k vertices/persons. I think this is closely related to the vertex problem, but where we only have to cover k vertices instead of all. But still it does not seem to quite fit the other problem.

Can anybody name a well-known problem that shares a similar structure? This would help me better to approach an approximation algorithm for it.

Edit: I am intrested in the optimization aspect of this problem, but it seems to me that an optimal approach would be to choose a set of connected people, as large as possible, and then remove the selected people from all the other sets of connected people and repeat the process. Then the problem would be in P, but it is actually NP-hard. This I do not see.

SimpleProgrammer
  • 259
  • 3
  • 9
  • To clarify - does information flow if there’s a *path* from one node to another? Or does there need to be a direct edge from the first node to the second? – templatetypedef Apr 20 '20 at 15:26
  • Good question. No, information will only travel one step from where it originated, but only in the reverse direction of the edge. For example, if information is placed at a vertex or person with only outgoing edges, then the information will only reach the one person who already has it. This representation might seem confusing and up-side-down, but that is how the problem is formulated. – SimpleProgrammer Apr 20 '20 at 15:35

1 Answers1

1

What you’re describing here is closely related to the dominating set problem. A dominating set is a set of nodes where each node is either in the set or at the end of an edge whose other endpoint is in the set. In your case, you’re more properly looking at the dominating set problem in directed graphs, and your graph happens to have the edge reversed.

This problem is known to be NP-hard, so you’ll likely need to look for approximation algorithms.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • The dominating set is similar to what I look for, but still I am just interested in finding a "sub-dominant set" where k nodes can be marked. These k nodes does not need to cover all the nodes in the graph, just at least m. So it is an optimization problem of the dominating set problem maybe? – SimpleProgrammer Apr 20 '20 at 19:48
  • I will try to formulate myself one more time: it is a dominating set problem in which we try to cover as many nodes as possible by choosing k nodes. Each node chosen will in turn "mark" or include its neighboring nodes if the edges are outwardsgoing. (Forget about the m i mentioned in the previous comment). – SimpleProgrammer Apr 20 '20 at 19:52
  • 1
    That sounds like a way of formulating your problem in terms of the dominating set problem! The fact that you’re trying to optimize what you can cover rather than cover everything doesn’t change the hardness, since in an ideal case you’d cover everything with your choice of k nodes. – templatetypedef Apr 20 '20 at 21:01