Jul 2026
Reachability in Directed Acyclic Graphs with Near-Linear Cut Queries
This work begins a systematic study of basic problems in directed \emph{acyclic} graphs (DAGs) and shows that reachability from a single vertex and even topological sorting are both computable in O(n \log^3 n) many cut queries.
Sanjeev Khanna, Aaron Putterman, Junkai Song
· arXiv.org · 1 citation