Hardness for Graph Problems - Reductions Based on APSP and SETH
summary
Dense-case claim: APSP-equivalent to radius/median/eccentricities via fine-grained, sometimes adaptive reductions that build min-plus (distance) products and tripartite graphs and show any O(n^{3−ε}) for one yields O(n^{3−Ω(1)}) for the others; core tools are distance-product ↔ negative-triangle and binary-search-on-all-pairs using distance product ↔ negative triangle constructions with piece partitioning and s ≈ n^{1/3} balancing. Sparse-case claim: conditional hardness from Orthogonal Vectors and Hitting Set yields tight approximation barriers like 3/2 and 5/3 approximation thresholds and n^{1.5}-time algorithms for those ratios.
AI-written summary · about
chapters (9)
- 0:00Graph problem definitions
- 4:25Dense graph equivalences
- 7:24Sub-cubic reductions
- 12:49Distance product analysis
- 16:56Negative triangle reduction
- 24:01Adaptive reduction process
- 32:00Radius and triangle linkage
- 40:48Sparse graph conjectures
- 46:25Approximation and conclusions
related talks
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
23mTowards General and Tight Hardness Results for Graph Problems
35mApproximation hardness and online algorithms for resource scheduling
35mSuperlinear Lower Bounds for Multipass Graph Processing
23mA New Connection Between Node and Edge Depth Robust Graphs
32mFrom Sparse Matrices to Graphs and Back Again
01h 05mGraph Algorithms in the MPC Model
01h 23mProperty Testing for Graphs