In a directed graph i want to call bfs on some of the vertices so that all of the vertices will be met.

(in other words all of the other vertices are reachable from these chosen vertices.)

I want to find the minimum number of such vertices.

Actually this problem arises in social networks when we want to find the minimum number of people to which if we send a message then all of the network members will get that.(suppose that we know when someone gets the message he/she will send that to all of his/her followers.)

Can anyone help?

  • 6
    $\begingroup$ Contract to strongly connected components, topologically sort, find sources. $\endgroup$ – G. Bach Jan 14 '14 at 0:16
  • 4
    $\begingroup$ Come to think of it, topologically sorting is superfluous. $\endgroup$ – G. Bach Jan 14 '14 at 2:00
  • $\begingroup$ I am pretty sure you will find your answer in this paper that I've read a few years ago. It's about the minimal set of words that you must know in a dictionnary in order to understand every definitions. It's very similar to your problem. $\endgroup$ – Amelie Turgeon Feb 4 '14 at 14:05
  • $\begingroup$ I don't understand your question, especially when you say "the minimum number": the minimum number is a number. Do you mean you're looking for a set $S$, of minimal size, such that every vertex is reachable from $S$? $\endgroup$ – David Richerby Feb 4 '14 at 16:19
  • $\begingroup$ Yes David. Exactly! $\endgroup$ – HsnVahedi Feb 4 '14 at 20:05

The problem can be reduced to finding "sources" (opposite of "sinks", nodes with in-degree zero) in the graph. Suppose there is an optimal solution in which $B$ is one of the chosen nodes and there is an edge $A\rightarrow B$. Then we can put $A$ instead of $B$ in the solution and still cover the whole graph ($A$ can reach $B$, so it can reach all the nodes reachable from $B$). On the other hand, "sources" have to be chosen because they are not reachable from any other node. Then we should repeatedly find "source" nodes, chose them and mark all the vertices reachable from them as covered.

If there are no "source" nodes, then the graph must have cycles. All the nodes in a cycle are equivalent in terms of the nodes they can reach. Thus, they can be simplified into a "supernode". If eventually the supernode becomes a "source" and hence chosen by the algorithm, that means an arbitrary node of the cycle can be chosen.

So the algorithm repeatedly performs iterations of "finding source nodes" and "simplification" until the whole graph is covered.

| cite | improve this answer | |
  • $\begingroup$ Technically, you need to contract strongly connected components before finding sources, since a cycle can also behave as a source for the OP's purposes. $\endgroup$ – Antimony Mar 29 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.