# Generalized Quasikernels in Digraphs

Sam Spiro111Dept. of Mathematics, Rutgers University
<EMAIL_ADDRESS>This material is based upon work supported by
the National Science Foundation Mathematical Sciences Postdoctoral Research
Fellowship under Grant No. DMS-2202730.

###### Abstract

Given a digraph $D$, we say that a set of vertices $Q\subseteq V(D)$ is a
$q$-kernel if $Q$ is an independent set and if every vertex of $D$ can be
reached from $Q$ by a path of length at most $q$. In this paper, we initiate
the study of several extremal problems for $q$-kernels. For example, we
introduce and make progress on (what turns out to be) a weak version of the
Small Quasikernel Conjecture, namely that every digraph contains a $q$-kernel
with $|N^{+}[Q]|\geq\frac{1}{2}|V(D)|$ for all $q\geq 2$.

##  1 Introduction

This paper concerns problems about (finite) digraphs, for which we recall a
few basic definitions. Given vertices $u,v$ of a digraph $D$, we define
$\mathrm{dist}(u,v)$ to be the length of a shortest directed path from $u$ to
$v$, and for a set of vertices $S$, we define $\mathrm{dist}(S,v)=\min_{u\in
S}\mathrm{dist}(u,v)$. We say a set of vertices $S$ is independent if there
exist no arcs between two vertices of $S$.

The following (less basic) objects will be the starting point for this paper.

######  Definition 1.

A set of vertices $K$ of a digraph $D$ is said to be a kernel if (1) $K$ is an
independent set and (2) $\mathrm{dist}(K,x)\leq 1$ for all $x\in V(D)$ (that
is, every vertex $x\in V(D)$ is either contained in $K$ or has a vertex of $K$
as an in-neighbor).

######  Definition 2.

A set of vertices $Q$ of a digraph $D$ is said to be a quasikernel if (1) $Q$
is an independent set and (2) $\mathrm{dist}(Q,x)\leq 2$ for all $x\in V(D)$
(that is, every vertex $x\in V(D)$ can be reached from $Q$ by a directed path
of length at most 2).

The concept of kernels was introduced by Von Neumann and Morgenstern [12] in
relation to problems from game theory. Not every digraph contains a kernel
(for example, a directed 3-cycle does not), but it turns out that every
digraph has a quasikernel, as was originally shown by Chvátal and Lovász [2].

Because every digraph contains a quasikernel, it is natural to ask extremal
type problems about the set of quasikernels for a given digraph. One
conjecture in this direction is the Small Quasikernel Conjecture due to P.L.
Erdős and Székely [3], where here we recall a digraph is source-free if it
contains no vertices with in-degree 0.

######  Conjecture 1.1 (Small Quasikernel Conjecture).

If $D$ is a source-free digraph, then $D$ contains a quasikernel $Q$ with
$|Q|\leq\frac{1}{2}|V(D)|$.

The source-free condition is necessary for the conclusion
$|Q|\leq\frac{1}{2}|V(D)|$ to hold, as can be seen by considering, for
example, $D$ to be a digraph with no arcs. The bound $\frac{1}{2}|V(D)|$ is
best possible, as can be seen by considering (disjoint unions of) directed
2-cycles and 4-cycles.

The Small Quasikernel Conjecture seems difficult, with very little progress
being made between its original statement in 1976 and 2020. However, since
2020, there have been a number of results solving the Small Quasikernel in a
few special cases [1, 8, 9, 11], with this recent increase in popularity
largely due to work of Kostochka, Luo, and Shan [6] who (in particular) showed
that 4-chromatic digraphs satisfy the Small Quasikernel Conjecture. We provide
our own small step towards the Small Quasikernel Conjecture here by proving
what appears to be the first general bound for the size of the smallest
quasikernel in source-free digraphs.

######  Proposition 1.2.

If $D$ is a source-free digraph, then $D$ contains a quasikernel with

$|Q|\leq|V(D)|-\lfloor|V(D)|^{1/2}\rfloor.$

This bound is tight for directed 2-cyles and 4-cycles, with the former example
showing that one can not strengthen 1.2 by dropping its floor.

Much more can be said about the Small Quasikernel Conjecture, and we refer the
interested reader to the nice survey by P.L. Erdős, Győri, Mezei, Salia, and
Tyomkyn [4] for a more thorough overview of this problem.

##  2 Main Results

We introduce a natural generalization of kernels and quasikernels which does
not appear to have been considered within the context222Our definition of
$q$-kernels are a special case of the more general notion of a
$(k,\ell)$-kernel due to Kwásnik and Borowiecki [7] which is studied a fair
amount. However, the results for $(k,\ell)$-kernels are mostly focused on
existence questions rather than extremal problems, and our particular
definition of $q$-kernels does not appear to have been given any special
attention in this setting. of the Small Quasikernel Conjecture.

######  Definition 3.

Given an integer $q\geq 1$ and a digraph $D$, we say that a set of vertices
$Q\subseteq V(D)$ is a $q$-kernel if $Q$ is independent and if
$\mathrm{dist}(Q,v)\leq q$ for every vertex $v\in V(D)$.

For example, 1-kernels are kernels and 2-kernels are quasikernels.

In view of the Small Quasikernel Conjecture, it is natural to ask how small of
a $q$-kernel one can find in source-free digraphs. Unlike with quasikernels,
this problem turns out to be quite easy for $q\geq 3$. Indeed, in Section 5 we
will show the following.

######  Proposition 2.1.

If $D$ is a source-free digraph and $q\geq 3$, then $D$ contains two disjoint
$q$-kernels. In particular, $D$ contains a $q$-kernel of size at most
$\frac{1}{2}|V(D)|$.

This result is best possible by considering disjoint unions of directed
2-cycles. This result does not hold for $q=2$, i.e. there exist source-free
digraphs such that every two quasikernels intersect each other, as was
originally proven by Gutin, Koh, Tay, and Yeo [5].

Although 2.1 solves the most natural analog of 1.1, it also serves as the
starting point for many new problems which we explore further below. In
particular, we study the more general problem of finding $r$ disjoint
$q$-kernels in digraphs, as well as strengthening the bound of 2.1 when extra
structural information for $D$ is assumed. In addition to this, we introduce
(what turns out to be) a weak version of the Small Quasikernel Conjecture and
make some progress towards this problem, especially in the setting of
$q$-kernels.

###  2.1 Disjoint $q$-kernels

Here we study the problem of finding $r$ disjoint $q$-kernels in a digraph
$D$. One immediate obstacle is the following structure, where here and
throughout we define the open in-neighborhood of a set $S$ by

$N^{-}_{D}(S):=\\{u\in V(D)\setminus S:\exists v\in S,\ uv\in E(D)\\}.$

######  Definition 4.

Given a digraph $D$, we say that a set of vertices $S\subseteq V(D)$ is a
source set if $N^{-}(S)=\emptyset$. We say that $S$ is an $s$-source set if
$S$ is non-empty and $|S|\leq s$.

For example, 1-source sets are just sources.

Observe that if $D$ contains an $(r-1)$-source set $S$, then it does not
contain $r$ disjoint $q$-kernels for any $q$. Indeed, every $q$-kernel needs
to use at least one vertex of $S$, and hence $D$ can contain at most $|S|<r$
disjoint $q$-kernels.

It is not difficult to show that $(r-1)$-source sets are the only obstruction
for $D$ containing $r$ disjoint $q$-kernels for some $q\leq|V(D)|$. With more
work, one can significantly improve upon this trivial bound $q\leq|V(D)|$.

######  Theorem 2.2.

If a digraph has no $(r-1)$-source sets, then it contains $r$ disjoint
$2^{r+1}$-kernels.

In other words, if a digraph contains $r$ disjoint $q$-kernels for some $q$,
then it in fact contains $r$ disjoint $2^{r+1}$-kernels. We will ultimately
prove a somewhat stronger result which guarantees disjoint sets
$Q_{1},\ldots,Q_{r}$ such that each $Q_{i}$ is a $q_{i}$-kernel with
$q_{i}\approx i\cdot 2^{r-i}$; see 5.2 for more.

###  2.2 Smaller $q$-kernels

The examples showing sharpness of 1.1 and 2.1 both involve disjoint unions of
directed 2-cycles or 4-cycles. As such, it is reasonable to ask if these
bounds can be improved if $D$ avoids certain cycle lengths. A reasonable guess
here would be the following.

######  Question 2.3.

Let $q\geq 2$ be an integer and let $D$ be a source-free digraph with $L(D)$
the set of $\ell$ such that $D$ contains a directed $\ell$-cycle. Is it true
that $D$ contains a $q$-kernel $Q$ such that

$|Q|\leq\max_{\ell\in L(D)}\frac{\lceil\ell/(q+1)\rceil}{\ell}\cdot|V(D)|?$

Observe that this upper bound is tight if $D$ is the disjoint union of
directed $\ell$-cycles. Also observe that $D$ being source-free implies
$L(D)\neq\emptyset$, so this maximum is well defined.

We suspect 2.3 is too ambitious to be true in general. We are, however, able
to verify a few cases of 2.3 when our digraph is bipartite, which is analogous
to the work of [6] solving the Small Quasikernel Conjecture for digraphs of
chromatic number at most 4. To this end, we say a partition $U,V$ of $V(D)$ is
a bipartition of $D$ if every arc has exactly one vertex in $U$ and exactly
one vertex in $V$, and we say that $D$ is bipartite if it has a bipartition.

For quasikernels in bipartite digraphs, we can prove the simplest non-trivial
statement which agrees with 2.3.

######  Proposition 2.4.

If $D$ is a source-free bipartite digraph which has no directed 2-cycles or
4-cycles, then $D$ contains a quasikernel $Q$ with $|Q|<\frac{1}{2}|V(D)|$.

Observe that the bound $|Q|\leq\frac{1}{2}|V(D)|$ is trivial by taking $Q$ to
be the smaller part of the bipartition, but some work is required in order to
use the cycle hypothesis on $D$ to improve this trivial bound.

2.3 predicts that the conclusion of 2.4 should hold with
$|Q|\leq\frac{2}{5}|V(D)|$ (due to $\ell=10$), so the bound of 2.4 is quite
far from sharp. However, if one shifts from quasikernels to the setting of
$q$-kernels with $q>2$, then one can prove sharp results when the smallest
cycle length is small relative to $q$.

######  Theorem 2.5.

Let $D$ be a source-free bipartite digraph with bipartition $U\cup V$. If
$q,\ell\geq 3$ are integers such that $\ell\leq(q+3)/2$ and such that every
directed cycle of $D$ has length at least $\ell$, then $D$ contains a
$q$-kernel $Q$ of size at most $\frac{1}{\ell}|V(D)|$ with $Q\subseteq U$.

For example, taking $q=\ell=3$ implies that every bipartite digraph without
directed 2-cycles contains a 3-kernel of size at most $\frac{1}{3}|V(D)|$,
which is best possible by considering directed 6-cycles. More generally, the
bound for $Q$ in 2.5 is best possible and matches what 2.3 predicts if $D$ is
the disjoint union of directed $\ell$-cycles when $\ell$ is even (the even
condition making $D$ bipartite), or if $D$ is the disjoint union of directed
$2\ell$-cycles when $2\ell\geq q+2$.

We suspect that one can extend our approach for 2.5 to verify 2.3 for a larger
class of bipartite digraphs. However, it is not possible to solve 2.3 in full
for bipartite digraphs if we continue imposing the additional condition
$Q\subseteq U$ in 2.5 (which will turn out to be vital to our proof); see
Appendix A for some concrete examples of this.

###  2.3 Large $q$-kernels

This subsection studies the problem of finding “large” $q$-kernels in
digraphs. The most straightforward problem of trying to maximize $|Q|$ amongst
$q$-kernels $Q$ is not interesting, as $|Q|$ could be as small as 1 if $D$ is
a tournament. However, this problem becomes interesting if we change how we
measure $Q$. To this end, we denote the closed out-neighborhood of a set
$S\subseteq V(D)$ by

$N^{+}[S]=S\sqcup N^{+}(S)=S\cup\\{v:\exists u\in S,\ uv\in E(D)\\}.$

######  Conjecture 2.6 (Large Quasikernel Conjecture).

Every digraph $D$ contains a quasikernel $Q$ with
$|N^{+}[Q]|\geq\frac{1}{2}|V(D)|$.

This bound is asymptotically best possible by considering $Q$ to be an
Eulerian touranment. The main motivation for this conjecture is the following.

######  Proposition 2.7.

The Small Quasikernel Conjecture implies the Large Quasikernel Conjecture.

As such, the Large Quasikernel Conjecture can be seen as a weak version of the
Small Quasikernel Conjecture. We are able to take a modest step towards the
Large Quasikernel Conjecture, with us making significantly more progress for
3-kernels.

######  Theorem 2.8.

Let $D$ be a digraph.

  * (a)

There exists a quasikernel $Q$ with $|N^{+}[Q]|\geq|V(D)|^{1/3}$.

  * (b)

There exists a 3-kernel $Q$ with $|N^{+}[Q]|\geq\frac{1}{3}|V(D)|$.

###  2.4 Organization and Conventions

Our proofs are broken into four essentially independent sections organized by
increasing levels of technical detail: we begin with our general upper bound
for quasikernels in Section 3, our results about large $q$-kernels in Section
4, our results about disjoint $q$-kernels in Section 5, and our results about
bipartite digraphs in Section 6. We close the paper with a large number of
open problems in Section 7 along with an Appendix A discussing technical
avenues for refining our results further.

Throughout the text, we always assume that our digraphs are finite. Our proofs
will sometimes use without comment the fact that every digraph contains a
quasikernel. We let $C_{\ell}$ denote the directed $\ell$-cycle, i.e. the
digraph with vertices $v_{1},\ldots,v_{\ell}$ and arcs $v_{i}v_{i+1}$ for all
$1\leq i\leq\ell$ (with these indices written cyclically).

##  3 Proof of 1.2: Small Quasikernels

We begin with a simple lemma that will be used in the next section as well.

######  Lemma 3.1.

For every digraph $D$ and $x\in V(D)$, there exists a quasikernel $Q$ of $D$
such that $Q\cap N^{+}(x)=\emptyset$ and $Q\cap N^{-}[x]\neq\emptyset$.

###### Proof.

Let $D^{\prime}=D-N^{+}[x]$ and let $Q^{\prime}$ be any quasikernel of
$D^{\prime}$, noting that $Q^{\prime}\cap N^{+}(x)=\emptyset$ by construction.
If $Q^{\prime}\cap N^{-}(x)\neq\emptyset$, then it is straightforward to show
that $Q^{\prime}$ is a quasikernel for $D$ which intersects $N^{-}[x]$. If
instead $Q^{\prime}\cap N^{-}(x)=\emptyset$, then $Q=Q^{\prime}\cup\\{x\\}$ is
an independent set, and it is not difficult to see that $Q$ is a quasikernel
which satisfies $Q\cap N^{+}(x)=\emptyset$ and $Q\cap N^{-}[x]\neq\emptyset$,
giving the result. ∎

We also need the following observation.

######  Lemma 3.2.

If $D$ is a digraph with minimum in-degree $\delta$ and maximum out-degree
$\Delta$, then every independent set $I$ of $D$ satisfies

$|I|\leq|V(D)|-\frac{\delta}{\delta+\Delta}|V(D)|.$

###### Proof.

Let $I$ be an independent set and let $D^{\prime}\subseteq D$ be the
subdigraph consisting only of the arcs that go from $V(D)\setminus I$ to $I$.
Because $I$ is independent, each $v\in I$ has
$\deg_{D^{\prime}}^{-}(v)=\deg_{D}^{-}(v)\geq\delta$. From this we conclude

$\delta|I|\leq\sum_{v\in I}\deg_{D^{\prime}}^{-}(v)=\sum_{u\in V(D)\setminus
I}\deg_{D^{\prime}}^{+}(u)\leq\Delta(|V(D)|-|I|).$

Rearranging gives the result. ∎

We now prove our general bound for small quasikernels.

###### Proof of 1.2.

Recall that we wish to show that if $D$ is a source-free digraph, then $D$
contains a quasikernel $Q$ with $|Q|\leq|V(D)|-\lfloor|V(D)|^{1/2}\rfloor$.

First consider the case that $D$ contains a vertex $x$ with out-degree at
least $\lfloor|V(D)|^{1/2}\rfloor$. By 3.1, there exists a quasikernel $Q$
disjoint from $N^{+}(x)$, so

$|Q|\leq|V(D)|-|N^{+}(x)|\leq|V(D)|-\lfloor|V(D)|^{1/2}\rfloor,$

proving the bound.

We now assume $D$ has maximum out-degree at most
$\lfloor|V(D)|^{1/2}\rfloor-1$, noting that the source-free condition is
equivalent to saying that $D$ has minimum in-degree at least 1. By 3.2, any
independent set (and in particular, any quasikerenl) has size at most

$|V(D)|-\frac{1}{\lfloor|V(D)|^{1/2}\rfloor}|V(D)|\leq|V(D)|-|V(D)|^{1/2},$

proving the result. ∎

As an aside, this same approach can be used to show that digraphs with minimum
in-degree $\delta$ contain quasikernels of size at most
$|V(D)|-\sqrt{\delta|V(D)|}+\delta$; see also the discuss around 7.4 for
problems related to this.

##  4 Proof of 2.8: Large $q$-kernels

We begin by proving 2.7, which we recall says that the Small Quasikernel
Conjecture implies the Large Quasikernel Conjecture, i.e. that if every
source-free digraph contains a quasikernel with $|Q|\leq\frac{1}{2}|V(D)|$,
then every digraph contains a quasikernel with
$|N^{+}[Q]|\geq\frac{1}{2}|V(D)|$.

###### Proof of 2.7.

Let $D$ be a minimal counterexample to the Large Quasikernel Conjecture. If
$D$ contains a source $v$, then $D$ being a minimal counterexample implies we
can find a quasikernel $Q^{\prime}$ in $D^{\prime}=D-N^{+}_{D}[v]$ with

$|N^{+}_{D^{\prime}}[Q^{\prime}]|\geq\frac{1}{2}(|V(D)|-|N^{+}_{D}[v]|).$

One can then verify that $Q:=Q^{\prime}\cup\\{v\\}$ is a quasikernel of $D$
and that

$|N^{+}_{D}[Q]|=|N^{+}_{D^{\prime}}[Q^{\prime}]|+|N^{+}_{D}[v]|\geq\frac{1}{2}|V(D)|,$

giving the result. Thus we may assume $D$ is source-free.

Let $k$ be a large integer to be determined later and define a digraph
$D^{\prime}$ by taking each vertex $v\in V(D)$ and adding $k$ new vertices
$v_{1},\ldots,v_{k}$ together with the arcs $vv_{i}$ for all $i$. Let
$Q^{\prime}$ be a smallest quasikernel of $D^{\prime}$, noting that
$|Q^{\prime}|\leq\frac{1}{2}|V(D^{\prime})|=\frac{k+1}{2}|V(D)|$ by hypothesis
of the Small Quasikernel Conjecture holding.

It is not difficult to verify that $Q:=Q^{\prime}\cap V(D)$ is a quasikernel
of $D$ and that $Q^{\prime}\setminus Q=Q^{\prime}\setminus V(D)$ contains
every vertex $v_{i}$ with $v\in V(D)\setminus N^{+}_{D}[Q]$ (as otherwise
$Q^{\prime}$ would not be a quasikernel for $D^{\prime}$). These observations
imply

$\frac{k+1}{2}|V(D)|\geq|Q^{\prime}|\geq|Q^{\prime}\setminus Q|\geq
k(|V(D)|-|N^{+}_{D}[Q]|),$

and rearranging gives

$|N^{+}[Q]|\geq\frac{1}{2}|V(D)|-\frac{1}{2k}|V(D)|.$

Since $|N^{+}[Q]|$ is an integer, this implies
$|N^{+}[Q]|\geq\lceil\frac{1}{2}|V(D)|-\frac{1}{2k}|V(D)|\rceil$ for all
$k\geq 1$. By taking any $k>|V(D)|$, we see that this ceiling is at least
$\frac{1}{2}|V(D)|$, proving the result.

∎

We now prove that digraphs have $q$-kernels with $|N^{+}[Q]|$ relatively
large. The following observations will be useful, where here we say an
independent set $S$ is maximal if $S\cup\\{v\\}$ is not independent for all
$v\notin S$ and that a digraph is acyclic if it contains no directed cycles.

######  Lemma 4.1.

Let $D$ be a digraph.

  * (a)

If every vertex of $D$ has out-degree at most $\Delta$, then there exists a
set $A\subseteq V(D)$ such that $D[A]$ is acyclic with
$|A|\geq\frac{|V(D)|}{\Delta+1}$.

  * (b)

There exists a maximal independent set $S$ with
$|N^{+}[S]|\geq\frac{1}{2}|V(D)|$.

As an aside, 4.1(b) can be viewed as a very weak version of the Large
Quasikernel Conjecture (as the Large Quasikernel Conjecture requires finding
such a set which is additionally a quasikernel).

###### Proof.

For (a), let $A$ be a largest set such that $D[A]$ is acyclic, noting that at
least one such set exists by considering $A=\emptyset$. If
$|A|<\frac{|V(D)|}{\Delta+1}$, then there exists some vertex $v\notin
N^{+}[A]$ (since $N^{+}[A]$ has size at most $|A|(\Delta+1)<|V(D)|$). Observe
that $D[A\cup\\{v\\}]$ continues to be acyclic (since $v$ can not be a vertex
in any directed cycle with $A$ by construction), contradicting the maximality
of $|A|$ and giving the result.

For (b), we introduce the notation $N[S]=N^{+}[S]\cup N^{-}(S)$, i.e. this is
the set of vertices which are contained in some arc containing a vertex of
$S$. Let $S$ be a largest independent set satisfying

$|N^{+}[S]|\geq\frac{1}{2}|N[S]|,$ (1)

noting that at least one such independent set exists by considering
$S=\emptyset$.

Let $T=V(D)\setminus N[S]$. If $T=\emptyset$ (i.e. if $N[S]=V(D)$) then $S$ is
a maximal independent set with $|N^{+}[S]|\geq\frac{1}{2}|V(D)|$, so we may
assume for contradiction that this is not the case. Let $D^{\prime}=D[T]$.
Because $D^{\prime}$ is a non-empty digraph, there exists some vertex $v\in T$
with

$|N^{+}_{D^{\prime}}[v]|\geq\frac{1}{2}|N_{D^{\prime}}[v]|,$ (2)

namely this holds by taking any $v\in T$ with at least as many out-neighbors
as in-neighbors. In this case, $S^{\prime}=S\cup\\{v\\}$ is a larger
independent set satisfying

$N_{D}[S^{\prime}]=N_{D}[S]\cup(N_{D}[v]\setminus N_{D}[S])=N_{D}[S]\cup
N_{D^{\prime}}[v],$

and

$N_{D}^{+}[S^{\prime}]=N_{D}^{+}[S]\cup(N^{+}_{D}[v]\setminus
N_{D}^{+}[S])\supseteq N_{D}^{+}[S]\cup(N_{D}^{+}[v]\setminus
N_{D}[S])=N_{D}^{+}[S]\cup N_{D^{\prime}}^{+}[v].$

Combining these with (1) and (2) gives

$|N^{+}_{D}[S^{\prime}]|\geq|N^{+}_{D}[S]|+|N^{+}_{D^{\prime}}[v]|\geq\frac{1}{2}|N_{D}[S]|+\frac{1}{2}|N_{D^{\prime}}[v]|=\frac{1}{2}|N_{D}[S^{\prime}]|,$

a contradiction to the maximality of $|S|$. We conclude that a maximal
independent set with the desired properties must exist. ∎

We next show that if $D$ contains a small quasikernel, then $D$ contains a
large 3-kernel.

######  Proposition 4.2.

If $D$ is a digraph and $Q\subseteq V(D)$ is a quasikernel with
$|N^{+}[Q]|=\varepsilon|V(D)|$ for some $0<\varepsilon<1$, then there exists a
3-kernel $Q^{\prime}\subseteq V(D)$ with
$|N^{+}[Q^{\prime}]|\geq\frac{1-\varepsilon}{2}|V(D)|$.

###### Proof.

Let $T=V(D)\setminus N^{+}(Q)$, noting that $|T|\geq(1-\varepsilon)|V(D)|$ and
that $Q\subseteq T$. By 4.1(b), the digraph $D[T]$ contains a maximal
independent set $Q^{\prime}$ with

$|N^{+}_{D}[Q^{\prime}]|\geq|N^{+}_{D[T]}[Q^{\prime}]|\geq\frac{1}{2}|T|\geq\frac{1-\varepsilon}{2}|V(D)|.$

It thus remains to show that $Q^{\prime}$ is a 3-kernel. Note that
$Q^{\prime}$ is an independent set by construction. For any $w\in V(D)$, we
know there exists some $v\in Q$ such that $\mathrm{dist}(v,w)\leq 2$. Observe
that $v\in Q$ has $N^{+}(v)\subseteq N^{+}(Q)$ since $Q$ is an independent
set, and hence $v$ has no out-neighbors in $T=V(D)\setminus N^{+}(Q)$. As
such, since $Q^{\prime}$ is a maximal independent set of $D[T]$ and $v\in
Q\subseteq T$, either $v\in Q^{\prime}$ or some in-neighbor of $v$ lies in
$Q^{\prime}$. In either case we find $\mathrm{dist}(Q^{\prime},w)\leq
1+\mathrm{dist}(v,w)\leq 3$. This shows $Q^{\prime}$ is a 3-kernel, proving
the result. ∎

4.2 is essentially a refinement of 2.8(b), and in particular implies this
result.

###### Proof of 2.8(b).

Recall that we aim to show every digraph $D$ contains a 3-kernel with
$|N^{+}[Q]|\geq\frac{1}{3}|V(D)|$. Let $Q\subseteq V(D)$ be any quasikernel.
If $|N^{+}[Q]|\geq\frac{1}{3}|V(D)|$ then we are done, otherwise there exists
a 3-kernel of the desired size by 4.2. ∎

It remains to show that digraphs always contain large quasikernels. For this
we use the following.

######  Lemma 4.3.

If $D$ is a digraph and $A\subseteq V(D)$ is such that $D[A]$ is acyclic, then
there exists a quasikernel $Q\subseteq V(D)$ such that $A\subseteq N^{+}[Q]$.

###### Proof.

Let $S\supseteq A$ be a maximal subset such that $D[S]$ is acyclic. Observe
that every $v\notin S$ has an in-neighbor in $S$, as otherwise $S\cup\\{v\\}$
would be a larger subset inducing an acyclic digraph (since $v$ can not be a
part of any directed cycle in $S\cup\\{v\\}$).

It is known that every acyclic digraph contains a (unique) kernel (see [10,
Exercise 8.5]), and we let $Q$ denote the kernel of $D[S]$. Observe that
$A\subseteq S\subseteq N^{+}[Q]$ by definition of $Q$ being a kernel of
$D[S]$. We also have $\mathrm{dist}(Q,v)\leq 2$ for all $v\notin S$, since by
the observation above, $v$ has an in-neighbor in $S$ which is at distance at
most 1 from $Q$. Thus $Q$ is a quasikernel with the desired properties, giving
the result. ∎

We now have all we need to prove our main result for this section.

###### Proof of 2.8(a).

Recall that we aim to show every digraph contains a qusaikernel with
$|N^{+}[Q]|\geq|V(D)|^{1/3}$. Let $X\subseteq V(D)$ be the set of vertices $x$
which are not contained in any quasikernel of $D$.

First consider the case $|X|\geq|V(D)|-|V(D)|^{2/3}$. By the second half of
3.1, we in particular see that for each $x\in X$, there exists some $y\in
V(D)\setminus X$ such that $yx\in E(D)$ (namely, by considering the
quasikernel $Q$ which intersects $N^{+}[x]$ after noting that $Q$ is disjoint
from $X$ by definition of $X$). This implies that there are at least $|X|$
arcs from $V(D)\setminus X$ to $X$, and hence there must exist some $y\in
V(D)\setminus X$ with

$\deg^{+}(y)\geq\frac{|X|}{|V(D)|-|X|}\geq|V(D)|^{1/3}-1.$

Because $y\notin X$, there exists some quasikernel $Q$ such that $y\in Q$, and
hence $|N^{+}[Q]|\geq\deg^{+}(y)+1\geq|V(D)|^{1/3}$, proving the result.

Next consider $|X|\leq|V(D)|-|V(D)|^{2/3}$ and let $D^{\prime}=D-X$, noting
that $|V(D^{\prime})|\geq|V(D)|^{2/3}$. By the same argument as above, if
there exists $y\in V(D^{\prime})$ with
$\deg^{+}_{D^{\prime}}(y)\geq|V(D)|^{1/3}-1$, then any quasikernel of $D$
containing $y$ gives the desired result, so we may assume
$\deg^{+}_{D^{\prime}}(y)\leq|V(D)|^{1/3}-1:=\Delta$ for all $y\in
V(D^{\prime})$. By 4.1(a), there exists a subset $A\subseteq V(D^{\prime})$
such that $D^{\prime}[A]=D[A]$ is acyclic with
$|A|\geq\frac{|V(D^{\prime})|}{\Delta+1}\geq|V(D)|^{1/3}$. 4.3 then implies
the existence of quasikernel with $|N^{+}[Q]|\geq|A|\geq|V(D)|^{1/3}$, proving
the result. ∎

##  5 Proof of 2.2: Disjoint $q$-kernels

Recall that $S\subseteq V(D)$ is an $(r-1)$-source set if $N^{-}(S)=\emptyset$
and if $0<|S|\leq r-1$. In this subsection, we show that digraphs without
$(r-1)$-source sets contain $r$ disjoint $q$-kernels with $q$ small. We will
in fact prove something slightly stronger.

######  Definition 5.

Given a vector $\beta$ of length $r$ and a digraph $D$, we say that a tuple
$(Q_{1},\ldots,Q_{r})$ of disjoint vertex subsets of $D$ is a $\beta$-kernel
of $D$ if $Q_{i}$ is a $\beta_{i}$-kernel of $D$ for all $i$.

For example, a (3,2)-kernel of a digraph is a pair of disjoint sets
$Q_{1},Q_{2}$ such that $Q_{1}$ is a 3-kernel and $Q_{2}$ is a 2-kernel.

######  Theorem 5.1.

Define a sequence of vectors $\beta^{(r)}$ of length $r$ by taking
$\beta^{(2)}=(3,2)$, and for $r>2$ by setting

$\beta_{i}^{(r)}=\begin{cases}2(\beta_{i}^{(r-1)}+r-2)&i<r,\\\
2r-3&i=r.\end{cases}$

If $D$ contains no $(r-1)$-source sets for $r\geq 2$, then it contains a
$\beta^{(r)}$-kernel.

It is not difficult to determine the exact values of $\beta^{(r)}$ from 5.1.

######  Corollary 5.2.

If $D$ contains no $(r-1)$-source sets for $r\geq 2$, then it contains a
$\beta^{(r)}$-kernel where

$\beta_{i}^{(r)}=\begin{cases}7\cdot 2^{r-2}-2r&i=1,\\\ 3\cdot
2^{r-1}-2r&i=2,\\\ (4i-3)2^{r-i}-2r&3\leq i\leq r.\end{cases}$

Indeed, this follows by checking for each $i$ that the sequence
$\beta_{i}^{(r)}$ in 5.1 satisfies the same initial condition and recurrence
relation as the sequence in 5.2. From this our main result for disjoint
$q$-kernels is easy to derive.

###### Proof of 2.2 assuming 5.2.

Recall that we wish to show that every digraph without $(r-1)$-sources
contains $r$ disjoint $2^{r+1}$-kernels. By 5.2 we know there exist $r$
disjoint sets which are each $\beta_{i}^{(r)}$-kernels. It is straightforward
to show that $\beta_{i}^{(r)}\leq 2^{r+1}$ for all $i$ (for example, by noting
that $4i-3\leq 2^{i+1}$ for $i\geq 3$), giving the result. ∎

It remains to prove 5.1. We begin by proving a slight strengthening of the
$r=2$ case which will serve as a warmup for the general approach.

######  Lemma 5.3.

If $D$ is a source-free digraph, then for every independent set $Q\subseteq
V(D)$, there exists a 3-kernel $Q^{\prime}$ of $D$ which is disjoint from $Q$.

Note that this together with the fact that every digraph contains a
quasikernel implies that every source-free digraph contains a (3,2)-kernel.
This implies the $r=2$ case of 5.1 as well as 2.1.

###### Proof.

Define $D^{\prime}=D-Q$ and let $Q^{\prime}$ be any 2-kernel of $D^{\prime}$.
Because $D$ is source-free and $Q$ is independent, every vertex of $Q$ has an
in-neighbor in $V(D)\setminus Q$. Since $Q^{\prime}$ can reach every vertex of
$V(D)\setminus Q$ with a path of length at most 2 by construction,
$Q^{\prime}$ can reach every vertex of $V(D)$ with a path of length at most 3.
Since $Q^{\prime}$ is independent by construction, we conclude that
$Q^{\prime}$ is a 3-kernel, giving the result. ∎

We would like to adapt the approach above to find 3 disjoint $q$-kernels in
digraphs which contain no 2-source sets. Specifically, we would like to prove
that given any independent set $Q$, there always exist two disjoint
$q$-kernels in $V(D)\setminus Q$.

Unfortunately this approach will not work. Indeed, consider the digraph
$D_{s}$ with vertex set $\\{u,v_{1},\ldots,v_{s}\\}$ which consists of the
arcs $uv_{i}$ and $v_{i}u$ for all $i$ (equivalently, $D_{s}$ is a star graph
where each edge is replaced by a directed 2-cycle). It is not difficult to
check that $D_{s}$ contains no 2-source sets if $s\geq 2$, but there exists an
independent set $Q=\\{v_{1},\ldots,v_{s}\\}$ such that $V(D_{s})\setminus
Q=\\{u\\}$ does not contain two disjoint $q$-kernels.

Roughly speaking, the issue with the previous example is that, although
$D_{s}$ contains no 2-source sets for $s\geq 2$, there exists an independent
set $Q$ such that $D_{s}-Q$ contains sources, and hence there is no hope in
finding two disjoint $q$-kernels in $D_{s}-Q$. More generally, one can show
that the following condition is an obstruction to the approach of 5.3.

######  Definition 6.

Given a digraph $D$, we say that a non-empty set of vertices $S$ is a pseduo-
source set if $N^{-}(S)$ is an independent set and if $S\cup N^{-}(S)$ is a
source set (i.e. $N^{-}(S\cup N^{-}(S))=\emptyset$). Equivalently, $S$ is a
pseudo-source set if every $v\in N^{-}(S)$ has $N^{-}(v)\subseteq S$. We say
that such a set of vertices $S$ is an $s$-pseudo-source set if $S$ is non-
empty with $|S|\leq s$.

For example, every source set is a pseudo-source set (since in this case
$N^{-}(S)=\emptyset$), and in particular digraphs without 1-pseudo-source sets
are source-free. More generally, one can check that a digraph $D$ contains a
1-pseudo-source set if and only if it contains an induced copy of $D_{s}$ for
some $s\geq 0$ which has no incoming arcs from the rest of the digraph (noting
in particular that the $s=0$ case is equivalent to $D$ containing a source).

It turns out that pseudo-source sets are the only obstruction to the approach
of 5.3 going through.

######  Proposition 5.4.

Let $\beta$ be a vector of length $r-1\geq 2$ such that every digraph
$D^{\prime}$ without $(r-2)$-source sets contains a $\beta$-kernel. If $D$ is
a digraph which contains no $(r-2)$-pseudo-source sets, then for every
independent set $Q\subseteq V(D)$, there exist disjoint sets
$Q_{1},\ldots,Q_{r-1}$ which are disjoint from $Q$ such that each $Q_{i}$ is a
$(2\beta_{i}+1)$-kernel for $D$.

###### Proof.

Define a digraph $D^{\prime}$ on $V(D)\setminus Q$ by including the arc $uw$
if either $uw\in E(D)$ or if there exists a vertex $v\in Q$ such that
$uv,vw\in E(D)$.

######  Claim 5.5.

$D^{\prime}$ contains no $(r-2)$-source sets.

###### Proof.

Assume for contradiction that there exists a non-empty set $S\subseteq
V(D^{\prime})=V(D)\setminus Q$ with $|S|\leq r-2$ and
$N^{-}_{D^{\prime}}(S)=\emptyset$. Our aim is to show that $S$ is an
$(r-2)$-pseudo-source set in $D$, contradicting our hypothesis on $D$. In
particular, it suffices to show that each $v\in N^{-}_{D}(S)$ has
$N^{-}_{D}(v)\subseteq S$.

Consider an arbitrary $v\in N^{-}_{D}(S)$ (if such a vertex exists), say with
$vw\in E(D)$ and $w\in S$. If $v\in V(D)\setminus Q$, then $vw\in
E(D^{\prime})$ by definition of $D^{\prime}$ (since $w\in S\subseteq
V(D)\setminus Q$), contradicting $N^{-}_{D^{\prime}}(S)=\emptyset$. Thus we
can assume $v\in Q$. Note then that every $u\in N^{-}_{D}(v)$ satisfies
$u\notin Q$ (since $v\in Q$ and $Q$ is independent) and $u\notin
V(D^{\prime})\setminus S=V(D)\setminus(S\cup Q)$ (since otherwise $v\in Q$
would imply $uw\in E(D^{\prime})$ by definition of $D^{\prime}$, contradicting
$N_{D^{\prime}}^{-}(S)=\emptyset$), so we must have $u\in S$. Since $u\in
N_{D}^{-}(v)$ was arbitrary we conclude $N_{D}^{-}(v)\subseteq S$, completing
our contradiction for $S$ being an $(r-2)$-pseudo-source set. ∎

By hypothesis and the claim above, there exists a $\beta$-kernel
$(Q_{1},\ldots,Q_{r-1})$ of $D^{\prime}$. We claim that each $Q_{i}$ is a
$(2\beta_{i}+1)$-kernel of $D$, which will complete the proof.

Indeed, fix some $i$ and first consider an arbitrary vertex $w\in
V(D^{\prime})$. By definition of $Q_{i}$, there exists some $u\in Q_{i}$ and a
directed walk from $u$ to $w$ of length at most $\beta_{i}$ in $D^{\prime}$.
By definition of $D^{\prime}$, each of these walks in $D^{\prime}$ can be
extended to a walk of length at most $2\beta_{i}$ in $D$. This gives the right
distance condition for vertices in $V(D^{\prime})=V(D)\setminus Q$, so it
remains to show the result for $w\in Q$.

Because $D$ is source-free (since it contains no $(r-1)$-pseudo-source sets)
and $Q$ is an independent set, every $w\in Q$ has some in-neighbor $v\in
V(D)\setminus Q=V(D^{\prime})$. By our previous analysis, we know $v$ can be
reached from some $u\in Q_{i}$ by a walk of length at most $2\beta_{i}$, which
means $w$ can be reached by a walk of length at most $2\beta_{i}+1$. We
conclude that $Q_{i}$ is a $(2\beta_{i}+1)$-kernel, proving the result. ∎

In order to use 5.4 towards proving 5.1, we must transform digraphs which
avoid $(r-1)$-source sets into digraphs which avoid $(r-2)$-pseudo-source
sets. This is accomplished through the following lemma, where here we say that
a pseudo-source set $S$ is proper if there does not exist a non-empty set
$T\subsetneq S$ which is a pseudo-source set.

######  Lemma 5.6.

Let $r\geq 3$ be an integer and $D$ a digraph without $(r-1)$-source sets. Let
$D^{\prime}$ be the digraph obtained from $D$ by taking each proper
$(r-2)$-pseudo-source set $S$ of $D$ and adding all possible arcs between the
vertices of $N_{D}^{-}(S)$. Then $D^{\prime}$ contains no $(r-2)$-pseudo-
source sets.

###### Proof.

Assume for contradiction that there exists an $(r-2)$-pseudo-source set
$S^{\prime}$ of $D^{\prime}$.

######  Claim 5.7.

$S^{\prime}$ is an $(r-2)$-pseudo-source set of $D$.

###### Proof.

If this is not the case, then by definition there exists $v\in
N^{-}_{D}(S^{\prime})$ with $N^{-}_{D}(v)\not\subseteq S^{\prime}$. This
implies $v\in N^{-}_{D^{\prime}}(S^{\prime})$ and
$N^{-}_{D^{\prime}}(v)\not\subseteq S^{\prime}$ (because $D^{\prime}$ only add
arcs to $D$). This implies $S^{\prime}$ is not an $(r-2)$-pseudo-source set of
$D^{\prime}$, a contradiction. ∎

######  Claim 5.8.

For any non-empty pseudo-source set $S$ of $D$, the set $S\cup N^{-}_{D}(S)$
contains at least $r$ vertices.

###### Proof.

Observe that

$N^{-}_{D}(S\cup N^{-}_{D}(S))\subseteq N^{-}_{D}(S)\cup
N^{-}_{D}(N^{-}_{D}(S))\subseteq N^{-}_{D}(S)\cup S,$

where this last step uses that $N^{-}_{D}(N^{-}_{D}(S))\subseteq S$ since $S$
is a pseudo-source set by hypothesis. The expression above implies $S\cup
N^{-}_{D}(S)$ is a source set of $D$, and since $D$ contains no $(r-1)$-source
sets, this set must either be empty or have size at least $r$. The set can not
be empty since in particular $S\neq\emptyset$, so we conclude the set has size
at least $r$ as desired.

∎

Let $S\subseteq S^{\prime}$ be a proper $(r-2)$-pseudo-source set of $D$.

######  Claim 5.9.

There exists at most one vertex $w\in N_{D}^{-}(S)$ which is not in
$S^{\prime}$.

###### Proof.

If there exists no vertex with this property then we are done, so we may
assume there exists a vertex $w$ with this property. Note that $w\in
N_{D^{\prime}}^{-}(S^{\prime})$ since, by hypothesis, $w\notin S^{\prime}$ and
$w$ has an arc in $D\subseteq D^{\prime}$ to some vertex in $S\subseteq
S^{\prime}$. Thus

$(N^{-}_{D}(S)\setminus\\{w\\})\subseteq N^{-}_{D^{\prime}}(w)\subseteq
S^{\prime},$

where the first inclusion uses the definition of $D^{\prime}$, and the second
uses that $S^{\prime}$ is a pseudo-source set of $D^{\prime}$ and $w\in
N_{D^{\prime}}^{-}(S)$. This proves the claim. ∎

Putting these last two claims together, we see that $S^{\prime}$ contains at
least $r-1$ vertices (namely $S\cup N^{-}_{D}(S)\setminus\\{w\\}\subseteq
S^{\prime}$ since $S\subseteq S^{\prime}$ by definition), contradicting
$S^{\prime}$ being an $(r-2)$-pseudo-source set. We conclude the result.

∎

To use 5.6, we will need to understand how much the diameters of $D$ and
$D^{\prime}$ differ from each other. For this, we say a set of vertices $C$ of
a digraph $D$ is strongly connected if for all $u,v\in C$ there exists a
directed path from $u$ to $v$, and we say $C$ is a strongly connected
component if $C$ is a maximal set with this property. We define the diameter
of a strongly connected set $C$ to be $\max_{u,v\in C}\mathrm{dist}_{D}(u,v)$,
and we note that for strongly connected components this quantity is the same
as $\max_{u,v\in C}\mathrm{dist}_{D[C]}(u,v)$ (since no vertex $w$ outside of
$C$ can ever be used in a shortest path from $u$ to $v$, as otherwise
$C\cup\\{w\\}$ would also be strongly connected).

######  Lemma 5.10.

If $S$ is a proper pseudo-source set of a source-free digraph $D$, then $S\cup
N^{-}(S)$ is a strongly connected component of $D$ and has diameter at most
$2|S|$.

This diameter bound is best possible: if $D$ is obtained from a path graph
$u_{0}u_{1}\cdots u_{2r-1}u_{2r}$ by including both arcs for each edge, then
$S=\\{u_{1},u_{3},\ldots,u_{2r-1}\\}$ is a proper pseudo-source set and $S\cup
N^{-}(S)=V(D)$ has diameter exactly $2r$.

###### Proof.

We begin with the following.

######  Claim 5.11.

For any two vertices $u,v\in S\cup N^{-}(S)$, there exists a directed path in
$D$ from $u$ to $v$.

###### Proof.

Let $v\in S\cup N^{-}(S)$ be arbitrary, and let $T\subseteq S\cup N^{-}(S)$
denote the set of vertices $u$ such that there exists a directed path from $u$
to $v$ in $D$, noting that we trivially include $v\in T$. We aim to show that
$S\cap T$ is a pseudo-source set.

Showing $S\cap T\neq\emptyset$ is trivial if $v\in S$. If instead $v\in
N^{-}(S)$, then $N^{-}(v)\subseteq S$ since $S$ is a pseudo-source set. We
also have $N^{-}(v)\subseteq T$ by definition of $T$, so $N^{-}(v)\subseteq
S\cap T$. Moreover, $N^{-}(v)\neq\emptyset$ since $D$ is source-free, proving
that $S\cap T\neq\emptyset$.

We next show that every $u\in N^{-}(S\cap T)$ has $N^{-}(u)\subseteq S\cap T$.
If $u\in N^{-}(S\cap T)$ then, since $u$ has an arc to a vertex of $T$, we
must have $u\in T$ by definition of $T$, and similarly we must have
$N^{-}(u)\subseteq T$. Because $u\in T$ and $u\notin S\cap T$ by definition of
$u\in N^{-}(S\cap T)$, we must have $u\notin S$, and as such $u$ having an arc
to $S$ implies that $u\in N^{-}(S)$, so $N^{-}(u)\subseteq S$ by definition of
$S$ being a pseudo-source set. In total we find $N^{-}(u)\subseteq S\cap T$
for all $u\in N^{-}(S\cap T)$, which combined with our observation $S\cap
T\neq\emptyset$ shows that $S\cap T$ is a pseudo-source set.

Because $S\cap T$ is a pseudo-source set and $S$ is proper, we must have
$S\cap T=S$, i.e. $S\subseteq T$. By definition of $T$ this implies $S\cup
N^{-}(S)\subseteq T$, and hence $T=S\cup N^{-}(S)$. This implies every vertex
$u$ of $S\cup N^{-}(S)$ can reach the (arbitrary) vertex $v\in S\cup
N^{-}(S)$, proving the claim. ∎

Observe that no vertex $u\notin S\cup N^{-}(S)$ has an arc to $S\cup N^{-}(S)$
by definition of $S$ being a pseudo-source set. This together with the claim
above implies $S\cup N^{-}(S)$ is a strongly connected component.

To prove the diameter condition, consider any path $x_{0}x_{1}\cdots x_{\ell}$
in $D[S\cup N^{-}(S)]$. Note that for all $i$, at least one of the vertices
$x_{i},x_{i+1}$ must lie in $S$ since $N^{-}(v)\subseteq S$ for all $v\in
N^{-}(S)$, and this implies $\ell\leq 2|S|$. ∎

This gives the following.

######  Lemma 5.12.

Let $r,\ D$, and $D^{\prime}$ be as in 5.6. If $x_{0}\cdots x_{\ell}$ is a
directed path in $D^{\prime}$, then there exists a directed path from $x_{0}$
to $x_{\ell}$ in $D$ of length at most $\ell+2(r-2)-1$.

###### Proof.

This proof relies on two claims.

######  Claim 5.13.

If $S$ is a proper pseudo-source set of $D$, then $N_{D^{\prime}}^{-}(S\cup
N^{-}_{D}(S))=\emptyset$.

###### Proof.

Note that $N_{D}^{-}(S\cup N^{-}_{D}(S))=\emptyset$ by definition of $S$ being
a pseudo-source set of $D$. Thus the only way the claim can fail is if there
exists some $u\notin S\cup N^{-}_{D}(S)$ for which $D^{\prime}$ contains an
arc from $u$ to $S\cup N^{-}_{D}(S)$. By definition of $D^{\prime}$, this
would only be possible if there exists some proper pseudo-source set $T$ of
$D$ such that $T\cup N^{-}_{D}(T)$ contains $u$ and intersects $S\cup
N^{-}_{D}(S)$. However, the two sets $T\cup N^{-}_{D}(T)$ and $S\cup
N^{-}_{D}(S)$ are strongly connected components of $D$ by 5.10, so these two
sets must either be equal or disjoint from each other, a contradiction to
$T\cup N^{-}_{D}(T)$ intersecting $S\cup N^{-}_{D}(S)$ and containing a vertex
$u\notin S\cup N^{-}_{D}(S)$. ∎

The key observation from this claim is that if $j$ is such that $x_{j}\notin
S\cup N^{-}_{D}(S)$ for some proper $(r-2)$-pseudo-source set $S$ of $D$, then
$x_{j+1}\notin S\cup N^{-}_{D}(S)$, since the claim says that the only arcs in
$D^{\prime}$ to vertices of $S\cup N^{-}_{D}(S)$ come from vertices of $S\cup
N^{-}_{D}(S)$. With this key observation we get the following.

######  Claim 5.14.

There exists an integer $i$ and a proper $(r-2)$-pseudo-source set $S$ of $D$
such that for all $j\geq i$ we have $x_{j-1}x_{j}\in E(D)$, and for all $j<i$
we have $x_{j}\in S\cup N^{-}_{D}(S)$.

###### Proof.

By the key observation mentioned above, there exists some smallest integer
$i\geq 0$ (possibly with $i=\ell+1$) such that for all $j\geq i$, $x_{j}\notin
S\cup N^{-}_{D}(S)$ for every proper $(r-2)$-pseudo-source set $S$ of $D$. In
particular, this implies $x_{j-1}x_{j}\in E(D)$ for all $j\geq i$, since the
only arcs which lie in $E(D^{\prime})\setminus E(D)$ contain two vertices in
some $S\cup N^{-}_{D}(S)$ set with $S$ a proper $(r-2)$-pseudo-source set of
$D$.

If $i=0$ then the $j<i$ part of the claim trivially holds, so assume $i\geq
1$. By definition of $i$, there exists some proper $(r-2)$-pseudo-source set
$S$ of $D$ with $x_{i-1}\in S\cup N^{-}_{D}(S)$. Using the key observation
together with induction shows that we must have $x_{j}\in S\cup N^{-}_{D}(S)$
for all $j<i$, completing the claim. ∎

Let $i,S$ be as in the claim above. If $i\leq 1$ then $x_{0}\cdots x_{\ell}$
itself is a path in $D$ and there is nothing to prove, so assume $i\geq 2$. By
5.10 (which we can apply since $D$ avoiding $(r-1)$-source sets means it is
source-free), there exists a walk of length at most $2(r-2)$ from $x_{0}$ to
$x_{i-1}$ in $D$. Composing this with the walk $x_{i-1}\cdots x_{\ell}$ (which
is also in $D$ by definition of $i$) gives a path of length at most
$2(r-2)+\ell-(i-1)\leq 2(r-2)+\ell-1$ in $D$, giving the result. ∎

With everything in place, we can now prove our main result

###### Proof.

Recall that we wish to prove that if $D$ contains no $(r-1)$-source sets for
$r\geq 2$, then it contains a $\beta^{(r)}$-kernel where $\beta^{(2)}=(3,2)$
and inductively

$\beta_{i}^{(r)}=2(\beta_{i}^{(r-1)}+r-2)\ \ \textrm{for }i<r,\hskip
20.00003pt\beta_{r}^{(r)}=2r-3.$

We prove this by induction on $r$, the $r=2$ case following from 5.3 and the
fact that every digraph contains a 2-kernel.

Assume we have proven the result up to some value $r\geq 3$. Let $D$ be a
digraph without $(r-1)$-source sets and let $D^{\prime}$ be as in 5.6, i.e.
the digraph obtained by taking each proper $(r-2)$-pseudo-source set $S$ of
$D$ and adding all possible arcs between the vertices of $N^{-}_{D}(S)$, and
let $Q_{r}$ be an arbitrary 2-kernel of $D^{\prime}$. Because $D^{\prime}$ has
no $(r-2)$-pseudo-source sets by 5.6, 5.4 implies that there exist a
$\gamma$-kernel $(Q_{1},\ldots,Q_{r-1})$ for $D^{\prime}$ where
$\gamma_{i}:=2\beta_{i}^{(r-1)}+1$ for all $i$ such that each $Q_{i}$ is
disjoint from $Q_{r}$

We claim that each $Q_{i}$ is a $2(\beta^{(r-1)}_{i}+r-2)$-kernel of $D$ for
all $i<r$. Indeed, since $D\subseteq D^{\prime}$, each of these sets are still
independent. Fix an integer $i$ and $v\in V(D)$ and consider a shortest walk
$x_{0}\cdots x_{\ell}$ in $D^{\prime}$ from a vertex $u\in Q_{i}$ to $v$,
noting that $\ell\leq 2\beta_{i}^{(r-1)}+1$ by hypothesis. By 5.12, there
exists a path from $x_{0}$ to $x_{\ell}$ in $D$ of length at most
$2\beta_{i}^{(r-1)}+1+2(r-2)-1=2(\beta_{i}^{(r-1)}+r-2)$, proving the claim.

An essentially identical argument shows that $Q_{r}$ is a $q$-kernel of $D$
with $q=2+2(r-2)-1=2r-3$, which combined with the claim above gives the
desired result. ∎

##  6 Proof of 2.5: Bipartite Digraphs

In this section we show that bipartite digraphs with high girth have small
$q$-kernels. We begin by proving our result for quasikernels, for which the
following will be useful.

######  Lemma 6.1.

If $D$ is a digraph such that for every vertex $u\in V(D)$ there exists a
vertex $v\in N^{+}(u)$ which has in-degree 1, then $D$ is a disjoint union of
directed cycles.

###### Proof.

Since by hypothesis every vertex in $V(D)$ has an out-neighbor with in-degree
1, and since by definition each vertex of in-degree 1 has only 1 in-neighbor,
it follows that there are at least (and hence exactly) $|V(D)|$ vertices with
in-degree 1. It follows that every vertex also has out-degree 1 (using that
every vertex has positive out-degree by hypothesis and that the sum of the in-
degrees equals the sum of the out-degrees), from which we conclude that $D$ is
a disjoint union of directed cycles. ∎

With this we can prove our result for small quasikernels.

###### Proof of 2.4.

Recall that we wish to show that if $D$ is a source-free digraph with
bipartition $U\cup V$ which contains no directed 2-cycles or 4-cycles, then
there exists a quasikernel $Q$ such that $|Q|<\frac{1}{2}|V(D)|$. If
$|U|<\frac{1}{2}|V(D)|$, then taking $Q=U$ is a quasikernel (since $D$ is
source-free and bipartite) which satisfies the result. A similar result holds
if $|V|<\frac{1}{2}|V(D)|$, so we may assume $|U|=|V|=\frac{1}{2}|V(D)|$.

First consider the case that $D$ is a directed cycle on
$x_{1},\ldots,x_{2\ell}$ for some $\ell\geq 3$. In this case the set
$Q=\\{x_{1}\\}\cup\\{x_{2i}:2\leq i\leq\ell-1\\}$ is a quasikernel with
$|Q|=\ell-1<\frac{1}{2}|V(D)|$. A similar argument works if $D$ is a disjoint
union of directed cycles with lengths at least 6, so we may assume $D$ is not
of this form. The previous lemma thus implies that there exists a vertex $u\in
V(D)$ such that every vertex in $N^{+}(u)$ has in-degree at least 2, and
without loss of generality we may assume $u\in U$.

Consider $Q=U\setminus\\{u\\}$, and observe that $Q$ is a quasikernel due to
both our hypothesis on $u$ (which ensures that every vertex of $V$ is within
distance 1 of $Q$) and our hypothesis that $D$ is source-free (which ensures
$u$ is within distance 1 of some vertex in $V$). We also have
$|Q|=\frac{1}{2}|V(D)|-1$ by hypothesis on $U$, proving the result. ∎

We now prove our results about $q$-kernels. Here the key idea will be to
reduce the problem to the following case.

######  Definition 7.

We say that a finite digraph $D$ is unicyclic if every vertex has in-degree 1
and if the underlying graph of $D$ is connected.

The name “unicyclic” is motivated by the following result.

######  Lemma 6.2.

If $D$ is unicyclic, then (1) $D$ contains exactly one directed cycle $C$, and
(2) for every vertex $w\in V(D)$, there exists a unique directed path $P_{w}$
whose first vertex is in $C$, last vertex is $w$, and which contains no other
vertices of $C$.

###### Proof.

Let $w_{1}\in V(D)$ be arbitrary and iteratively define $w_{i+1}$ to be the
unique vertex in $N^{-}(v_{i})$. Because $D$ is finite, we must have
$w_{i}=w_{j}$ for some $i<j$. If one chooses this $i,j$ so that $j-i$ is as
small as possible, then we see that $w_{j},w_{j-1},\ldots,w_{i+1}$ are
distinct vertices with $w_{k+1}w_{k}\in E(D)$ for all $i<k<j$ and with
$w_{i+1}w_{j}\in E(D)$. We conclude that $D$ contains at least one directed
cycle. Moreover, the directed path $w_{i},w_{i-1}\ldots,w_{1}$ shows that
every vertex of $D$ has a directed path to it from a directed cycle which
intersects this cycle only at its endpoint. It thus remains to prove
uniqueness of these cycles and paths.

Let $C=(v_{j},v_{j-1},\ldots v_{1})$ be a directed cycle and assume for
contradiction that there exists some other directed cycle $C^{\prime}$ which
contains $v_{1}$. Because $v_{1}$ has a unique in-neighbor, namely $v_{2}$, we
see that the in-neighbor of $v_{1}$ in $C^{\prime}$ must also be $v_{2}$, and
continuing this we see that $C^{\prime}=C$, a contradiction. Thus if another
directed cycle $C^{\prime}$ exists it must be disjoint from $C$. Because $D$
is unicyclic, there exists some shortest (undirected) path $u_{1}\cdots u_{t}$
in the underlying graph of $D$ with $u_{1}\in C$ and $u_{t}\in C^{\prime}$.
Because this is a shortest path, we must have $u_{2}\notin C$, and because the
unique in-neighbor of $u_{1}$ lies in $C$ this implies $u_{1}u_{2}\in E(D)$.
Continuing this argument by induction, we conclude that $u_{i}u_{i+1}\in E(D)$
for all $i$, but this implies $u_{t}$ has an in-neighbor that is not in
$C^{\prime}$, a contradiction to the in-degree 1 hypothesis. We conclude that
$C$ is the only directed cycle in $D$.

Finally, let $w\in V(D)$ and suppose there exists two directed paths
$u_{s}u_{s-1}\cdots u_{1}$ and $v_{t}v_{t-1}\cdots v_{1}$ with the properties
as in the lemma, noting that this means $u_{1}=v_{1}=w$. Iterativelly given
that $u_{i}=v_{i}$ for some $i<\min\\{s,t\\}$, we must have that
$u_{i+1}=v_{i+1}$ since $u_{i}=v_{i}$ has a unique in-neighbor. If, say,
$s<t$, then this implies the path $v_{t}\cdots v_{1}$ contains two vertices of
$C$, namely $v_{s}=u_{s}$ and $v_{s+1}$ (since this is the unique in-neighbor
of $v_{s}=u_{s}$), a contradiction. Thus we must have $s=t$ and that
$u_{i}=v_{i}$ for all $i$, proving these directed paths are unique. ∎

We now prove the following special case of 2.5 when $D$ is unicyclic and $q$
is odd, which will turn out to give the full result after a few reductions.

######  Proposition 6.3.

Let $D$ be a unicyclic digraph with directed cycle of length $2\ell\geq 4$ and
which has bipartition $U\cup V$. If $q\geq 3$ is an odd integer and
$|V(D)|\geq(q+3)/2$, then there exists a $q$-kernel $Q\subseteq U$ with
$|Q|\leq\frac{2}{q+3}|V(D)|$.

This statement differs slightly from 2.5 in that we have replaced the
conditions on cycle lengths of $D$ with the condition $|V(D)|\geq(q+3)/2$
(which will allow our inductive proof to go through smoother), and we have
changed what the notation $\ell$ represent. We also note that this result is
false for $\ell=1$, as $D$ could consist of a directed 2-cycle $uv$ together
with a directed path of $q$ vertices attached to $v$.

###### Proof.

Assume for contradiction that there exists a counterexample $D$, and choose
such a counterexample with $|V(D)|$ as small as possible. Let $C$ denote the
vertices of the directed cycle of $D$, and for each $w\in V(D)$, let $P_{w}$
denote the path to $w$ guaranteed by 6.2. We begin by showing that every
vertex is somewhat close to the cycle.

######  Claim 6.4.

We have $\mathrm{dist}(C,w)<q$ for all $w\in V(D)$.

For this proof, we will make multiple uses of the fact that if $w^{\prime}\in
P_{w}$, then

$\mathrm{dist}(C,w)=\mathrm{dist}(C,w^{\prime})+\mathrm{dist}(w^{\prime},w),$

since $P_{w}$ being the unique path from 6.2 implies that $P_{w}$ must be
composed of $P_{w^{\prime}}$ together with the unique path from $w^{\prime}$
to $w$ if $w^{\prime}\notin C$ (and if $w^{\prime}\in C\cap P_{w}$ then
trivially $\mathrm{dist}(C,w)=\mathrm{dist}(w^{\prime},w)$).

###### Proof.

Let $w\in V(D)$ be such that $\mathrm{dist}(C,w)=\max_{x}\mathrm{dist}(C,x)$
and assume for contradiction that $\mathrm{dist}(C,w)\geq q$. Since $P_{w}$
has length $\mathrm{dist}(C,w)\geq q\geq(q+3)/2$ (using $q\geq 3$) and $q$ is
odd, there exists a vertex $w^{\prime}\in P_{w}$ with
$\mathrm{dist}(w^{\prime},w)=(q+1)/2$, noting that

$\mathrm{dist}(C,w^{\prime})=\mathrm{dist}(C,w)-\mathrm{dist}(w^{\prime},w)>0,$

so $w^{\prime}\notin C$. Let $X=\\{x\in
V(D):\mathrm{dist}(w^{\prime},x)\leq(q+1)/2\\}$ and define $D^{\prime}=D-X$.
We claim that $D^{\prime}$ satisfies the conditions of the lemma.

To show $D^{\prime}$ is unicyclic, it suffices to show that each path $P_{y}$
with $y\in V(D^{\prime})$ is contained in $V(D^{\prime})$ (since this will
imply each $y$ continues to have in-degree 1 and that the underlying graph is
connected). Assume for contradiction we had some $y\notin X$ and $x\in
P_{y}\cap X$. Because $x\in X$, there exists a path from $w^{\prime}$ to $x$,
and having $x\in P_{y}$ implies there is also a path from $w^{\prime}$ to $y$
by transitivity. Because $y\notin X$, we must have
$\mathrm{dist}(w^{\prime},y)>(q+1)/2=\mathrm{dist}(w^{\prime},w)$. But this
implies

$\mathrm{dist}(C,y)=\mathrm{dist}(C,w^{\prime})+\mathrm{dist}(w^{\prime},y)>\mathrm{dist}(C,w^{\prime})+\mathrm{dist}(w^{\prime},w)=\mathrm{dist}(C,w),$

a contradiction to how we chose $w$.

We next show $|V(D^{\prime})|\geq(q+3)/2$. For this, we observe that the
number of vertices removed from $P_{w}$ is exactly
$\mathrm{dist}(w^{\prime},w)+1=(q+3)/2$ and that we removed none of the
$2\ell$ vertices in the cycle, so we have

$|V(D^{\prime})|\geq 2\ell+\mathrm{dist}(C,w)-(q+3)/2\geq
4+q-(q+3)/2=(q+5)/2,$

proving the desired bound. Finally, since $D$ has bipartition $U\cup V$, it is
clear that $D^{\prime}$ has bipartition $U^{\prime}\cup V^{\prime}$ with e.g.
$U^{\prime}=U\cap V(D^{\prime})$.

We thus see that $D^{\prime}$ satisfies the conditions of the proposition.
Because $D$ was a minimal counterexample, there must exist a $q$-kernel
$Q^{\prime}\subseteq U^{\prime}$ of $D^{\prime}$ satisfying

$|Q^{\prime}|\leq\frac{2}{q+3}|V(D^{\prime})|=\frac{2}{q+3}(|V(D)|-|X|)\leq\frac{2}{q+3}|V(D)|-1,$

with this last step using $|X|\geq(q+3)/2$ (since $X$ includes every vertex
along the path from $w^{\prime}$ to $w$).

Define $z$ to be $w^{\prime}$ if $w^{\prime}\in U$ and $z$ to be the unique
vertex in $N^{-}_{D}(w^{\prime})$ otherwise. Note that in either case $z\in
U$. Define $Q=Q^{\prime}\cup\\{z\\}\subseteq U$, noting that this satisfies
$|Q|\leq\frac{2}{q+3}|V(D)|$ by the inequality above. We also have for
$x\notin X$ that

$\mathrm{dist}_{D}(Q,x)\leq\mathrm{dist}_{D^{\prime}}(Q^{\prime},x)\leq q,$

and for $x\in X$ we have

$\mathrm{dist}(Q,x)\leq\mathrm{dist}(z,x)\leq\mathrm{dist}(z,w^{\prime})+\mathrm{dist}(w^{\prime},x)\leq
1+(q+1)/2\leq q.$

Thus $Q$ is a $q$-kernel satisfying the conditions of the proposition,
contradicting $D$ being a counterexample. We conclude the claim. ∎

We can boost the previous claim by showing there are relatively few vertices
outside the cycle. For this we introduce some new notation that will be vital
for the rest of the proof.

Label the vertices of the cycle $C$ by
$(u_{1},v_{1},\ldots,u_{\ell},v_{\ell})$ with $u_{j}\in U$ for all $j$. We say
that a vertex $w\in V(D)$ has type $j$ if the path $P_{w}$ begins with either
$u_{j}$ or $v_{j}$. Equivalently, $w$ is of type $j$ if
$\mathrm{dist}(C,w)=\mathrm{dist}(\\{u_{j},v_{j}\\},w)$. We let
$\mathrm{ty}(j)$ denote the number of vertices of type $j$ in $D$. A useful
observation that we use throughout the proof is that if $w$ is of type $j$,
then

$\mathrm{dist}(u_{j},w)\leq\mathrm{ty}(j)-1,$ (3)

as the shortest path from $u_{j}$ to $w$ only uses vertices of type $j$ (and
the length of this path will be 1 less than the total number of vertices in
the path). With this observation in mind, we see that the following
significantly improves upon the previous claim.

######  Claim 6.5.

We have $\mathrm{ty}(j)<(q+3)/2$ for all $j$.

###### Proof.

Assume for contradiction that there exists some $j$ with
$\mathrm{ty}(j)\geq(q+3)/2$.

First consider the case $|V(D)|-\mathrm{ty}(j)\leq(q+1)/2$, and let
$Q=\\{u_{j}\\}\subseteq U$. Observe that $|Q|\leq\frac{2}{q+3}|V(D)|$ since we
assume $|V(D)|\geq(q+3)/2$. Also observe that if $w\in V(D)$ is of type
$j^{\prime}\neq j$, then there exists a shortest path from $u_{j}$ to $w$
obtained by using the arc $u_{j}v_{j}$ followed by some set of vertices not of
type $j$, so

$\mathrm{dist}(u_{j},w)\leq 1+(|V(D)|-\mathrm{ty}(j))\leq 1+(q+1)/2\leq q.$

On the other hand, if $w$ is of type $j$, then 6.4 implies

$\mathrm{dist}(u_{j},w)\leq 1+(q-1)\leq q,$

where the $1$ comes from the fact that $P_{w}$ may begin with $v_{j}$. We
conclude that $Q\subseteq U$ is a $q$-kernel for $D$ of size at most
$\frac{2}{q+3}|V(D)|$, a contradiction to $D$ being a counterexample to the
proposition. Thus we may assume $|V(D)|-\mathrm{ty}(j)\geq(q+3)/2$.

Next consider the subcase $\ell=2$ and define $Q=\\{u_{1},u_{2}\\}\subseteq
U$. Observe that our hypothesis
$\mathrm{ty}(j),|V(D)|-\mathrm{ty}(j)\geq(q+3)/2$ imply $V(D)|\geq q+3$, so
$|Q|\leq\frac{2}{q+3}|V(D)|$. Moreover, if $w\in V(D)$ has type $j$, then
again by using 6.4 we find

$\mathrm{dist}(Q,w)\leq\mathrm{dist}(u_{j},w)\leq q,$

so $Q$ is a $q$-kernel, contradicting $D$ being a counterexample.

With this we may assume $\ell>2$ and $|V(D)|-\mathrm{ty}(j)\geq(q+3)/2$. Let
$D^{\prime}$ be the digraph obtained from $D$ by deleting all vertices of type
$j$ and then adding the arc $v_{j-1}u_{j+1}$ (with these indices written mod
$\ell$). It is not difficult to see that $D^{\prime}$ is a unicyclic digraph
with cycle length $2(\ell-1)\geq 4$ which has
$|V(D^{\prime})|=|V(D)|-\mathrm{ty}(j)\geq(q+3)/2$ and which has bipartition
$U^{\prime}\cup V^{\prime}$ defined by e.g. $U^{\prime}=U\cap V(D^{\prime})$.

Since $D^{\prime}$ satisfies the conditions of the proposition, and since we
choose $D$ to be a minimal counterexample, there must exist some $q$-kernel
$Q^{\prime}\subseteq U^{\prime}$ for $D^{\prime}$ of size at most

$\frac{2}{q+3}|V(D^{\prime})|=\frac{2}{q+3}(|V(D)|-\mathrm{ty}(j))\leq\frac{2}{q+3}|V(D)|-1.$

Let $Q:=Q^{\prime}\cup\\{u_{j}\\}\subseteq U$, noting that
$|Q|\leq\frac{2}{q+3}|V(D)|$ by the above. We claim that $Q$ is a $q$-kernel
for $D$.

Indeed, if $w\in V(D)$ is of type $j$ then 6.4 implies
$\mathrm{dist}(u_{j},w)\leq q$. Otherwise $w\in V(D^{\prime})$, so there
exists a directed path $P^{\prime}=(w_{1},\ldots,w_{t})$ from $Q^{\prime}$ to
$w$ in $D^{\prime}$ of length at most $q$. If the arc $v_{j-1}u_{j+1}$ is not
in $P^{\prime}$, then every arc of $P^{\prime}$ is still in $D$, so
$P^{\prime}\subseteq D$ and the distance condition is satisfied. Thus we may
assume $v_{j-1}u_{j+1}$ is in $P^{\prime}$, say with $w_{s}=v_{j-1}$, noting
that $s\geq 2$ since any path from $Q^{\prime}\subseteq U$ must start with a
vertex in $U$. In this case we consider the path
$P=(u_{j},v_{j},w_{s+1},\ldots,w_{t})$ (i.e. we delete the beginning of
$P^{\prime}$ up to $u_{j+1}$ and then append $u_{j},v_{j}$ at the start). Note
that

$\mathrm{len}(P)=\mathrm{len}(P^{\prime})+2-s\leq\mathrm{len}(P^{\prime})\leq
q,$

so this path shows $\mathrm{dist}_{D}(Q,w)\leq q$.

In total we conclude that $Q\subseteq U$ is a small $q$-kernel for $D$, a
contradiction, giving the claim. ∎

Define $m=\lceil(q+3)/4\rceil$. Equivalently, $m\geq 2$ is the integer such
that either $q=-3+4m$ or $q=-5+4m$. The idea here is that if we can find some
$Q\subseteq U$ which uses a $1/m$ fraction of the $\ell$ vertices $u_{j}$,
then it turns out $Q$ will have the desired size. This idea quickly gives the
following.

######  Claim 6.6.

We have $\frac{2}{q+3}|V(D)|<\lceil\ell/m\rceil$.

###### Proof.

Assume for contradiction that $\frac{2}{q+3}|V(D)|\geq\lceil\ell/m\rceil$.
Define

$Q=\\{u_{1+mt}:0\leq t\leq\lceil\ell/m\rceil-1\\}\subseteq U,$

noting that $|Q|=\lceil\ell/m\rceil\leq\frac{2}{q+3}|V(D)|$.

We aim to show $Q$ is a $q$-kernel. To this end, consider any $w\in V(D)$, say
of type $j$. Observe that there exists some integer $0\leq
t<\lceil\ell/m\rceil$ such that $1+mt\leq j\leq m(t+1)$ (namely
$t=\lfloor(j-1)/m\rfloor$ works via observing $j-m\leq mt\leq j-1$). This and
(3) implies

$\mathrm{dist}(Q,w)\leq\mathrm{dist}(u_{1+mt},u_{j})+\mathrm{dist}(u_{j},w)\leq
2(j-(1+mt))+\mathrm{ty}(j)-1\leq 2(m-1)+(q-1)/2,$

with this last step using $j\leq m(t+1)$ and 6.5. Note that this quantity is
at most $q$ since $q\geq-5+4m$. Thus $Q\subseteq U$ is a small $q$-kernel for
$D$, a contradiction. ∎

We will use the bound above to prove the following set of inequalities, where
here and throughout we let $0\leq a\leq m-1$ be the integer such that
$\ell\equiv a\mod m$.

######  Claim 6.7.

For all $j$ we have

$\mathrm{ty}(j)\leq q-2m-2a+5,$

and further

$\min_{j}\mathrm{ty}(j)\leq q-2m-2a+3.$

###### Proof.

We begin by making a few observations about $|V(D)|$. By 6.6, we have

$\frac{2}{q+3}|V(D)|<\lceil\ell/m\rceil\leq\lfloor\ell/m\rfloor+1=(\ell+m-a)/m.$

Recall that $|V(D)|\geq(q+3)/2$ by hypothesis of the proposition, so the
inequality above combined with $\ell\equiv a\mod m$ implies

$\ell\geq m+a.$

Using these two inequalities gives

$|V(D)|<\frac{(\ell+m-a)(q+3)}{2m}=(2\ell+2m-2a)+\frac{(\ell+m-a)(q+3-4m)}{2m}\leq(2\ell+2m-2a)+(q+3-4m),$

where this last step used $q+3-4m\leq 0$ and $\ell\geq m+a$. In total, this
implies

$|V(D)|\leq 2\ell+q-2m-2a+2.$ (4)

We also note that

$q-2m-2a+2>0.$

Indeed, recalling that either $q=-5+4m$ or $q=-3+4m$, we see that this
immediately holds if either $a\leq m-2$ or if $a=m-1$ and $q=-3+4m$, so the
only potential issue is when $a=m-1$ and $q=-5+4m$. In this case, (4) would
imply $|V(D)|\leq 2\ell-1$, a contradiction to having $|V(D)|\geq 2\ell$ by
virtue of $D$ containing a directed $2\ell$-cycle.

Returning to the proof of the claim; if there existed some $j$ with
$\mathrm{ty}(j)\geq q-2m-2a+6$, then this together with the trivial bound
$\mathrm{ty}(j^{\prime})\geq 2$ for all $j^{\prime}$ (coming from
$u_{j},v_{j}$) would imply

$|V(D)|=\sum\mathrm{ty}(j^{\prime})\geq 2(\ell-1)+q-2m-2a+6=2\ell+q-2m-2a+4,$

a contradiction to (4). This proves the first part of the claim.

Similarly, if we had $\mathrm{ty}(j)\geq q-2m-2a+4$ for all $j$, then this
would imply

$\displaystyle|V(D)|$ $\displaystyle\geq\ell(q-2m-2a+4)=2\ell+\ell(q-2m-2a+2)$
$\displaystyle=2\ell+q-2m-2a+2+(\ell-1)(q-2m-2a+2)>2\ell+q-2m-2a+2,$

where this last step used $q-2m-2a+2>0$ and $\ell\geq 2$. This contradicts
(4), so we conclude the result. ∎

With these inequalities and the definition of $a$ in mind, we assume without
loss of generality that $\mathrm{ty}(\ell)=\min_{j}\mathrm{ty}(j)$ and define

$Q=\\{u_{1+mt}:0\leq t\leq\lfloor\ell/m\rfloor-1\\}=\\{u_{1+mt}:0\leq
t\leq(\ell-a)/m-1\\}\subseteq U.$

Note that

$|Q|=\lfloor\ell/m\rfloor\leq\frac{1}{2m}\cdot 2\ell\leq\frac{2}{q+3}\cdot
2\ell\leq\frac{2}{q+3}|V(D)|,$

where this first inequality used that $\frac{2}{q+3}$ either equals
$\frac{1}{2m}$ if $q=-3+4m$ or $\frac{1}{2m-1}\geq\frac{1}{2m}$ if $q=-5+4m$.
Note that this inequality together with 6.6 implies $a\neq 0$ (i.e. that
$\lfloor\ell/m\rfloor\neq\lceil\ell/m\rceil$).

We aim to show that $Q$ is a $q$-kernel. First, we claim that if $w\in V(D)$
is of type $j<\ell$, then there exists some $0\leq t\leq(\ell-a)/m-1$ such
that $1+mt\leq j\leq a-1+m(t+1)$. Indeed, if $j\leq\ell-a$ then one can take
$t=\lfloor(j-1)/m\rfloor\leq(\ell-a)/m-1$, and as in the proof of 6.6 this
satisfies

$1+mt\leq j\leq m(t+1)\leq a-1+m(t+1).$

If instead $\ell-a<j<\ell$ then we take $t=(\ell-a)/m-1$, in which case

$a-1+m(t+1)=\ell-1\geq j\geq 1+mt.$

Using this together with (3) and 6.7 gives

$\displaystyle\mathrm{dist}(Q,w)$
$\displaystyle\leq\mathrm{dist}(u_{1+mt},u_{j})+\mathrm{dist}(u_{j},w)$
$\displaystyle\leq 2(j-(1+mt))+\mathrm{ty}(j)-1$ $\displaystyle\leq
2(m+a-2)+(q-2m-2a+5)-1=q,$

where this last inequality used $j\leq a-1+m(t+1)$. Similarly if $w$ has type
$\ell$ then we have

$\displaystyle\mathrm{dist}(Q,w)$ $\displaystyle\leq\mathrm{dist}(u_{1+\ell-
a-m},u_{\ell})+\mathrm{dist}(u_{\ell},w)$ $\displaystyle\leq 2(\ell-(1+\ell-
a-m))+\mathrm{ty}(\ell)-1$ $\displaystyle\leq 2(m+a-1)+(q-2m-2a+3)-1=q.$

We conclude that $Q$ is a small $q$-kernel for $D$, a contradiction. We
conclude that no counterexample $D$ exists, proving the result. ∎

With 6.3 in hand we can now prove 2.5 in the special case when $q$ is odd and
$\ell=(q+3)/2$.

######  Theorem 6.8.

Let $D$ be a source-free bipartite digraph with bipartition $U\cup V$. If
$q\geq 3$ is odd and every directed cycle of $D$ has length at least
$(q+3)/2$, then $D$ contains a $q$-kernel $Q$ of size at most
$\frac{2}{q+3}|V(D)|$ with $Q\subseteq U$.

###### Proof.

Let $D,q$ be as in the hypothesis of the theorem. Form a subdigraph
$D^{\prime}\subseteq D$ by iteratively deleting arcs from $D$ until every
vertex has in-degree exactly 1 (which can be done since $D$ is source-free).

We can write $D^{\prime}$ as the disjoint union of digraphs
$D_{1}\cup\cdots\cup D_{t}$ where the underlying graph of each $D_{i}$ is
connected, and we observe that each $D_{i}$ is unicyclic with bipartition
$U_{i}\cup V_{i}$ defined by $U_{i}=U\cap V(D_{i})$ and $V_{i}=V\cap
V(D_{i})$. Moreover, since every directed cycle of $D$ has length at least
$(q+3)/2$, the directed cycle in each $D_{i}$ has length at least $(q+3)/2$.
This implies $|V(D_{i})|\geq(q+3)/2$ for all $i$, and that the length of the
cycle in each $D_{i}$ is at least 4 (since this cycle length is an even
integer that is at least $(q+3)/2\geq 3$). We can thus apply 6.3 to obtain
$q$-kernels $Q_{i}$ for each $D_{i}$ with $|Q_{i}|\leq\frac{2}{q+3}|V(D_{i})|$
and $Q_{i}\subseteq U_{i}$.

Let $Q=\bigcup Q_{i}$. Because $Q_{i}\subseteq U_{i}\subseteq U$ for all $i$,
we have that $Q\subseteq U$ (and hence is an independent set). We also have
$|Q|\leq\frac{2}{q+3}|V(D)|$ (since $|Q_{i}|\leq\frac{2}{q+3}|V(D_{i})|$ for
all $i$) and that $\mathrm{dist}_{D}(Q,x)\leq q$ for all $x\in V(D)$ (since
$x\in V(D_{i})$ for some $i$ and
$\mathrm{dist}_{D}(Q,x)\leq\mathrm{dist}_{D_{i}}(Q_{i},x)\leq q$). This
completes the proof. ∎

We now use this to complete the proof of our main result.

###### Proof of 2.5.

Recall that we wish to show that if $D$ is a source-free bipartite digraph
with bipartition $U\cup V$ and if $q,\ell\geq 3$ are integers such that
$\ell\leq(q+3)/2$ and such that every directed cycle of $D$ has length at
least $\ell$, then $D$ contains a $q$-kernel $Q$ of size at most
$\frac{1}{\ell}|V(D)|$ with $Q\subseteq U$.

By the hypothesis of the theorem, we can apply 6.8 with
$q^{\prime}=2\ell-3\geq 3$ to obtain a $q^{\prime}$-kernel $Q$ of $D$ with
size at most $\frac{2}{q^{\prime}+3}|V(D)|=\frac{1}{\ell}|V(D)|$ that lies in
$U$. Note that $Q$ is also a $q$-kernel since $q\geq q^{\prime}=2\ell-3$ by
hypothesis, proving the result. ∎

One can extend 2.5 somewhat beyond bipartite graphs with some (non-trivial)
extra work. To this end, given a digraph $D$, we say that a partition
$V_{1}\cup\cdots V_{r}$ of $V(D)$ is an $r$-cyclic partition if every arc
$uv\in E(D)$ has $u\in V_{i}$ and $v\in V_{i+1}$ for some $1\leq i\leq r$
(where here and throughout we write our indices mod $r$). By adapting our
methods we claim without proof that we can establish the following
generalization of 2.5.

######  Theorem 6.9.

Let $D$ be a source-free bipartite digraph with $r$-cyclic partition
$V_{1}\cup\cdots\cup V_{r}$. If $q\geq r^{2}-1$ and $\ell\geq(r^{2}+r)/2$ are
integers such that $\ell\leq(q+1+r)/2$, $\ell\equiv 0\mod r$, and such that
every directed cycle of $D$ has length at least $\ell$, then $D$ contains a
$q$-kernel $Q$ of size at most $\frac{1}{\ell}|V(D)|$ with $Q\subseteq V_{1}$.

Note that this theorem requires the extra hypothesis $\ell\equiv 0\mod r$
compared to 2.5, but this is somewhat superfluous since every cycle length of
$D$ must be a multiple of $r$. As 6.9 is not our focus, we defer discussing
the tightness of its parameters and the details of its proof to the Appendix.

##  7 Concluding Remarks

In this section we outline a number of remaining problems involving
$q$-kernels.

###  7.1 Disjoint $q$-kernels

Recall that 2.2 guarantees the existence of $r$ disjoint $q$-kernels with
$q\leq 2^{r+1}$ provided $D$ contains no $(r-1)$-source sets. The best
construction we know of is $D=C_{2r-1}$, which requires $q\geq 2r-2$ in order
to have $r$-disjoint $q$-kernels. We suspect that this lower bound is much
closer to the truth compared to the upper bound.

######  Conjecture 7.1.

There exists $\varepsilon,r_{0}>0$ such that if $D$ contains no $(r-1)$-source
sets with $r\geq r_{0}$, then $D$ contains $r$-disjoint $q$-kernels with
$q\leq(2-\varepsilon)^{r}$.

The main barrier for proving 7.1 is 5.4, which roughly involves replacing $D$
by its “square” and is the primary source of the growth rate of $2^{r}$. As
5.4 is the heart of our present argument, significant new ideas would be
needed in order to prove 7.1.

###  7.2 Small $q$-kernels

We next turn to questions involving small $q$-kernels in source-free digraphs
with certain restrictions.

####  7.2.1 Restricted Cycle Lengths

2.3 involving digraphs with restricted cycle lengths seems too difficult to
solve in general, but many interesting problems remain even in the case when
$D$ is bipartite. For example, 2.5 gives optimal bounds when $D$ is a
bipartite digraph of an appropriate girth. It would be interesting to extend
this result to all bipartite $D$. One promising approach for odd $q$ would be
the following, where here we recall a digraph is unicyclic if every vertex has
in-degree 1 and if the underlying graph is connected.

######  Question 7.2.

Let $D$ be a unicyclic digraph with directed cycle of length $2\ell$ and
bipartition $U\cup V$. If $q\geq 3$ is odd, do there exist $q$-kernels
$Q_{U}\subseteq U$ and $Q_{V}\subseteq V$ such that

$|Q_{U}|+|Q_{V}|\leq 2\cdot\frac{\lceil\ell/(q+1)\rceil}{\ell}\cdot|V(D)|?$

As mentioned in the introduction, it is not true in general that we can always
guarantee e.g. $|Q_{U}|\leq\frac{\lceil\ell/(q+1)\rceil}{\ell}\cdot|V(D)|$,
but 7.2 suggests that on average at least one of the sets $Q_{U}$ or $Q_{V}$
will meet this bound if $q$ is odd. If this were true, then one could use the
same reduction from the proof of 2.5 to give a positive answer to 2.3 whenever
$q$ is odd and $D$ is bipartite (with the additional conclusion that $Q$ is
contained in either $U$ or $V$, though we can not specify which set it will
lie in ahead of time).

The situation is more complex for bipartite $D$ when $q$ is even, as we can
not in general find small $q$-kernels contained in either $U$ or $V$. For
$q=2$ we managed to prove the weak bound $|Q|<\frac{1}{2}|V(D)|$ when $D$
avoids directed 2-cycles and 4-cycles. We suspect this can be improved
substantially.

######  Conjecture 7.3.

There exists an $\varepsilon>0$ such that if $D$ is a source-free bipartite
digraph with no directed 2-cycles or 4-cycles, then $D$ contains a quasikernel
$Q$ with $|Q|\leq\left(\frac{1}{2}-\varepsilon\right)|V(D)|$.

The optimal possible value here would be $\varepsilon=1/10$ due to $C_{10}$.
We note that 2.3 predicts that 7.3 should hold even without the hypothesis
that $Q$ is bipartite, but this seems comparable in difficulty to the Small
Quasikernel Conjecture itself.

####  7.2.2 Variants of Source-Free Digraphs

Source-free digraphs are exactly digraphs with minimum in-degree 1. As such,
the following is a natural followup question to the Small Quasikernel
Conjecture.

######  Question 7.4.

For integers $\delta\geq 1$ and $q\geq 2$, what is the smallest constant
$c_{\delta,q}$ such that every digraph $D$ with minimum in-degree $\delta$
contains a $q$-kernel $Q$ with $|Q|\leq c_{\delta,q}|V(D)|$?

For example, the Small Quasikernel Conjecutre is equivalent to the statement
$c_{1,2}=\frac{1}{2}$. The full extent of our knowledge around this question
is as follows.

######  Proposition 7.5.

Let $c_{\delta,q}$ be defined as above.

  * (a)

For all $\delta\geq 1$ and $q\geq 2$, we have
$c_{\delta,q}\geq\frac{1}{\delta+1}$.

  * (a)

If $q\geq 2^{\delta+2}$, then $c_{\delta,q}=\frac{1}{\delta+1}$.

  * (b)

For all $\delta\geq 2$, we have $c_{\delta,2}\geq\frac{1}{3}$.

###### Proof.

Part (a) follows by considering a bidirected $K_{\delta+1}$, which has minimum
in-degree $\delta$ and every non-empty independent set has size
$\frac{1}{\delta+1}|V(D)|$.

For (b), observe that any digraph $D$ with minimum in-degree $\delta$ has no
$\delta$-source sets. As such, 2.2 implies that $D$ contains $\delta+1$
disjoint $q$-kernels for any $q\geq 2^{\delta+2}$, and in particular one of
these has size at most $\frac{1}{\delta+1}|V(D)|$.

For (c), consider the digraph $D$ on vertex set $V_{1}\cup V_{2}\cup V_{3}$
where $|V_{i}|=\delta$ for all $i$ and where we add every arc from $V_{i}$ to
$V_{i+1}$ (with these indices written cyclically). It is not difficult to see
that the only quasikernels of $D$ are the $V_{i}$ sets, proving the result. ∎

It is unclear what the true behavior of $c_{\delta,q}$ should be in general,
especially when $\delta$ is large in terms of $q\geq 3$. For $q=2$ the
following seems natural to guess.

######  Conjecture 7.6.

There exists some $\delta\geq 2$ such that every digraph $D$ of minimum in-
degree at least $\delta$ contains a quasikernel $Q$ with
$|Q|\leq\frac{1}{3}|V(D)|$.

This problem might be easy to solve in the setting of bipartite digraphs,
though we note that a bidirected $C_{6}$ shows for $\delta=2$ that one can not
hope to prove such a result by finding a quasikernel of size at most
$\frac{1}{3}|V(D)|$ contained in one of the two parts of $D$.

Another variant of being source-free is being strongly connected. For this we
ask the following.

######  Question 7.7.

If $D$ is a strongly connected digraph and $q\geq 2$ is an integer, does there
exist a $q$-kernel $Q$ of $D$ such that $|Q|\leq\frac{|V(D)|}{q+1}+O_{q}(1)$?

This bound would be best possible by considering a collection of $C_{q+2}$’s
sharing a common vertex. We have not spent a substantial amount of time
thinking about this problem, so it is quite likely that better constructions
exist. Still, it would be interesting to see if any non-trivial bounds could
be obtained under the assumption of being strongly connected.

###  7.3 Large Quasikernels

We asked in 2.6 whether every digraph contains a “large” quasikernel, namely
one with $|N^{+}[Q]|\geq\frac{1}{2}|V(D)|$, and we made some modest progress
towards this goal in 2.8 by proving $|N^{+}[Q]|\geq V(D)|^{1/3}$. We believe
that our bounds can be improved by proving the following result.

######  Conjecture 7.8.

Every digraph $D$ either contains a subset $A\subseteq V(D)$ with $D[A]$
acyclic and $|A|\geq|V(D)|^{1/2}$, or a vertex $y\in V(D)$ which is contained
in some quasikernel and which has $\deg^{+}(y)\geq|V(D)|^{1/2}-1$.

The bounds of 7.8 are best possible, as can be seen by considering the
disjoint union of Eulerian tournaments of size $|V(D)|^{1/2}$. We note that
our proof of 2.8(a) essentially reduced to showing the conjecture above holds
with $1/2$ replaced by $1/3$, and in particular 7.8 would improve 2.8(a) to
the stronger bound $|N^{+}[Q]|\geq|V(D)|^{1/2}$, which is the natural barrier
for our present approach.

There are various weakenings of the Large Quasikernel Conjecture that one
could try to solve, such as by improving the bounds for $q$-kernels, or by
replacing $|N^{+}[Q]|$ with the larger quantity $\sum_{v\in Q}|N^{+}[v]|$.
Another direction would be to look for stronger versions of 2.6, such as the
following.

######  Question 7.9.

Does every digraph $D$ contains a quasikernel $Q$ with
$|N^{+}(Q)|\geq\frac{1}{2}|V(D)\setminus Q|$? Equivalently, does there exist a
quasikernel with $|N^{+}[Q]|\geq\frac{|V(D)|+|Q|}{2}$?

This result would be sharp by considering the disjoint union of Eulerian
tournaments of arbitrary sizes (cf the Large Quasikernel Conjecture which is
only asymptotically sharp). It would be interesting to know if, like the Large
Quasikernel Conjecture, 7.9 is a consequence of the Small Quasikernel
Conjecture.

Acknowledgments. We thank Ruth Luo for introducing us to the Small Quasikernel
Conjecture, as well as Xiaoyu He, Noah Kravitz, and Bhargav Narayanan for
fruitful discussions. We further thank Noah Kravitz for correcting typos from
an earlier draft, as well as for shortening our original proof of 6.1.

## References

  * [1] J. Ai, S. Gerke, G. Gutin, A. Yeo, and Y. Zhou.  Results on the small quasi-kernel conjecture.  Discrete Mathematics, 346(7):113435, 2023.
  * [2] V. Chvátal and L. Lovász.  Every directed graph has a semi-kernel.  In Hypergraph Seminar: Ohio State University 1972, pages 175–175. Springer, 1974.
  * [3] P. Erdős and L. Székely.  Two conjectures on quasi-kernels, open problems no. 4. in fete of combinatorics and computer science.  Bolyai Society Mathematical Studies, 2010.
  * [4] P. L. Erdős, E. Győri, T. R. Mezei, N. Salia, and M. Tyomkyn.  On the small quasi-kernel conjecture.  arXiv preprint arXiv:2307.04112, 2023.
  * [5] G. Gutin, K. M. Koh, E. G. Tay, and A. Yeo.  On the number of quasi-kernels in digraphs.  Journal of Graph Theory, 46(1):48–56, 2004.
  * [6] A. Kostochka, R. Luo, and S. Shan.  Towards the small quasi-kernel conjecture.  arXiv preprint arXiv:2001.04003, 2020.
  * [7] M. Kwasnik.  On (k, l)-kernels on graphs and their products.  Technical University of Wrocław, Wrocław, 1980.
  * [8] H. Langlois, F. Meunier, R. Rizzi, and S. Vialette.  Algorithmic aspects of small quasi-kernels.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 370–382. Springer, 2022.
  * [9] H. Langlois, F. Meunier, R. Rizzi, and S. Vialette.  Quasi-kernels in split graphs.  arXiv preprint arXiv:2312.15519, 2023.
  * [10] L. Lovász.  Combinatorial problems and exercises, volume 361.  American Mathematical Soc., 2007.
  * [11] A. van Hulst.  Kernels and small quasi-kernels in digraphs.  arXiv preprint arXiv:2110.00789, 2021.
  * [12] J. Von Neumann and O. Morgenstern.  Theory of games and economic behavior, 2nd rev.  1947\.

##  Appendix A Strengthening the Results

Here we discuss a few technical ideas themed around improving the main results
of the paper.

###  A.1 Small Quasikernels

Here we comment on some natural extensions of our argument for 1.2 which do
not end up yielding significantly better bounds. One of the main drivers of
our argument was 3.1, which in particular says that there exist quasikernels
disjoint from $N^{+}(x)$ for any $x\in V(D)$. One can easily extend the proof
of this result to show the following.

######  Lemma A.1.

If $D$ is a digraph and $X\subseteq V(D)$ is an independent set, then there
exists a quasikernel $Q$ of $D$ with $Q\cap N^{+}(X)=\emptyset$.

This together with our argument for 1.2 yields the following.

######  Proposition A.2.

If $D$ is a digraph and $\Delta$ is a real number such that either (1) $D$
contains an independent set $X$ with $|N^{+}(X)|\geq\Delta$ or (2) every
independent set of $D$ has size at most $|V(D)|-\Delta$, then there exists a
quasikernel $Q$ with $|Q|\leq|V(D)|-\Delta$.

Our present argument essentially shows that one can take
$\Delta=\sqrt{|V(D)|}$ for source-free digraphs via only ever considering $X$
in (1) which are singletons. It turns out that one can not do much better than
this even if one uses the full power of (1).

To see this, consider the digraph $D$ formed by taking any source-free
tournament on $\sqrt{n}$ vertices $v_{1},v_{2},\ldots$ and then for each $i$
adding $\sqrt{n}-1$ new vertices $v_{i,j}$ together with the arcs
$v_{i}v_{i,j}$. Here $|V(D)|=n$, and it is not difficult to see that every
independent set $X$ has $|N^{+}(X)|\leq 2\sqrt{n}$ and that there exist
independent sets of size $n-\sqrt{n}$, namely the set $V$ consisting of all
$v_{i,j}$ vertices.

One could try and get around the previous example by altering (2) in A.2 via
demanding the bound $|V(D)|-\Delta$ hold only for quasikernels of $D$, or even
just for minimal quasikernels of $D$. Unfortunately this still does not work:
take the previous example and add a new vertex $w$ together with the arcs
$v_{i,j}w$ and $wv_{i}$ for all $i,j$. In this case, essentially all of the
conditions from before hold and $V$ is now a minimal quasikernel of $D$.

###  A.2 Variants of the Large Quasikernel Conjecture

Here we briefly discuss some variants of the Large Quasikernel Conjecture
which are natural to consider but which ultimately turn out to be non-
interesting.

First, one could form an (a priori) stronger version of the Large Quasikernel
Conjecture by considering digraphs $D$ together with a weight function
$w:V(D)\to\mathbb{R}_{\geq 0}$. In this setting, a natural conjecture would be
that for every weighted digraph $D$, there exists a qusikernel $Q$ such that
the weight of the vertices of $N^{+}[Q]$ is at least half of the total weight
on $V(D)$. This stronger conjecture is implicitly solved for tournaments in
[1, Theorem 12], and we note that the proof for 2.7 can be used to show that
this weighted conjecture is also implied by the Small Quasikernel Conjecture
(essentially by giving each vertex about $k\cdot w(u)$ new neighbors).

However, this weighted version turns out to be implied by the unweighted
version. Somewhat more precisely, if $w$ is integral valued, then we can
replace each $u\in V(D)$ by a set $U$ of size $w(u)$ and each arc $uv$ by
including every possible arc from $U$ to $V$, in which case a solution to the
Large Quasikernel Conjecture in this auxiliary digraph lifts to a solution for
the weighted version. This solves the problem for $w$ integral valued, which
solves it for rational values, which can then be used to solve it for real
values by approximating by rationals. As such, there is no loss in generality
by only considering 2.6.

Second, one might consider a variant of the Large Quasikernel Conjecture for
$q$-kernels by replacing $N^{+}[Q]$ by the set of all vertices that are at
distance at most $q-1$ from $Q$. However, if $q\geq 3$ then we can take $Q$ to
be any quasikernel (which is in particular a $q$-kernel), in which case this
set ends up being all of $V(D)$.

###  A.3 Improving the Disjointness Result

Here we discuss the problem of improving the bounds of 5.1 for finding
$\beta$-kernels in digraphs without source-set. As noted around 7.1, the
largest loss in our argument comes from 5.4 (where we essentially take the
square of $D$), and this step seems difficult to get around with our present
approach. However, there is one (somewhat technical) place where our argument
can likely be improved to give a moderate strengthening of our results.

Specifically, the loss we consider comes from 5.6 where we take each proper
$(r-2)$-pseudo-source set $S$ and add all possible arcs within $N^{-}(S)$.
With this process, we destroy all $(r-2)$-pseudo-source sets of $D$ at the
cost of decreasing the path lengths in $D^{\prime}$ by as much as $2(r-2)-1$
compared to that of $D$. It seems plausible that one can add fewer arcs to
$S\cup N^{-}(S)$ while maintaining the $(r-2)$-pseudo-source set condition and
decreasing the path length by significantly less. Unwinding our proof shows
that it would suffice333Specifically, given a digraph $D$, we take each
strongly connected component $C$ which contains an $(r-2)$-pseudo-source set
and replace $D[C]$ with $D^{\prime}[C]$ as defined in A.3. We can apply this
result since $C$ contains at least $r$ vertices by 5.8 and 5.11 (with this
second claim implying that $C=S\cup N^{-}(S)$), and the condition
$|V(D)|-\alpha(D)\leq r-2$ holds since $|S|\leq r-2$ and
$|N^{-}(S)|\leq\alpha(D)$. The proof of 5.9 essentially says that the set of
vertices of $D^{\prime}[C]$ which is not in some $(r-2)$-pseudo-source set of
$D^{\prime}$ is an independent set of $D^{\prime}$, i.e. has size at most
$\alpha(D^{\prime})$, so $|V(D^{\prime})|-\alpha(D^{\prime})\geq r-1$ implies
there are no $(r-2)$-pseudo-source sets in $D^{\prime}$. to solve the
following (seemingly tractable) problem, where here $\alpha(D)$ denotes the
size of a largest independent set of $D$.

######  Problem A.3.

For each $r\geq 3$, determine the smallest number $\Delta(r)$ such that the
following holds: If $D$ is a strongly connected digraph on at least $r$
vertices such that $|V(D)|-\alpha(D)\leq r-2$, then there exist a superdigraph
$D^{\prime}\supseteq D$ on the same vertex set $V(D)$ such that
$|V(D^{\prime})|-\alpha(D^{\prime})\geq r-1$ and such that for all $u,v\in
V(D^{\prime})$, we have

$d_{D^{\prime}}(u,v)\geq d_{D}(u,v)-\Delta(r).$

Our current argument essentially shows that we can take $\Delta(r)=2(r-2)-1$
(via adding all possible arcs within $D$). We believe one can get this to work
with $\Delta(r)=r-3$, which would be best possible by considering a directed
$r$-cycle. If one could prove this for $\Delta(r)=r-3$, then one could
essentially replace every $2(r-2)$ in our proof with $r-2$. In particular, the
analog of 5.1 would guarantee $\alpha$-kernels in $(r-1)$-source-free digraphs
with $\alpha_{r}=r-1$, and such a result would be best possible by considering
the directed $r$-cycle.

###  A.4 Difficulties with Bipartite Digraphs

In 2.5 we managed to verify some special cases of 2.3 by finding small
$q$-kernels whenever $D$ has a bipartition $U\cup V$ and avoids certain cycle
lengths. Moreover, 2.5 guarantees that these small $q$-kernels lie entirely
within $U$. This additional feature of having $Q\subseteq U$ was vital to our
proof of 6.8, as otherwise we would not be able to guarantee that the union of
the $Q_{i}$ sets from our reduced digraph $D^{\prime}$ would still be
independent. However, the following result shows that it is not possible in
general to solve 2.3 for bipartite digraphs if we continue to require
$Q\subseteq U$.

######  Lemma A.4.

For all $q,\ell\geq 1$, there exists a digraph $D$ with bipartition $U\cup V$
such that every directed cycle of $D$ has length $2\ell$ and such that any
$q$-kernel $Q$ of $D$ which lies in $U$ has $|Q|\geq\frac{1}{q}|V(D)|$.

For example, when $q=3$ this shows that regardless of the cycle conditions
placed on $D$, it is impossible to improve upon the bound
$|Q|\leq\frac{1}{3}|V(D)|$ obtained from 2.5 if we continue insisting that
$Q\subseteq U$. As such, something like 7.2 would be needed to solve 2.3 for
bipartite digraphs when $q=3$.

###### Proof.

Let $D$ be the digraph obtained from a directed cycle
$u_{1},v_{1},\ldots,u_{\ell},v_{\ell}$ after attaching directed paths of
length $q-2$ to each $v_{i}$ vertex. If $u_{i}\in U$ for all $i$, then it is
not difficult to see that every $q$-kernel contained in $U$ must have size at
least $\ell$ (namely, $Q$ must contain either $u_{i}$ or at least one vertex
in the path attached to $v_{i}$ for all $i$), proving the result. ∎

There exist some constructions that are even better than those of A.4. For
example, for $q=5$ and $\ell=3$ one can consider a directed 6-cycle after
attaching a leaf to each vertex of $V$. In this case the smallest 5-kernel
contained in $U$ satisfies $|Q|=\frac{2}{9}|V(D)|$, which is a larger fraction
than is guaranteed by A.4 and which (unlike A.4 in this case) shows that 2.3
can not hold when $q=5$ and $L(D)=\\{\ell\\}$ if we insist on $Q\subseteq U$.

###  A.5 Beyond Bipartite Digraphs

Recall that we say a partition $V_{1}\cup\cdots V_{r}$ of $V(D)$ is an
$r$-cyclic partition if every arc $uv\in E(D)$ has $u\in V_{i}$ and $v\in
V_{i+1}$ for some $1\leq i\leq r$ (where here and throughout we write our
indices mod $r$). Here we discuss 6.9, which we restate below for convenience.

######  Theorem.

Let $D$ be a source-free bipartite digraph with $r$-cyclic partition
$V_{1}\cup\cdots\cup V_{r}$. If $q\geq r^{2}-1$ and $\ell\geq(r^{2}+r)/2$ are
integers such that $\ell\leq(q+1+r)/2$, $\ell\equiv 0\mod r$, and such that
every directed cycle of $D$ has length at least $\ell$, then $D$ contains a
$q$-kernel $Q$ of size at most $\frac{1}{\ell}|V(D)|$ with $Q\subseteq V_{1}$.

6.9 can be tight by considering disjoint unions of $C_{\ell}$, as well as by
considering disjoint unions of $C_{2\ell}$ whenever $2\ell\geq q+2$ (which
always occurs at the maximum possible value $\ell=\lfloor(q+1+r)/2\rfloor$).

The bound $q\geq r^{2}-1$ is necessary for 6.9 to hold: if we had
$q=r^{2}-r-1$, then one could take $D$ to be $C_{q+1}$ after attaching a leaf
to each of the $(q+1)/r=r$ vertices in $V_{r}$. In this case, any $q$-kernel
contained in $V_{1}$ must contain at least two vertices, but the bound we ask
for is
$\lfloor\frac{2|V(D)|}{q+1+r}\rfloor=\lfloor\frac{2(r^{2}-1)}{r^{2}}\rfloor=1$.

Similar to our proof of 6.8, 6.9 will follow from the following special case
of $\ell=(q+1+r)/2$ and $q\equiv-1\mod r$.

######  Theorem A.5.

Let $D$ be a source-free digraph with $r$-cyclic partition
$V_{1}\cup\cdots\cup V_{r}$. If $q\geq r^{2}-1$ is an integer with
$q\equiv-1\mod r$ and is such that every directed cycle of $D$ has length at
least $(q+1+r)/2$, then there exists a $q$-kernel $Q$ of $D$ such that
$|Q|\leq\frac{2}{q+1+r}|V(D)|$ with $Q\subseteq V_{1}$.

With this result we can prove 6.9 by applying A.5 with
$q^{\prime}:=2\ell-r-1\geq r^{2}-1$, which yields a $q^{\prime}$-kernel of
size at most $\frac{1}{\ell}|V(D)|$ that is also a $q$-kernel since $q\geq
q^{\prime}$ by hypothesis. We now discuss the ideas of this proof.

###### Sketch of Proof of A.5.

As before, it suffices to prove the result when $D$ is unicyclic with cycle
length $r\ell\geq 2r$ and $|V(D)|\geq(q+1+r)/2$. We label the vertices of the
cycle by $v_{1}^{1},v_{1}^{2},\ldots,v_{1}^{r},v_{2}^{1},v_{2}^{2}$, and so
on. We say a vertex $w$ has type $j$ if it is closest to
$\\{v_{j}^{1},\ldots,v_{j}^{r}\\}$ and let $\mathrm{ty}(j)$ denote the number
of vertices of type $j$. Essentially the same proof as before shows for all
$j$ that

$\mathrm{ty}(j)<(q+1+r)/2,$

though a little extra care is needed to deal with the case when $(q+1+r)/2$ is
not an integer.

Let $m$ be such that either $q=-1-r+2rm$ or $q=-1-2r+2rm$ and let $a$ be such
that $\ell\equiv a\mod m$. The case where
$\frac{2}{q+1+r}|V(D)|<\lceil\ell/m\rceil$ is very similar to the $r=2$ case:
here we can follow the same logic as in our proof of (4) to show

$|V(D)|\leq r\ell+q-rm-ra+r,$

where again we have that $q-rm-ra+r>0$ by the same reasoning as before. From
this it is easy to show that $\mathrm{ty}(j)\leq q-rm-ra+2r+1$ and that
$\min_{j}\mathrm{ty}(j)\leq q-rm-ra+2r+1$. Assuming
$\mathrm{ty}(\ell)=\min_{j}\mathrm{ty}(j)$, we can take
$Q=\\{v_{1+mt}^{1}:0\leq t\leq\ell/m-1\\}$ which will have the desired size.
If $w\in V(D)$ is of type $j\neq\ell$ then we have

$\mathrm{dist}(Q,w)\leq r(m+a-2)+\mathrm{ty}(j)-1\leq q,$

and a similar argument holds for $j=\ell$ showing that $Q$ is indeed a small
$q$-kernel.

It thus remains to deal with the case
$\frac{2}{q+1+r}|V(D)|\geq\lceil\ell/m\rceil$, and it is here that things get
more complicated. Naively, we would like to use the set
$Q=\\{v_{1+mt}^{1}:0\leq t\leq\lceil\ell/m\rceil-1\\}$ which has the desired
size, but this turns out444Specifically this will be a $q$-kernel if we always
have $\mathrm{ty}(j)\leq q-rm+r+1$, and we are only guaranteed
$\mathrm{ty}(j)<(q+1+r)/2$. If $q=-1-r+2rm$ then we have
$\mathrm{ty}(j)<rm=q-rm+r+1$, so this is fine. However, if $q=-1-2r+2rm$ we
only have $\mathrm{ty}(j)<rm-r/2$, and this will only imply
$\mathrm{ty}(j)\leq q-rm+r+1=rm-r$ if $r=2$. to be a $q$-kernel in general
only if either $q=-1-r+2rm$ or if $r=2$. However, we can still get the idea of
picking every $1/m$ vertices to work when $q=-1-2r+2rm$ and
$\frac{2}{q+1+r}|V(D)|\geq\lceil\ell/m\rceil$ provided we add in a few extra
vertices.

To this end, define $B$ to be the set of $j$ with $\mathrm{ty}(j)\geq rm-r+1$,
and let $B^{\prime}\subseteq B$ be the elements with $j=mt$ for some integer
$1\leq t\leq\ell/m$ (noting that the $j\in B^{\prime}$ are exactly the $j$
such that we can not guarantee $\mathrm{dist}(Q,w)\leq q$ in the argument
above). Possibly by reindexing our cycle, we can assume that
$|B^{\prime}|\leq\lfloor|B|/m\rfloor$ (since, for example, randomly choosing
the vertex labeled $v_{1}^{1}$ gives $\mathbb{E}[|B^{\prime}|]\leq|B|/m$).
Define

$Q=\\{v_{1+mt}^{1}:0\leq t\leq\lceil\ell/m\rceil-1\\}\cup\\{v_{j}^{1}:j\in
B^{\prime}\\}.$

It is not difficult to show that $Q$ is a $q$-kernel. Since
$|Q|\leq\lceil\ell/m\rceil+\lfloor|B|/m\rfloor$, it suffices to show

$\frac{2}{rm-r}|V(D)|=\frac{2}{q+1+r}|V(D)|\geq\lceil\ell/m\rceil+\lfloor|B|/m\rfloor.$
(5)

Since we assume $\frac{2}{q+1+r}|V(D)|\geq\lceil\ell/m\rceil$, there is
nothing to prove if $|B|<m$, so we can assume $|B|\geq m$. We can also assume
$m\geq 3$, as otherwise $q\geq r^{2}-1$ does not hold for $r\geq 3$ (since
$q=-1-2r+2rm$).

By definition of $B$ we have

$|V(D)|\geq r(\ell-|B|)+(rm-r+1)|B|=r\ell+(1-2r+rm)|B|.$

Multiplying both sides by $\frac{2}{rm-r}$ and using some crude estimates
gives

$\frac{2}{rm-r}|V(D)|\geq\frac{2}{m}\ell+\frac{2(m-2)}{m-1}|B|=\frac{2}{m}\ell+\frac{2m-5}{m-1}|B|+\frac{1}{m-1}|B|\geq\frac{2}{m}\ell+1+\lfloor|B|/m\rfloor,$

where this last step used $|B|\geq m-1$ and that $2m-5\geq 1$ since $m\geq 3$.
Observe that $\frac{2}{m}\ell+1\geq\lceil\ell/m\rceil$ (this is trivial if
$\ell\leq m$, otherwise $\lceil\ell/m\rceil\leq 2\ell/m$). We thus conclude
that (5) holds, proving the result.

∎