Finding a minimum set of dependencies in a cycle-filled dependency graph
Decompose your graph into strongly connected components.  Now each strongly-connected component (SCC) of size $&gt;1$ contains a cycle.

Let $G=(V,E)$ be the dag of SCCs obtained by this decomposition.  Sometimes $G$ is called "the metagraph".  Let $S \subseteq V$ be the set of SCCs of size $&gt;1$.  Now our algorithmic problem is as follows:


  Given the dag $G$ and the set $S$, find a minimum-size set $T \subseteq V$ such that for every $v \in S$, there's a path from $v$ to some vertex of $T$.


The rest of the answer below is incorrect, but I'll leave the problem statement above in case it helps someone else find a clean algorithm.



This problem can be solved using a network flow algorithm.

In particular, this problem can in turn be rephrased as something akin to a minimum-cut problem: if we add a source vertex $s$ with an edge to each vertex of $S$ and a sink vertex $t$ with an edge from each vertex of $T$ to $t$, we want to find a minimum-size set of vertices that completely disconnect $s$ from $t$.  Notice that this isn't quite the normal minimum-cut problem, because here we care about minimizing the number of selected vertices rather than minimizing the cost of the edges that cross the cut, but it's close.

Here's how we can solve this problem.  For each vertex $v \in V$, we add two vertices $v_\text{in},v_\text{out}$, and we add an edge with cost 1 from $v_\text{in}$ to $v_\text{out}$.  Also, we replace each edge $(v,w) \in E$, with the edge $(v_\text{out}, w_\text{in})$, and we make this edge have cost $\infty$.  We add a source vertex $s$ and, for each $v \in S$, we add a source vertex $s$ and an edge of capacity $\infty$ from $s$ to $v_\text{in}$.  We also add a sink vertex $t$ and, for each $v \in V$, we add an edge of capacity $1$ from $v_\text{out}$ to $t$.  Let $G'=(V',E')$ be the resulting graph.

Finally, we find a minimum $(s,t)$-cut in $G'$.  This can be done by using a standard network flow algorithm to compute the maximum $(s,t)$-flow, and then using the Ford-Fulkerson min-cut/max-flow theorem to reconstruct a minimum $(s,t)$-cut.  Suppose the cut is $(U,V'\setminus U)$, where $s \in U$ and $t \notin U$.  Then for each vertex $v \in V$ such that $v_\text{in} \in U$ and $v_\text{out} \notin U$, we add $v$ to $T$.  This gives us a set $T$ of vertices that, in $G$, disconnect $s$ from $t$, and by construction, the size of $T$ is minimal.