Vertex cover algorithms for directed graphs?
Thanks for the edit!  This isn't vertex cover; it's something different.

There are simple algorithms for this problem.  Decompose the graph into a dag of strongly connected components.  (The dag is sometimes called "the metagraph".)  Each source vertex in the dag corresponds to a SCC that has no edges coming into it from outside; for each such SCC, pick one vertex and add it to $S$.

The result will be the smallest set $S$ that meets your conditions.  This can be done in $O(V+E)$ time.



Answer to the original version of your question (now irrelevant):

Your problem, as stated, is trivial: the solution is the empty set $S=\emptyset$.

If, on the other hand, you meant that $e_{ij} &gt; 0$ implies $i \in S$, the problem is also trivial: the set $S$ has to include the source vertex of every edge.  So, you just loop over all the edges $(i,j)$ and add $i$ to $S$.