Speaker: Yonggang Jiang Max Planck Institute for Informatics
Time: 2025-01-06 15:00-2025-01-06 16:00
Venue: FIT 1-222

Abstract:

We developed new tools for vertex Min-cut problems, leading to several breakthrough results.1. For the most general weighted directed vertex Min-cut problem, we present a deterministic algorithm with an almost $mn$ time complexity, matching the running time of the current best randomized algorithm by [HRG, FOCS’96]. Previously, only trivial algorithms (running $n^2$ max flows) were known.2. For undirected unweighted graphs, we provide a deterministic algorithm with an almost $mk$ time complexity, where $k$ is the vertex connectivity of the graph. This result subsumes all previous results—$(n + k^2)m$ [Even’75], $n^{0.5}mk$ [Gabow, FOCS’00], $m2^{O(k^2)}$ [SY, FOCS’22]—up to subpolynomial factors.3. In parallel and distributed models, we provide an almost perfect reduction of undirected unweighted vertex connectivity to max-flow. Previously, such a reduction was only known in the sequential model [LNPSY, STOC’21].At the heart of our algorithms is a new graph decomposition technique called common-neighborhood clustering. Like many graph decomposition techniques, it serves as a versatile tool for parallelization and derandomization. In this talk, we will focus on introducing this tool by providing a simple framework for computing vertex connectivity, which can be extended to all of our results by combining it with the appropriate model-related tools.

Short Bio:

Yonggang Jiang is currently a PhD student at Max Planck Institute for Informatics, advised by Danupon Nanongkai. Before that, he got his Bachelor’s Degree in Computer Science at Nanjing University in 2021. His research interest is theoretical computer science in general. His current research focus is on developing efficient graph algorithms, especially cut and flow algorithms, in various computation models.