New algorithm reduces queries to find paths in directed graphs
A Simple Subquadratic Cut Query Protocol for Directed Reachability
Data Structures and Algorithms
Summary
Finding if there is a path from one point to another in a one-way network can take a lot of checking. The authors look at this problem in a new way by asking about certain 'cuts' or boundaries in the network, which helps find the path more efficiently. They created a simpler method that asks fewer questions than before, improving how quickly this can be solved with a computer. Their work gives a new way to handle these problems with fewer steps, saving time.
What this means in practice
- •For network analysts: Improve efficiency in checking communication paths in complex directional networks using fewer data queries.
- •For database query optimizers: Optimize query plans that involve reachability within directed data graphs by reducing the number of edge inspections needed.
A theory result. No direct application yet.
Authors
Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal
Abstract
We study $s$--$t$ reachability in an unweighted directed graph on $n$ vertices, accessed through a directed cut oracle: given $S\subseteq V$, the oracle returns the number of edges directed from $S$ to $V\setminus S$. Directed cut functions are submodular, and reachability asks whether the minimum $s$--$t$ cut has positive value. This connects the problem to the query complexity of submodular function minimisation. Whether or not reachability can be solved in truly subquadratic query complexity has been an outstanding open question for a decade. We give a simple algorithmic blueprint with two randomised implementations. The first uses $\widetilde O(n^{9/5})$ outgoing-cut queries; the second improves this bound to $\widetilde O(n^{5/3})$. The common idea is to construct an alternative orientation with the same underlying undirected graph and vertex-wise degree imbalances, thereby preserving reachability. We first approximate the target imbalances using an averaging and rounding procedure, then correct the remaining error with a flow. An earlier manuscript, made available in August 2026 in an online AI repository, reports an $\widetilde O(n^{3/2})$ query bound. Our contribution is a simple and comprehensible alternative approach that already achieves a polynomial saving over quadratic query complexity.