Vertex cover algorithms for directed graphs? I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph. 

Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a set of edges between vertices. The edges are directed so we can have $e_{ij} = 1$ but $e_{ji} = 0$ where $i,j \in V$. Here, $e_{ji} = 0$ would mean that there is no edge from $j$ to $i$. 

My problem is as follows. I would like to find the smallest subset of vertices $S \subseteq V$ such that there is a path from every vertex in S to every vertex to V. That is, for every vertex $j \in V$, there is an $i \in S$ such that either: 


$e_{i,j} &gt; 0$ (edge between $i$ and $j$)
$e_{i,{k_1}}e_{{k_1,k_2}}$...$e_{{k_t,j}} &gt; 0$ (path from $i$ to $j$) 


I will assume that $e_{ii} = 1$ to ensure that such a subset exists, as I can set $S = V$. However, this is only optimal when the set of nodes is entirely disconnected.

I'm wondering if this a vertex cover problem? If so, are there algorithms for this problem? I'm slightly confused because most vertex cover algorithms are for problems where the graph is undirected (e.g., $e_{ij} = e_{ji}$). If not, are there algorithms to solve this problem?
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$.