Why Process a Directed Acyclic Graph Backwards?
A kernel is a set of vertices that do not point to one another and that every vertex outside the set can point to. In a directed acyclic graph, these two requirements can be built together: begin at vertices with no outgoing arcs, then work backwards. At each step, select a vertex if none of its out-neighbors has already been selected; otherwise reject it. The order matters because, in a topological order, every arc points forward, so the out-neighbors of a vertex have already been considered when that vertex is processed in reverse.
All directed graphs in this tutorial are finite and have no loops or multiple arcs. Write \(u\to v\) for an arc from \(u\) to \(v\). A directed graph is acyclic if it contains no directed cycle. A topological order of a directed acyclic graph \(G=(V,A)\) is an ordering \(v_1,\ldots,v_n\) of its vertices such that every arc \(v_i\to v_j\) satisfies \(i<j\). Every finite directed acyclic graph has a topological order; this is the topological-ordering result from the earlier material on directed acyclic graphs.
Independence forbids arcs in either direction between two members of \(K\). Absorption is a condition only on vertices outside \(K\). In particular, an isolated vertex must belong to every kernel: if it were outside, it would have no outgoing arc to a vertex in \(K\). The empty directed graph has the empty set as a kernel, since both conditions hold vacuously.
The Reverse-Order Rule
Choose a topological order \(v_1,\ldots,v_n\), and process the vertices as \(v_n,v_{n-1},\ldots,v_1\). Start with \(K=\varnothing\). When processing \(v_i\), select it and add it to \(K\) if none of its out-neighbors is in \(K\). If at least one out-neighbor is already in \(K\), reject \(v_i\) and leave \(K\) unchanged. A vertex is never removed after selection.
List every vertex so each arc points from an earlier vertex to a later one.
Initialize \(K=\varnothing\) and consider vertices in reverse order.
If none is in \(K\), select the vertex. If any is in \(K\), reject it.
Each rejected vertex has a selected out-neighbor; the proof below shows that the final set is independent as well as absorbing.
The essential local test is exact: a vertex is selected precisely when it has no out-neighbor in the set selected so far. Because every out-neighbor comes later in a topological order, the reverse-order procedure has already made all the decisions relevant to that test.
Worked Example: A Diamond-Shaped Directed Acyclic Graph
Let \(G=(V,A)\), where \(V=\{a,b,c,d,e\}\) and \(A=\{a\to b,a\to c,b\to d,c\to d,d\to e\}\). The order \(a,b,c,d,e\) is topological: each listed arc points from an earlier vertex to a later one. Process the vertices in the order \(e,d,c,b,a\).
| Vertex processed | Out-neighbors | Out-neighbors already in \(K\) | Decision | \(K\) after decision |
|---|---|---|---|---|
| \(e\) | None | None | Select | \(\{e\}\) |
| \(d\) | \(\{e\}\) | \(\{e\}\) | Reject | \(\{e\}\) |
| \(c\) | \(\{d\}\) | None | Select | \(\{e,c\}\) |
| \(b\) | \(\{d\}\) | None | Select | \(\{e,c,b\}\) |
| \(a\) | \(\{b,c\}\) | \(\{b,c\}\) | Reject | \(\{e,c,b\}\) |
The algorithm returns \(K=\{b,c,e\}\). To check independence, inspect the arc set: \(a\to b\), \(a\to c\), \(b\to d\), \(c\to d\), and \(d\to e\) each has at least one endpoint outside \(K\), so none has both endpoints in \(K\). The vertices outside \(K\) are \(a\) and \(d\); the arcs \(a\to b\) and \(d\to e\) show that each has an outgoing arc into \(K\). Thus \(K\) satisfies both kernel conditions.
Worked Example: A Directed Chain
Let \(G=(V,A)\), where \(V=\{p,q,r,s\}\) and \(A=\{p\to q,q\to r,r\to s\}\). The order \(p,q,r,s\) is topological. Process \(s,r,q,p\).
| Vertex processed | Out-neighbors | Out-neighbors already in \(K\) | Decision | \(K\) after decision |
|---|---|---|---|---|
| \(s\) | None | None | Select | \(\{s\}\) |
| \(r\) | \(\{s\}\) | \(\{s\}\) | Reject | \(\{s\}\) |
| \(q\) | \(\{r\}\) | None | Select | \(\{s,q\}\) |
| \(p\) | \(\{q\}\) | \(\{q\}\) | Reject | \(\{s,q\}\) |
The output is \(K=\{q,s\}\). There is no arc between \(q\) and \(s\), so \(K\) is independent. The outside vertices are \(p\) and \(r\), and their arcs \(p\to q\) and \(r\to s\) enter \(K\). Hence the output is a kernel. This example also shows why not every vertex is selected: a selected out-neighbor is a reason to reject the current vertex.
Worked Example: Disconnected Vertices and an Isolated Vertex
Let \(G=(V,A)\), where \(V=\{u,v,w,x,z\}\) and \(A=\{u\to w,v\to w,w\to x\}\). The vertex \(z\) is isolated. One topological order is \(u,v,w,x,z\), so process \(z,x,w,v,u\).
| Vertex processed | Out-neighbors | Out-neighbors already in \(K\) | Decision | \(K\) after decision |
|---|---|---|---|---|
| \(z\) | None | None | Select | \(\{z\}\) |
| \(x\) | None | None | Select | \(\{z,x\}\) |
| \(w\) | \(\{x\}\) | \(\{x\}\) | Reject | \(\{z,x\}\) |
| \(v\) | \(\{w\}\) | None | Select | \(\{z,x,v\}\) |
| \(u\) | \(\{w\}\) | None | Select | \(\{z,x,v,u\}\) |
The returned set is \(K=\{z,x,v,u\}\). The listed arcs all have an endpoint outside \(K\): \(u\to w\), \(v\to w\), and \(w\to x\). Thus the set is independent. The only outside vertex is \(w\), and \(w\to x\) enters \(K\), so the set is absorbing. The isolated vertex is selected, as required by the definition.
Why the Algorithm Always Works
Proof. Suppose \(K\) is a kernel. If \(v\in K\), independence forbids an arc from \(v\) to any vertex in \(K\), so no out-neighbor of \(v\) belongs to \(K\). If \(v\notin K\), absorption gives an arc \(v\to k\) for some \(k\in K\), so \(v\) does have an out-neighbor in \(K\). These two cases prove the stated equivalence for every vertex. \(\square\)
Proof. Let \(G=(V,A)\) be a finite directed acyclic graph with topological order \(v_1,\ldots,v_n\), and let \(K\) be the set produced by the algorithm. If \(V=\varnothing\), the algorithm returns \(K=\varnothing\); independence and absorption are both vacuous, and this is the only subset of \(V\). Now suppose \(V\ne\varnothing\).
First, \(K\) is independent. Suppose instead that an arc \(v_i\to v_j\) has both endpoints in \(K\). The topological-order condition gives \(i<j\), so \(v_j\) was processed before \(v_i\). Since \(v_j\) was selected and remains in \(K\), when \(v_i\) was processed it had the selected out-neighbor \(v_j\). The rule would therefore have rejected \(v_i\), contrary to \(v_i\in K\). Thus no arc has both endpoints in \(K\).
Next, \(K\) is absorbing. Every vertex outside \(K\) was rejected. The rule rejects a vertex only if it has an out-neighbor already in \(K\). Since selected vertices are never removed, that out-neighbor remains in the final \(K\). Therefore every vertex outside \(K\) has an arc into \(K\). The two conditions show that \(K\) is a kernel.
To prove uniqueness, let \(K'\) be any kernel. Consider the vertices in reverse topological order. When processing \(v_i\), all its out-neighbors occur later in the topological order, so their membership in \(K'\) has already been determined in this reverse-order comparison. By the Lemma, \(v_i\in K'\) exactly when none of those out-neighbors belongs to \(K'\). This is precisely the algorithm's selection rule. Starting with the last vertex and applying this reasoning at each step forces the same membership decision as the algorithm for every vertex. Hence \(K'=K\), proving uniqueness. \(\square\)
The proof also explains the method's structure. Rejection supplies the absorption witness immediately: a selected out-neighbor. Processing backwards ensures that the algorithm has already decided whether every possible witness is selected. Independence follows because a vertex cannot be selected after one of its out-neighbors has entered the set.
Common Pitfall: Using the Same Rule in Forward Order
The rule depends on processing direction. Consider the directed graph \(G=(V,A)\) with \(V=\{x,y\}\) and \(A=\{x\to y\}\). Its topological order is \(x,y\). If the selection rule is incorrectly applied in this forward order, \(x\) is selected because it has no out-neighbor in the initially empty set. Then \(y\) is selected because it has no out-neighbors at all. The resulting set \(\{x,y\}\) is not independent: the arc \(x\to y\) has both endpoints in the set.
In reverse order, \(y\) is processed first and selected. When \(x\) is processed, its out-neighbor \(y\) is already selected, so \(x\) is rejected. The result \(\{y\}\) is independent, and the only outside vertex \(x\) has the arc \(x\to y\) into the set. The correction is not to change the local rule, but to process vertices in reverse topological order.
Implementation and Interpretation
With an adjacency list, the decision for a vertex can be made by checking its outgoing arcs and testing whether any endpoint is already selected. Across the full run, each vertex is processed once and each arc is checked at most once, so the work is proportional to \(|V|+|A|\), provided the topological order is already available. The output is not merely a set that happens to satisfy the definition: the proof shows that the forced decision rule gives the unique kernel of the directed acyclic graph.
Disconnected components need no special adjustment. A topological order covers every vertex, including isolated vertices, and the same rule processes them. Equivalently, decisions in one component cannot affect another because there are no arcs between components. The empty graph is also covered: it has no vertices to process and the returned empty set is its kernel.
Check Your Understanding
For each question, use the arc direction as written and justify each selection or rejection by the reverse-order rule.
- For \(V=\{a,b,c\}\) and \(A=\{a\to b,b\to c\}\), process the vertices in reverse topological order and give the kernel.
- For \(V=\{r,s,t\}\) and \(A=\{r\to t,s\to t\}\), use the order \(r,s,t\). Which vertices are selected?
- Explain why a rejected vertex remains absorbed even though later decisions may add more vertices to \(K\).
- In the uniqueness proof, why have all out-neighbors of the current vertex already had their membership decisions determined?
- Show directly that the empty directed graph has a unique kernel.