Deterministic Edge Connectivity in Near-Linear Time
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Deterministic algorithm finds global edge connectivity and a min-cut cactus for simple graphs in near‑linear time (polylog overhead), by repeatedly certifying or discovering low‑conductance cuts using a deterministic PageRank push scheme and then contracting all safely contractible parts to a graph with about m/Δ edges while preserving every non‑trivial min cut. Implementation details bound work by the small side volumes, produce a contracted graph of size O(m/Δ), and allow running standard min‑cut routines on the smaller instance.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:19Edge connectivity and global min-cut
- 3:44History cont'd
- 5:34Underlying result
- 8:05Involving cut conductance
- 9:43Non-trivial min-cuts have low-conductance
- 11:03Certify-or-cut
- 24:13Limit concentration and cuts
- 30:05Starting from any vertex on small side of min-cut
- 33:32Balanced min-cut
- 35:29Any non-trivial min-cut
- 40:36Cores to contract in full algorithm
- 43:57Concluding remarks