# Kernel (in digraph)

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

A quasi-kernel in D is an independent set $Y \subseteq V$ with the property that for each node $u \in V \setminus Y$ 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.