Subset of Vertices maximizing a function I have a Digraph $G = (V, E)$ and a function $f: V \to \mathbb{R}$ and want to find $S \subseteq V$ so that $f(S)$ is maximal with the condition that if an edge $(v,w)$ exists in the Graph and $v \in S$ then $w \in S$.
My general idea is to identify the strongly connected components (becuase if I pick one vertex from a SCC for $S$ I have to pick all of them anyway) and build a reduced Graph where nodes represent the SCCs, their value regarding $f$ is the sum of their values in $G$ and the edges are the edges between them.   
Now (the part I'm not so sure about) I calculate a value for each vertex $w$ that is $f(w)$ plus the sum of $f(v)$ for all $v$ reachable from that vertex. I can probably do that by finding the transitive reduction of the Graph and run a modified DFS on it. 
I think using that value I can find $S$, although I'm not quite sure how yet. Am I thinking in the right direction or is there a better way to do it?
 A: Yes, you are thinking in the right direction. Futher I'll assume that the digraph is finite. The reduced digraph $G’=(V’, E’)$ has no cycles, it is a forest. Now we can find a set $S’$ of  $G’$ which maximize a sum $\sum_{u’\in S’} f’(u’)$ as follows. Define a function $g$ recursively on the vertices of the graph $G’$, starting from leafs, such that $g’(u’)=f(u’)+\sum_{(u’,v’)\in E’} g(v’)$. For a vertex $u’\in V’$ as $T’(u’)$ we denote the maximal tree, which has $u’$ as a root. Then  $g’(u’)=\sum_{v’\in T’(u’)} f(u’)$. Again, we define recursively on the vertices of the graph $G’$, starting from leafs, a maximal subset $S’(u’)$ of a tree $T’(u’)$ as follows. Put $m(u’)=\sum_{(u’,v’)\in E’} M(v’)$. If $m(u’)>g’(u’)$ then put $M(u’)=m(u’)$ and $S(u’)=\bigcup_{u’,v’\in E’} S(v’)$, otherwise put $M(u’)=g’(u')$ and  $S(u’)=V(T’(u))$. Let $V_0’$ be the set of root vertices of the graph $G’$. The required minimal set is $S’=\bigcup_{u’\in V’_0} S(v’)$ and the minimal value is $\sum_{u’\in V’_0} M(u’)$.
