Let $G=(V,E)$ be a DAG. A subset $A \subseteq V$ is called a kernel if for all $u,v \in A$ $uv \notin E$ and for all $v \in V-A$ there exists an $a \in A$ such that $av \in E$ (note again, this is a directed graph).
I need to find an algorithm that runs in $O(V+E)$ that upon giving a DAG $G$, would find a kernel in the graph.
I started like this:
Sort the graph toplogically. Such a sorting exists since it is a DAG. Let us mark the output as $v_1, v_2,...,v_n$. Then we run right to left:
If $v_n$ has no ingoing edges, we add it to our kernel set $K$. Else, here I got stuck.
Maybe dynamic programming can help us here?