Testing a Candidate Kernel
A kernel is a set of vertices that has two properties at once: no two of its members are joined by an arc, and every vertex outside the set sends an arc to a member. The first condition limits which vertices may be chosen together; the second checks that the chosen set can absorb all remaining vertices in the required direction. For a small digraph, testing a proposed set is direct. Finding every kernel requires a systematic way to consider the candidates without overlooking a subset.
Throughout, a digraph \(D=(V,A)\) is finite and has no loops or multiple arcs. An arc is ordered: \(u\to v\) means the arc goes from \(u\) to \(v\). Both \(u\to v\) and \(v\to u\) may occur. The out-neighborhood of \(v\) is \(N_D^+(v)=\{w\in V:v\to w\in A\}\). In particular, an arc from an outside vertex into a set has its tail outside and its head in the set.
Absorption here means a single outgoing arc into \(K\), not merely a directed path that eventually reaches \(K\). Vertices already in \(K\) are not required to send arcs into it. The empty set is independent, but it absorbs no vertex. It is a kernel of the digraph with no vertices, because there are no outside vertices to check; it is not a kernel of any nonempty digraph.
A Complete Test and a Search Strategy
Proof. Assume first that \(K\) is a kernel. Its independence condition says that no two distinct vertices of \(K\) are joined by an arc; the digraph has no loops, so this is exactly the assertion that no arc has both endpoints in \(K\). Its absorption condition says that each vertex outside \(K\) has an outgoing arc to a vertex in \(K\). Thus both checks pass. Conversely, if both checks pass, the first is precisely independence and the second is precisely absorption. Hence \(K\) satisfies the definition of a kernel. \(\square\)
This test suggests a reliable search for all kernels in a small digraph:
Consider subsets of \(V\), using any forced choices to reduce the list. For each proposed \(K\), record its members and the outside vertices.
Inspect the arcs between pairs of members of \(K\). If an arc occurs in either direction, reject \(K\).
For each outside vertex \(v\), inspect \(N_D^+(v)\). The set passes for \(v\) exactly when \(N_D^+(v)\cap K\ne\varnothing\).
Accept \(K\) only if it passes both checks. To rule out kernels, account for every subset that could pass independence and show that each fails absorption, or vice versa.
For \(n\) vertices there are \(2^n\) subsets, since each vertex is either included or excluded. This gives a finite exhaustive method: if all subsets have been checked, no kernel has been missed. In hand calculations, structural constraints can make the list much shorter.
Proof. Let \(v\) have no outgoing arc and suppose a kernel \(K\) omits \(v\). Since \(v\in V\setminus K\), absorption requires an arc \(v\to k\) for some \(k\in K\). This contradicts the assumption that \(v\) has outdegree zero. Therefore \(v\in K\). If there are no such vertices, the statement holds vacuously. \(\square\)
A vertex of outdegree zero is often called a sink. The lemma gives a forced inclusion, but it does not by itself guarantee that a kernel exists. Once a sink is included, any vertex joined to it by an arc in either direction must be excluded by independence. Those exclusions may then make it impossible to absorb some other vertex.
Worked Checks and Exhaustive Searches
Worked Example: Finding All Kernels in a Four-Vertex Digraph
Let \(D\) have \(V=\{1,2,3,4\}\) and \(A=\{1\to2,2\to3,3\to4,4\to1\}\). Find every kernel.
For independence, a pair is forbidden if its vertices are joined by one of the listed arcs. The only pairs with no arc between them are \(\{1,3\}\) and \(\{2,4\}\). No three-vertex set is independent: each three-vertex set contains at least one of the four listed adjacent pairs. Thus the only independent candidates are \(\varnothing\), the four singletons, and those two pairs.
The empty set fails absorption because the graph has outside vertices and no vertex sends an arc to the empty set. Each singleton also fails. For \(K=\{1\}\), vertex \(2\) has \(N_D^+(2)=\{3\}\), which does not meet \(K\). For \(K=\{2\}\), vertex \(3\) has \(N_D^+(3)=\{4\}\), which does not meet \(K\). For \(K=\{3\}\), vertex \(4\) has \(N_D^+(4)=\{1\}\), which does not meet \(K\). For \(K=\{4\}\), vertex \(1\) has \(N_D^+(1)=\{2\}\), which does not meet \(K\).
Now test \(K=\{1,3\}\). Its members have no arc between them. The outside vertices are \(2\) and \(4\): vertex \(2\) sends \(2\to3\), and vertex \(4\) sends \(4\to1\). So this set absorbs every outside vertex. For \(K=\{2,4\}\), the members also have no arc between them; the outside vertices send \(1\to2\) and \(3\to4\). This set also absorbs every outside vertex.
Check: the independent candidates have all been accounted for: one empty set, four singletons and two pairs. The empty set and singletons fail, while both pairs pass, so the complete list of kernels is \(\{1,3\}\) and \(\{2,4\}\).
Worked Example: A Sink Forces the Candidate
Let \(D\) have \(V=\{1,2,3,4\}\) and \(A=\{1\to2,1\to3,2\to3,3\to4\}\). Determine all kernels.
Vertex \(4\) has no outgoing arc, so the lemma forces \(4\) into every kernel. Since \(3\to4\), independence then excludes \(3\). If \(2\) were also excluded, it would be outside the candidate, but its only out-neighbor is \(3\), which has already been excluded. Thus absorption forces \(2\) into the kernel.
Because \(1\to2\), independence excludes \(1\) once \(2\) is included. The forced choices and exclusions leave just \(K=\{2,4\}\). Check it directly: there is no arc between \(2\) and \(4\); the outside vertices are \(1\) and \(3\); and \(1\to2\) and \(3\to4\). So \(K\) is a kernel.
Check: the sink forces \(4\), absorption forces \(2\), and independence excludes both \(3\) and \(1\). These deductions cover every vertex, so no other kernel is possible.
Worked Example: Proving That No Kernel Exists
Let \(D\) have \(V=\{1,2,3\}\) and \(A=\{1\to2,2\to3,3\to1\}\). Decide whether it has a kernel.
Every pair of distinct vertices has an arc between its members: the pairs are \(\{1,2\}\), \(\{2,3\}\), and \(\{1,3\}\). Therefore an independent set can contain at most one vertex. The empty set fails absorption because all three vertices are outside it.
Test the three possible singleton sets. If \(K=\{1\}\), vertex \(2\) is outside and \(N_D^+(2)=\{3\}\), so it has no arc into \(K\). If \(K=\{2\}\), vertex \(3\) is outside and \(N_D^+(3)=\{1\}\), so it has no arc into \(K\). If \(K=\{3\}\), vertex \(1\) is outside and \(N_D^+(1)=\{2\}\), so it has no arc into \(K\). Each candidate fails absorption.
Check: every independent set is either empty or a singleton; the empty set and all three singletons fail. Larger sets fail independence. Hence this digraph has no kernel.
Why Direction and Exhaustiveness Matter
Independence is checked without regard to which way an arc points: either direction between two chosen vertices is enough to disqualify the pair. Absorption, by contrast, is directional. For a vertex \(v\) outside \(K\), the required arc is \(v\to k\), not \(k\to v\). A test that treats arcs as undirected can accept a set that is not a kernel.
For example, in the three-vertex digraph just considered, a mistaken check might claim that \(K=\{1\}\) absorbs vertex \(2\) because \(1\to2\) joins them. But absorption requires an arc from \(2\) into \(K\). Since \(N_D^+(2)=\{3\}\), vertex \(2\) is not absorbed by \(\{1\}\). The correction is to inspect the out-neighborhood of each outside vertex, not the neighbors of the proposed kernel members.
A second common error is to stop after finding one kernel when the question asks for all kernels. A successful candidate proves existence, not uniqueness. To establish that every kernel has been found, either enumerate all subsets that pass independence or use forced choices and exclusions that demonstrably cover all possibilities. Conversely, to prove nonexistence, it is not enough to show that one candidate fails; all possible candidates must be eliminated.
The candidate test is useful because it separates two distinct failure certificates. A candidate can fail independence because of a specific arc between chosen vertices, or fail absorption because of a specific outside vertex whose out-neighborhood misses the candidate. Recording the reason for each rejection makes a small search checkable and makes a claimed kernel easy to verify.
Check Your Understanding
For each question, distinguish the independence check from the absorption check, and keep the direction of each arc explicit.
- In a digraph with \(V=\{a,b,c\}\) and \(A=\{a\to b,b\to c\}\), test whether \(K=\{a,c\}\) is a kernel.
- For the same digraph, list every kernel and justify that your list is complete.
- Prove that if a digraph has a vertex of outdegree zero, its empty set is not a kernel.
- Give a precise reason why an arc \(k\to v\), with \(k\in K\) and \(v\notin K\), does not by itself show that \(v\) is absorbed by \(K\).
- Explain how a failed absorption check can be certified by one vertex and its out-neighborhood.