P486: Enumeration of all kernels in a directed graph
P486: Enumeration of all kernels in a directed graph
Input:
A directed graph $G = (V, E)$ with no odd cycles.
Output:
All kernels in $G$.
Complexity:
$O(|V||E|(k + 1))$ total time.
Comment:
$k$ is the number of solutions. A vertex subset $S$ is a kernel of $G$ if $S$ is an independent set and every vertex in $G$ can reach $S$ by a directed path of length at most
one.