[Solved]: Finding Kernel in DAG

Problem Detail: 

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?

Asked By : TheNotMe

Answered By : Billiska

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 kernel

You'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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28402