Speaker: |
Dr. Sagnik Mukhopadhyay (KTH, Stockholm) |

Organiser: |
Arkadev Chattopadhyay |

Date: |
Tuesday, 9 Jun 2020, 14:00 to 15:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

- An O(m log^2 n)-time sequential algorithm: This improves Karger's long-standing O(m log^3 n) bound. Improvements over Karger's bounds were previously known only under a rather strong assumption that the input graph is simple (unweighted without parallel edges) [Henzinger, Rao, Wang, SODA'17; Ghaffari, Nowicki, Thorup, SODA'20]. For unweighted graphs (possibly with parallel edges) and using bit operations, our bound can be further improved.

- An algorithm that requires \tilde O(n) cut queries to compute the min-cut of a weighted graph: This answers an open problem by Rubinstein, Schramm, and Weinberg [ITCS'18], who obtained a similar bound for simple graphs. Our bound is tight up to polylogarithmic factors.

- A dynamic streaming algorithm that requires \tilde O(n) space and O(log n) passes to compute the min-cut: The only previous non-trivial exact min-cut algorithm in this setting is the 2-pass \tilde O(n)-space algorithm on simple graphs [Rubinstein et al., ITCS'18] (observed by Assadi, Chen, and Khanna [STOC'19]).

In contrast to Karger's 2-respecting min-cut algorithm which deploys sophisticated dynamic programming techniques, our approach exploits some cute structural properties so that it only needs to compute the values of \tilde O(n) cuts corresponding to removing \tilde O(n) pairs of tree edges, an operation that can be done quickly in many settings.

This is joint work with Danupon Nanongkai.