Small and Large Quasi-Kernels in General Digraphs

Source abstract

In a digraph $D$, a set $Q$ of vertices is a quasi-kernel if $Q$ is an independent set and every vertex in $D$ can be reached from $Q$ via at most two edges. The small quasi-kernel conjecture by Erdős and Székely predicts that every source-free $n$-vertex digraph contains a quasi-kernel of size at most $n - n/2$. Chvátal and Lovász' 1974 work implies a bound of $n - \sqrt{n}+1$. In 2024, Sprio shows the bound $n - \frac{1}{4} \sqrt{n \log_2 n}$. We show that there always is a quasi-kernel of size at most $n - \frac{1}{51}n^{2/3} / \ln^{2/3}(n)$. For the related large quasi-kernel conjecture by Spiro, we show that there always is a quasi-kernel $Q$ with $|N^+[Q]| \ge 0.2917 \cdot n^{2/3} / \ln^{2/3}(n)$.