5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ May I ask back what are the applications of kernel? All my searches seems to go to the unrelated SVM kernel in the context of machine learning. $\endgroup$ – Apiwat Chantawibul Jul 14 '14 at 15:19
  • $\begingroup$ I saw that it is used in biological sequences. Apart from that, I have no idea, I saw this question at a previous Algorithms exam of mine. $\endgroup$ – TheNotMe Jul 14 '14 at 16:14
4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Great, thanks. An equal algorithm: Do a topological sort, run through the vertices left to right. If 'v' is not black, mark it as black, put it in the kernel, and mark all its' neighbours as black (as in $<v,u> \in E$). Continue until you finish the sort. $\endgroup$ – TheNotMe Jul 14 '14 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.