A quasi-kernel of a directed graph is an independent vertex set from which every graph vertex is reachable by a directed graph path of length at most two. This convention directs paths away from the quasi-kernel. The reverse convention is obtained by reversing all directed edges (Ai et al. 2026).
Chvátal and Lovász (1974) introduced quasi-kernels under the name semi-kernels and proved that every finite directed graph has a quasi-kernel. Neumann-Lara's semikernel uses a return-edge condition. Erdős et al. (2025) survey the small quasi-kernel conjecture and its relation to the ordinary kernel problem.
The small quasi-kernel conjecture asserts that every source-free directed graph on 
vertices has a quasi-kernel of size at most 
. Source-free means that every graph
vertex has positive indegree. The large quasi-kernel
conjecture asserts that every directed graph has
a quasi-kernel whose closed out-neighborhood contains at least half its vertices.
This neighborhood consists of the quasi-kernel and all vertices
reached from it by one directed edge. Ai et al.
(2026) proved that these two universal conjectures are equivalent. Neither is
thereby proved. Their conventions allow opposite directed
edges but exclude graph loops and parallel directed
edges.
