The Small Quasikernel Conjecture

Let $D$ be a finite digraph. A quasikernel is an independent set $Q\subseteq V(D)$ such that every vertex $x\in V(D)$ satisfies $\operatorname{dist}(Q,x)\le 2$. The digraph $D$ is source-free if it has no vertex of in-degree $0$.

Small Quasikernel Conjecture. If $D$ is a source-free digraph, then $D$ contains a quasikernel $Q$ with

$$|Q|\le\frac{1}{2}|V(D)|.$$

This conjecture, due to P. L. Erdős and Székely, asks for a sharp universal upper bound on the size of a quasikernel in source-free digraphs. It is presented here as an open problem.