A New Connection Between Node and Edge Depth Robust Graphs
summary
Gives a concrete reduction that turns an E-edge-depth-robust DAG with m edges into an E/2 node-depth-robust DAG with O(m) nodes and constant indegree by replacing each original vertex with a maximal ST-robust graph; the paper constructs linear-sized constant-degree linear-sized constant-degree ST-robust gadgets (three-copy H1/H2/H3 + random parent links + superconcentrators) and proves most H1 paths reach H3. Applies to the Grätzer/Graets-like construction to improve parameters for intermediate I and yields perfectly tight proofs-of-space and source-to-sink depth-robust graphs.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:58(Node) Depth Robust Graphs
- 2:17Edge Depth Robust Graphs
- 2:53Node v. Edge Depth Robust
- 4:08Our results
- 5:44Our Transformation (High Level)
- 6:50Key Building Block: (1. kn)-ST-Robust Graphs
- 7:54ST-Robust Example
- 8:23Maximal ST-Robust Graphs
- 9:21Core of Maximal ST-Robust Construction
- 10:35Proof Sketch
- 12:19Full Construction
- 14:03Proof of Main Theorem: Removing a Node
- 15:31Proof of Main Theorem: Corresponding Paths
- 16:29Open Question
- 17:34A Partial Answer
- 19:11Other Applications of ST-Robust Graphs
- 22:25Summary
- 23:00References
related talks
23mTowards General and Tight Hardness Results for Graph Problems
59mHardness for Graph Problems - Reductions Based on APSP and SETH
35mSuperlinear Lower Bounds for Multipass Graph Processing
01h 00mHardness for Dynamic Problems; Conclusion and Future Research
01h 37mGraphons and Graph Limits 3
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
01h 23mProperty Testing for Graphs
49mPerfection and Beyond