Kernels are defined as subsets of vertices which are independent and ``absorbing" (every vertex outside the subset has at least one outneighbor in the subset). Initially introduced by von Neumann and Morgenstern for game theory, they have also found applications in economics and logic. The existence of kernels in a digraph is not systematic and is even NP-complete to decide. The first part of this presentation aims to explore the challenges and theoretical aspects of kernels.
The notion of quasi-kernels, which was introduced by Chvátal and Lovász in 1974, derives from a slight modification in the definition of kernels. A quasi-kernel is a subset of vertices that is independent and such that there is a directed path of length at most two from every vertex to that subset. Any digraph has a quasi-kernel that can be found in polynomial time.
The research about quasi-kernels focuses on a conjecture called the ``small quasi-kernel conjecture." It suggests that a sink-free digraph (where every vertex has a positive outdegree) has a quasi-kernel of size at most half of the vertex set. However, this conjecture is only confirmed for specific classes of digraphs.
The second half of the presentation focuses on quasi-kernels, on their algorithmic aspect and strategies of proofs for the small quasi-kernel conjecture.

In a directed graph, a kernel is a subset of vertices that is independent and absorbing. Kernels form a fundamental topic of the theory of directed graphs, and appear in a variety of contexts: logic, game theory, economics, and others. Not all graphs possess a kernel and deciding the existence of a kernel is NP-complete. Among the most fundamental results ensuring existence of a kernel are the famous theorems of Sands, Sauer, and Woodrow (1982) and of Galeana-Sánchez and Neumann-Lara (1984). In this talk, we will discuss extensions of these theorems and some challenges they pose.

A subset Q of the vertices of a directed graph is a quasi-kernel (QK for short)
if it is independent and the shortest path to every vertex from Q is of length at
most two. Chvátal and Lovász proved in 1974 that all digraphs in fact possess QK.
Maybe it is characteristic, that almost any raised problem (like finding a minimum QK)
proved to be NP-hard. In this lecture I will survey in short the literature about QK.

Along the way I will talk about the small QK conjecture, which states that every
source-free digraph has a QK of size at most half of its size (Erdös and Székely,
1976). There is a growing list of partial results, but the end seems to be far
away. I also will mention the large quasi-kernel conjecture of Sam Spiro, 2024.

It is easy to see that the Chvátal-Lovász's theorem does not hold for countable
infinite digraphs. Therefore, if the time's limit allows, I will talk about
infinite quasi-kernel conjecture (Erdös-Soukup, 2008).