有向图上的次二次割查询可达性
Reachability with Subquadratic Cut Queries on Directed Graphs
Ben Bals, Matei Tinca, Yasamin Nazari
AI 速览：在有向图的割查询模型中，作者给出了DAG上单源可达性的确定性算法（O(n√(n log n))次查询），以及一般有向图上单源可达性、强连通分量和最小s-t割的确定性算法（O(n^{9/5} log n)次查询）。
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.