Fine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
summary
Graphs reachability and shortest-paths reduce to specific matrix products: transitive closure is equivalent to Boolean matrix multiplication and APSP to MinPlus product, both up to log factors. New sparse-results give an output-sensitive exponent ~1.3459 (improving prior 1.5) using densify via sparse-recovery plus high/low-degree splitting and rectangular fast matrix multiplication. Single-source shortest paths reach near-linear m · polylog W; APSP approximations match n^omega bounds, while undirected constant-factor queries use m·n^{1/k} preprocessing with 3SUM-based hardness.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 2:30Reachability Problems
- 13:00Sparse Boolean Matrix Product
- 17:10Further Improvements
- 19:20Running Time Complexity
- 31:51Reachability
- 32:34Distance Problems
- 36:07Single shortest path
- 38:07All pairs path
- 42:27Approximation
- 44:19Enter the Omega
- 49:56Summary
related talks
59mHardness for Graph Problems - Reductions Based on APSP and SETH
35mSuperlinear Lower Bounds for Multipass Graph Processing
32mFrom Sparse Matrices to Graphs and Back Again
01h 07mComputational Complexity of Polynomial Time Problems: Introduction
01h 05mGraph Algorithms in the MPC Model
30mThree Goals in Parallel Graph Computations: High Performance, High Productivity, and Reduced Comm...
19mBeeping Shortest Paths via Hypergraph Bipartite Decomposition
47mMultiscale Analysis on and of Graphs