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
