{"id":"arxiv/2601.11847","url":"https://arxiv.org/abs/2601.11847","tags":["math.CO"],"score":0,"title":"Greedily Constructing Small Quasi-Kernels","domain":"math.CO","source":"arxiv","authors":["Alexander Clow"],"reviews":0,"subject":"math.CO","summary":"In a digraph $D$,a quasi-kernel is an independent set $Q$ such that for every vertex $u$, there is a vertex $v \\in Q$ satisfying $\\text{dist}(v,u)\\leq 2$. In 1974 Chvátal and Lovász showed every digraph contains a quasi-kernel. In 1976, P. L. Erdős and Székely conjectured that every sourceless digraph has a quasi-kernel of order at most $\\frac{n}{2}$. Despite significant recent attention by the community the problem remains far from solved, with no bound of the form $(1-ε)n$ known. We introduce a polynomial time algorithm which greedily constructs a small quasi-kernel. Using this algorithm…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-17","reactions":{}}