P487: Enumeration of all kernels in a directed graph $G$

P487: Enumeration of all kernels in a directed graph $G$

Input:

A directed graph $G$.

Output:

All kernels in $G$.

Complexity:

Since the decision problem is NP-hard, the algorithm may need exponential time per solution.

Comment:

An independent set $S$ of $G$ is a kernel if every vertex $G$ can reach $S$ by a directed path with length at most one.

Reference:

[Frangakis1981] (Bibtex)