Kernels in Directed Acyclic Graphs

Kernels and Direction in a Digraph

A kernel is a set of vertices with two complementary properties: no two selected vertices are joined by an arc, and every unselected vertex has an arc leading into the selected set. In a directed graph, the direction in the second condition matters. For directed acyclic graphs, a sink provides a way to build such a set: select the sink, then remove it and the vertices that point to it. The proof below shows why this procedure works.

For a vertex \(v\), write \(N^-(v)=\{u\in V:u\to v\in E\}\) for its set of in-neighbors. A sink is a vertex with no outgoing arcs. A directed acyclic graph (DAG) is a directed graph with no directed cycle. For \(S\subseteq V\), \(G[S]\) denotes the induced subgraph on \(S\): it has vertex set \(S\) and all arcs of \(G\) whose two endpoints lie in \(S\).

The empty digraph has kernel \(\varnothing\): there are no vertices to violate independence or absorption. Isolated vertices must belong to any kernel, since an isolated vertex outside the set would have no outgoing arc to a member of it. These observations include cases that can arise when the construction removes vertices.

Why a Sink Can Start the Construction

Proof. Let \(G\) be a nonempty finite DAG. Suppose, to the contrary, that it has no sink. Then every vertex has an outgoing arc. Starting at any vertex \(v_0\), repeatedly choose an outgoing neighbor, obtaining a sequence \(v_0,v_1,v_2,\ldots\) with \(v_i\to v_{i+1}\) for every \(i\). Because \(G\) has finitely many vertices, some vertex must repeat. Choose the first index \(j>0\) for which \(v_j=v_i\) for some \(i<j\). By the choice of \(j\), the vertices \(v_i,v_{i+1},\ldots,v_{j-1}\) are distinct. The arcs from \(v_i\) through \(v_j=v_i\) therefore form a directed cycle, contradicting that \(G\) is acyclic. Thus \(G\) has a sink. \(\square\)

This lemma also applies to every nonempty induced subgraph of a DAG. Indeed, a directed cycle in an induced subgraph would also be a directed cycle in the original graph. So after some vertices are removed, the remaining nonempty graph still has a sink.

The Sink-Selection Construction

Suppose \(s\) is a sink in a DAG \(G\). No arc leaves \(s\), and the vertices adjacent to \(s\) by an arc are exactly its in-neighbors \(N^-(s)\). Remove \(s\) and all of \(N^-(s)\), and continue on the induced subgraph that remains. The proposed kernel consists of the sinks selected during this process.

Proof. We use induction on the number of vertices. If \(V=\varnothing\), then \(\varnothing\) is a kernel, because both defining conditions hold vacuously.

Now let \(G\) be a nonempty finite DAG, and assume the theorem holds for every DAG with fewer vertices. By the Lemma, choose a sink \(s\) of \(G\). Set \(R=\{s\}\cup N^-(s)\), and let \(H=G[V\setminus R]\). This is an induced subgraph, so it is acyclic, and it has fewer vertices than \(G\) because \(s\in R\). By the induction hypothesis, \(H\) has a kernel \(K_H\). Define \(K=K_H\cup\{s\}\).

First, \(K\) is independent. The vertices of \(K_H\) are independent because \(K_H\) is a kernel of \(H\), and hence of the induced subgraph on its vertices in \(G\). No arc leaves \(s\), since \(s\) is a sink. There is also no arc from a vertex of \(K_H\) into \(s\): every in-neighbor of \(s\) belongs to \(R\), whereas every vertex of \(H\), including \(K_H\), lies outside \(R\). Thus no two distinct vertices of \(K\) are joined by an arc.

Now take any \(v\in V\setminus K\). If \(v\in N^-(s)\), then \(v\to s\), so \(v\) is absorbed by \(s\in K\). Otherwise \(v\notin R\), so \(v\in V(H)\setminus K_H\). Since \(K_H\) is a kernel of \(H\), there is a \(k\in K_H\) with \(v\to k\). That same arc belongs to \(G\), so \(v\) is absorbed by \(K\). Every vertex outside \(K\) is therefore absorbed, and \(K\) is a kernel of \(G\). \(\square\)

The induction gives a direct construction: select a sink in the current induced graph, add it to the kernel, and delete that sink together with its current in-neighbors. The sink lemma ensures that a choice is available at every nonempty stage. The theorem’s proof verifies that the accumulated selected vertices form a kernel; the examples trace all selections and deletions.

Worked Constructions

Direction Matters: A Common Mistake

A frequent error is to check whether every outside vertex is adjacent to the kernel, without checking the direction of the arc. For example, let \(G\) have \(V=\{a,b\}\) and \(E=\{a\to b\}\). The set \(\{a\}\) is independent, but it is not a kernel: the outside vertex \(b\) has no arc to \(a\). The correct kernel is \(\{b\}\). It is independent, and the only outside vertex \(a\) is absorbed by the arc \(a\to b\).

The sink argument depends on this direction. A sink has no outgoing arcs, so no selected sink can point to a later selected vertex. Its in-neighbors, on the other hand, point into it; deleting them makes it possible to absorb them by the selected sink. Reversing the absorption condition would invalidate this construction.

The result is useful as an existence guarantee: although an arbitrary digraph need not have a kernel, every finite DAG does. The proof also handles disconnected graphs, since the sink at each stage may lie in any component of the current induced graph. The empty graph is the induction base, and isolated vertices are handled by selecting them when they remain. No assumption of connectedness is needed.