# find the minimum number of vertices in a directed graph from which the other vertices are reachable

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?

• Contract to strongly connected components, topologically sort, find sources. – G. Bach Jan 14 '14 at 0:16
• Come to think of it, topologically sorting is superfluous. – G. Bach Jan 14 '14 at 2:00
• 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. – Amelie Turgeon Feb 4 '14 at 14:05
• 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$? – David Richerby Feb 4 '14 at 16:19
• Yes David. Exactly! – 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.