Imagine a network made of one-way streets. You want to choose a small group of starting points so that every location can be reached by following the arrows—but you also want the chosen starting points to have no arrows directly connecting them. How small can that group be, even in the worst possible network?
This is a puzzle about directed graphs, abstract networks whose links have directions. A selected set that has no links between its members and can reach every vertex within a limited number of steps is called a q-kernel. The number q is the step limit. A vertex can reach itself in zero steps; another vertex must be reached by following arrows in their direction.
The two requirements pull against each other. Add more starting points and you may reach more of the graph, but you also risk choosing two that are directly linked. Allow more steps and each starting point can cover more territory, but the arrows may twist into loops and dead ends. Even knowing that every vertex has many arrows pointing into it does not tell you which way those vertices can reach the rest of the network.
A June 2026 paper by Geoffrey Boyer and colleagues sharpens the puzzle by asking how the answer depends on the graph’s minimum in-degree: the smallest number of incoming arrows any vertex has. Their results expose a striking change between two and three steps. With two steps, the small-set problem remains stubbornly open. With three, greater minimum in-degree guarantees that a relatively small group will suffice.
Here is the paper’s broad three-step guarantee in everyday terms: the share of vertices needed is at most one divided by one plus the integer part of the square root of the minimum in-degree plus one. That bound shrinks as the minimum in-degree grows. For example, if every vertex has at least 100 incoming arrows, the guarantee says a three-kernel can be found using no more than one eleventh of the vertices.
Why should one extra step matter so much? The clue is that the two-step problem has a formidable rival: the need for the chosen vertices to stay independent. The Small Quasikernel Conjecture asks whether every finite directed graph in which each vertex has at least one incoming arrow contains a two-step reaching set with no more than half its vertices. That question remains open. More generally, the paper notes that for two steps the best universal guarantee is known to be no smaller than half, even when every vertex has many incoming arrows.
The authors do not solve that two-step mystery. Instead, they show that at three steps the guaranteed fraction can approach zero as the minimum in-degree grows. The contrast is not that dense networks automatically make every route easy. It is that a third step gives a proof strategy room to manage two competing jobs: cover the graph, then remove conflicts among the covering points.
The strategy begins by building a set of provisional starting points. Call them anchors. Whenever an anchor can bring at least a chosen number of previously uncovered vertices within a short distance, the proof adds it and puts those newly reached vertices into a covered pile. Each anchor is thus credited with a batch of covered territory. That accounting limits how many anchors the procedure can collect.
But a greedy rule alone can leave stubborn vertices behind. These sit in the uncovered region, where each has too few nearby uncovered vertices to qualify for the next batch. Here minimum in-degree becomes useful. Count the arrows that run between vertices in that leftover region: each internal arrow contributes once to the total incoming count and once to the total outgoing count. The minimum incoming requirement, combined with the procedure’s limit on outgoing arrows there, constrains how large the troublesome leftover can be.
That counting argument lets the authors assemble a set that reaches the whole graph in two steps and has no directed cycle among its own members. It is not yet a q-kernel, because it may still contain an arrow between two selected anchors. The paper calls this almost-there object a prekernel. The name marks the remaining obstacle: coverage is in place, but independence is not.
To resolve that obstacle, the authors order the anchors so that arrows among them point consistently forward or backward through the order. They then keep an anchor only when it has no direct arrow to or from an anchor already kept. Any anchor left out can be reached from a kept one in a single extra step. So a route that previously took at most two steps now takes at most three. The extra step buys independence without throwing away the reachability already built.
The square-root bound comes from balancing the size of the batches against the leftover vertices. The resulting guarantee is not known to be the best possible for three steps. In fact, there is a simple reason no bound can be smaller than one out of every δ plus one vertices: make the graph from separate groups of δ plus one vertices, with arrows in both directions between every pair in each group and no arrows between groups. One selected vertex reaches its entire group, but each group needs a representative. For groups of 101, that forces one out of 101.
That construction suggests the next question. For every fixed minimum in-degree and every step limit of at least three, could the true worst-case requirement be just one vertex per group of δ plus one? The authors conjecture that it could be. They prove this exact guarantee once the step limit reaches the ceiling of one-and-a-half times δ, plus one. If δ is 100, that means at least 151 steps—far more than three.
So the puzzle has a partial solution and a new gap to investigate. Three steps already turn high minimum in-degree into a powerful guarantee, but the cleanest possible bound is reached only at a much larger step limit in the theorem. Between those results lies a question about how much directed reachability can be compressed without letting the starting points interfere with one another. One extra step opens the door; how far it can take us is still unsettled.
