Greedily Constructing Small Quasi-Kernels

Abstract

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)\le 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-\hat{I}\mu )n$ known. We introduce a polynomial time algorithm which greedily constructs a small quasi-kernel. Using this algorithm we show that if $D$ is a ${\vec{K}}_{1,d}$-free digraph, then $D$ has a quasi-kernel of order at most $\frac{(d^2-2d+2)n}{d^2-d+1}$. By refining this argument we prove that for any $D$ with maximum out-degree $3$ this algorithm constructs a quasi-kernel of order at most $4n/7$. Finally, we consider the problem in digraphs forbidding certain orientation of short cycles as subgraphs, concluding that all orientations $D$ of a graph $G$ with girth at least $7$ have a quasi-kernel of order at most $\frac{(d^2+4)n}{(d+2{)}^2}$, where $d$ is the maximum out-degree of $D$.

22 pages, 3 figures, 1 table