Vertex Connectivity in Poly-logarithmic Max-flows

on YouTube ↗07m

" summary

Proves vertex connectivity (global and s–t) using only poly-logarithmic max-flows instead of the previous ~n max-flow runs, by generating many sublinear-size max-flow instances whose total size is near-linear; combined with the recent almost-linear max-flow solver this yields an almost-linear time algorithm. Techniques include isolating-cut lemmas, sublinear-time kernelization, sketching and sparse-recovery; algorithm is randomized and leaves deterministic and weighted versions as open problems.

AI-written summary · about

" related talks

• 01h 09mElectrical Flows Primitive and Fast Graph AlgorithmsAleksander Madry · Fast Algorithms via Spectral Methods 2014
• 35mSuperlinear Lower Bounds for Multipass Graph ProcessingKrzysztof Onak · Information Theory in Complexity Theory and Combinatorics 2015
• 52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance ProblemsKarl Bringmann · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 17mSolving Max-Min Fair Resource Allocations Quickly on Large GraphsUmesh Krishnaswamy, Himanshu Raj, Santiago Segarra, Pooria Namyar, Behnaz Arzani, Srikanth Kandula, Daniel Crankshaw, Ramesh Govindan · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 01h 05mGraph Algorithms in the MPC ModelSlobodan Mitrovic · Sublinear Algorithms Boot Camp 2024
• 23mTowards General and Tight Hardness Results for Graph ProblemsChristian Komusiewicz · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 41mRerouting Flows when Links FailJannik Matuschke · Real-Time Decision Making 2018
• 01h 37mGraphons and Graph Limits 3Jennifer Chayes · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp