Imagine a city map where every street is one-way. You may place a few dispatchers at intersections, but no two dispatchers can be directly connected by a street. How many do you need so every intersection can be reached by following the arrows for only a few blocks?
This is a graph-theory puzzle about directed networks. Each intersection is a vertex and each one-way street is an arrow. A chosen group must meet two demands at once: its members cannot have arrows between them, and every vertex must be reachable from one of them within a set number of steps. Mathematicians call such a group a q-kernel, where q is the maximum allowed path length.
The tension is immediate. More arrows can help a dispatcher’s signal travel, but they can also make it harder to keep dispatchers independent. And if the arrows loop around, a small set of starting points may leave some vertices out of reach. The question is not simply how connected the network is, but how much reach can be gained without placing seeds too close together.
A team of eight researchers takes up this problem in a paper posted to arXiv in June 2026. The sharpest clue comes from comparing two-step reach with three-step reach. For two steps, a known lower bound says that some directed networks may require a chosen set containing at least half their vertices, even when every vertex has many incoming arrows. The paper does not settle that stubborn case. Allow one more step, though, and a striking new guarantee appears.
If every vertex has at least δ incoming arrows, the authors prove that a three-step q-kernel can always be found with no more than the total number of vertices divided by one plus the greatest integer no larger than the square root of δ plus one. In plain terms, as the minimum number of incoming arrows rises, the guaranteed share of vertices needed as starting points falls. The bound is not claimed to be the best possible, but it gives a firm answer where the two-step problem resists one.
Why should a single extra step matter so much? The proof starts by refusing to solve the full puzzle all at once. Instead, it grows a provisional set of useful vertices and sorts the rest of the network into two regions: vertices already covered nearby, and vertices still uncovered. Whenever a candidate can reach enough new vertices in the uncovered region, the method adds it to the provisional set and moves those newly covered vertices aside.
This choice creates an accounting rule. Each addition costs one candidate, but it must account for a batch of newly covered vertices. At the end, the provisional set has no directed cycles among its members. That is not yet enough: a cycle-free set can still contain arrows between selected vertices, violating the independence rule. But acyclicity gives the researchers an ordering of the candidates. They can keep some and discard others in a controlled way, removing immediate neighbors as they go. This turns the provisional set into a genuinely independent one.
There is a price for that cleanup. A vertex that had been reachable from the provisional set may now be reached through one of the retained independent vertices, adding a step to the route. That is the hidden exchange at the heart of the result: accept a slightly longer route in return for a smaller, better-separated set of starting points. The three-step guarantee comes from building a provisional set that covers within two steps, then paying one more step to enforce independence.
The leftover region is where the argument could have failed. If many vertices remain uncovered, perhaps they would force the set to grow too large. But the stopping rule says each leftover vertex has only a small neighborhood within that region. At the same time, the minimum in-degree condition insists that every vertex still has many incoming arrows. The authors use this clash—few local neighbors, many required incoming links—to bound how much troublesome territory can remain. Choosing the batch size near the square root balances the cost of selecting candidates against the cost of dealing with leftovers.
The researchers also find a threshold at which the answer becomes exact. When the allowed path length is at least the ceiling of one and a half times δ, plus one, they prove that no more than one out of every δ plus one vertices needs to be selected. This matches a simple obstruction: take a complete network on δ plus one vertices and put arrows in both directions between every pair. A valid independent set can contain only one vertex, and that one reaches the whole network. So a better universal guarantee is impossible.
That exact result still leaves a gap in the mystery. The authors conjecture that the same one-in-δ-plus-one fraction should be enough for every path allowance of at least three, not just once the allowance reaches their threshold. For three steps, their square-root bound is weaker than this conjectured answer. And at two steps, the old half-the-vertices barrier remains a separate, unresolved clue.
So the puzzle does not end with a universal recipe for every network. It ends with a surprising boundary: the mathematical cost of keeping starting points independent can change dramatically when a route gains just one more step. In directed networks, reach and separation are rivals—but give reach a little more room, and a much smaller set of origins may be enough.
