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.
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.
A directed graph D=(V,A) is kernel-perfect if every induced subdigraph has a kernel.