Kernel (in digraph)

In a directed graph D=(V,A), a kernel is an independent set [math]X \subseteq V[/math] with the property that for each node [math]u \in V \setminus X[/math] there is a node [math]v \in X[/math] such that [math]uv \in A[/math].

A quasi-kernel in D is an independent set [math]Y \subseteq V[/math] with the property that for each node [math]u \in V \setminus Y[/math] there is a directed path of length at most two which starts at u and ends at a node of Y.

Kernel-solvability

Let G be an undirected graph. A superorientation of G is a directed graph obtained by orienting each edge of G either in one direction or both ways. A superorientation is clique-acyclic if in every clique of G the subdigraph of one-way arcs is acyclic.

The undirected graph G is said to be kernel-solvable if every clique-acyclic superorientation of G has a kernel.

Kernel-perfectness

A directed graph D=(V,A) is kernel-perfect if every induced subdigraph has a kernel.