[Math] Find a kernel in a directed graph.

algorithmsgraph theory

It's a question from a sample exam I'm trying to solve but with no success yet.

Let $G(V, E)$ be a directed graph. set $A \subseteq V$ is a kernel if:

i. $\forall u,v\in A \implies (u, v), (v, u) \notin E $ (no edge between two vetex in $A$)

ii. $\forall v \in V $ \ $A, \space \space \exists a\in A$ such that $(a, v) \in E$.

In other words, there's an edge between vertex in A and vertex outside of A.

Suggest an algorithms that finds a kernel in a cycle-less directed graph.

Rqueired runtime: $O(V + E)$.

Can you please give me some hints to find this problem? Thanks in adnvace.

Best Answer

This should work:

  1. Let $A'$ be all vertices with in-degree 0, and let $A''$ be their neighbors
  2. Add vertices in $A'$ to $A$
  3. Add vertices in $A''$ to $V \setminus A$
  4. Remove $A' \cup A''$ from $G$ and repeat steps 1-3 until the graph is empty

Correctness: Since there are no edges between vertices with in-degree 0, property (i) holds for $A'$. As all neighbors of $A'$ are removed in step 4, no edges exist between vertices that are in $A'$ in different iterations.

Every vertex $v \in V \setminus A$ is in $A''$ in some iteration. In the same iteration, there is, by definition of $A''$, a vertex $a \in A'$ with $(a,v) \in E$.

Runtime: The algorithm can be implemented by running a breadth-first type search starting from the set of vertices with in-degree 0. In step 4, it is easy to find the in-degree 0 vertices of the next iteration (they have to be neighbors of vertices in $A''$).

Related Question