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