Graph / Kernel (Bibtex)

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)

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.

Reference:

[Szwarcfiter1994] (Bibtex)