2026/07/23 by Sanjeev Khanna, Aaron Putterman, Junkai Song · 1 citation
#cs.DS
In the cut-query model, an algorithm is given access to a graph G = (V, E) only via cut queries. This model has seen significant attention in the undirected graph setting, with works establishing O(n) cut query algorithms for computing the global minimum cut, \widetildeO(n3/2) cut query algorithms for all pairs minimum cut, and many more. However, despite this vast array of progress in designing sub-quadratic query algorithms for computing properties of undirected graphs, there has been no progress in designing such algorithms in directed graphs. Indeed, even for basic problems like whether a vertex t is reachable from a vertex s, the cut query complexity is only known to be bounded in the interval [Ω(n), O(n2 / log n)]. In this work, we begin a systematic study of these basic problems in directed acyclic graphs (DAGs). In this setting, we show that reachability from a single vertex and even topological sorting are both computable in O(n log3 n) many cut queries. As a consequence, we also obtain an algorithm which, for any arbitrary directed graph G, uses only O(n log3 n) cut queries and determines whether G contains a cycle.