← 研踪 PaperTrailarXiv:2607.26630 · v2
Reachability with Subquadratic Cut Queries on Directed Graphs
首次提交 2026-07-29 16:56
版本更新 2026-11-05 01:07
雷达观测 2026-11-05 12:12
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-05 01:07 · 最新观测版本
Reachability with Subquadratic Cut Queries on Directed Graphs
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.
查看此版本解读 →查看此版本原文 ↗