Reachability with Subquadratic Cut Queries on Directed Graphs

Abstract

In the cut-query model, we have access to a (directed) graph via an oracle and we can query the size of the (directed) cut of a given subset of the vertices. One of the most elementary tasks in this model is to decide if there is a path between two fixed vertices $s$ and $t$. While many results are known for undirected graphs, much less is understood for directed graphs in the cut-query model. Even for the basic task of $s$-$t$ reachability, the best known randomized algorithm is to reconstruct the entire graph with a technique by Grebinski and Kucherov using $O(n^2/\log n)$ queries. On directed acyclic graphs (DAGs), we obtain a deterministic single-source reachability algorithm using $O(n\sqrt{n\log n})$ queries. The result is based on a topological sort algorithm and can also be adapted to compute single-source shortest paths in DAGs. On general directed graphs, we obtain deterministic algorithms for single-source reachability, strongly connected components and minimum $s$-$t$ cut using $O(n^{9/5}\log n)$ queries. The algorithm is simple and relies on two natural greedy subroutines and a modified version of Dinic's algorithm.