In this talk I would like to discuss recent developments on the subject of kernels and quasi-kernels in directed graphs.

A kernel is an independent set K in a directed graph such that every vertex is reachable in at most one step from K. A quasi-kernel is a

weakening of the concept of a kernel. A quasi-kernel Q is an independent set in a directed graph such that every vertex can be

reached in at most two steps from Q. While there are simple directed graphs that do not have a kernel (for instance, a directed

triangle) it is a well-known result that every directed graph must have at least one quasi-kernel. A source in a directed graph is

a vertex having only outgoing arcs. It is an open problem since 1976 whether every source-free directed graph has a quasi-kernel

of size at most half of the number of vertices. As shown in the preprint: https://arxiv.org/abs/2110.00789, I have developed a

method to prove that the existence of a kernel implies the existence of a ‘small’ quasi-kernel. In further work, as shown in

https://arxiv.org/abs/2212.12764 I was able to prove that, if the number of sources introduced by the removal of a vertex and

its out-neighborhood can be bounded, every source-free directed graph has a quasi-kernel of size at most the desired bound.

The latter method uses a constructive approach that leads to an algorithm for finding a ‘small’ quasi-kernel