| Title | : | Breaking folklore barrier for Maximal $k$-edge-connected subgraph partition |
| Speaker | : | Chaitanya Nalam (University of Michigan) |
| Details | : | Mon, 6 Mar, 2023 4:00 PM @ SSB Meeting Room 1 |
| Abstract: | : | In the problem of maximal $k$-edge-connected partition, given a weighted graph $G=(V, E)$ with $n$ vertices and $m$ edges, we need to find the unique partition ${V_1,V_2,cdots}$ of vertex set $V$ such that each induced subgraph $G[V_i]$ has mincut at least $k$. This classical problem has been studied since the 70s. A folklore algorithm takes $tilde{O}(mn)$ time by simply computing the minimum cut recursively. All previous efforts [Henzinger et.al SODA'15, Chechik et al SODA'17, Forster et al SODA'20] can speed up this folklore algorithm only in unweighted or when $k$ is small enough. In this talk, I will explain a new algorithm that breaks this folklore barrier in weighted graphs. It takes $tilde{O}(mn^{0.8})$ time, which is, in particular, independent from $k$. The key technique is to "localize" the famous Karger's random contraction technique. |
