# 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.