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?
Finding Kernel in DAG
algorithms;graphs
Let's start the algorithm with these 3 sets:$V$ = {all vertices}$K$ = {}$K'$ = {}with the semantics:$V$ stores unprocessed vertices$K$ stores vertices known to be in the kernel$K'$ stores vertices known to be outside the kernelYou're right that all vertices without incoming edges always belongs to the kernel. Add the them to the set $K$ & remove from $V$.The next step is realizing that any vertices that can be immediately reached from vertices in the current $K$ must be outside the kernel. Add these to $K'$ &  remove from $V$.Now, all the vertices that is left in $V$ without incoming edges (from other vertices inside $V$) again can be added to $K$ (and remove from $V$)....Repeat the process until $V$ is empty.