Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Wednesday, November 20, 2024, 02:00 pm

Duration: 30 minutes

Location: OAT S13

Speaker: Yonggang Jiang (Max Planck Institute for Informatics)

New Tools and Faster Algorithms for Vertex Connectivity

We developed new tools for vertex connectivity problems, leading to several breakthrough results. 1. For the most general weighted directed vertex connectivity 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. ***************************************************************************************** Yonggang Jiang is a PhD student at Max Planck Institute for Informatics, advised by Danupon Nanongkai and Sagnik Mukhopadhyay. Before that, he got his bachelor’s degree in computer science at Nanjing University. His research interest is theoretical computer science in general. His current research focus is on developing efficient graph algorithms in various computation models.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login