A Simple Subquadratic Cut Query Protocol for Directed Reachability
cs.DS
Submitted: 2026-11-04
Updated: 2026-11-04
Project page: https://yangpliu.github.io/repo/directed-reachability-cut-queries/paper.pdf
Terminology
Sources
- Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
- Reachability with Subquadratic Cut Queries on Directed Graphs
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
- Reachability in Directed Acyclic Graphs with Near-Linear Cut Queries
- Solving Linear Programs with Sqrt(rank) Linear System Solves
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time