BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1063
DTSTAMP:20230914T125949Z
SUMMARY:Weighted min-cut: Sequential\, Cut-query and Streaming algorithms
DESCRIPTION:Speaker: Dr. Sagnik Mukhopadhyay (KTH\, Stockholm)\n\nAbstract:
  \nAbstract: Consider the following 2-respecting min-cut problem: Given a 
 weighted graph G and its spanning tree T\, find the minimum cut among the 
 cuts that contain at most two edges in T. This problem is an important sub
 routine in Karger's celebrated randomized near-linear-time min-cut algorit
 hm [STOC'96]. I will present a new approach to this problem which can be e
 asily implemented in many settings\, leading to the following randomized m
 in-cut algorithms for weighted graphs.\n- An O(m log^2 n)-time sequential 
 algorithm: This improves Karger's long-standing O(m log^3 n) bound. Improv
 ements over Karger's bounds were previously known only under a rather stro
 ng assumption that the input graph is simple (unweighted without parallel 
 edges) [Henzinger\, Rao\, Wang\, SODA'17\; Ghaffari\, Nowicki\, Thorup\, S
 ODA'20]. For unweighted graphs (possibly with parallel edges) and using bi
 t operations\, our bound can be further improved.\n- An algorithm that req
 uires \\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.\n- A dynamic streaming algorithm that requi
 res \\tilde O(n) space and O(log n) passes to compute the min-cut: The onl
 y previous non-trivial exact min-cut algorithm in this setting is the 2-pa
 ss \\tilde O(n)-space algorithm on simple graphs [Rubinstein et al.\, ITCS
 '18] (observed by Assadi\, Chen\, and Khanna [STOC'19]).\nIn contrast to K
 arger's 2-respecting min-cut algorithm which deploys sophisticated dynamic
  programming techniques\, our approach exploits some cute structural prope
 rties so that it only needs to compute the values of \\tilde O(n) cuts cor
 responding to removing \\tilde O(n) pairs of tree edges\, an operation tha
 t can be done quickly in many settings.\nThis is joint work with Danupon N
 anongkai.\n
URL:https://www.tcs.tifr.res.in/web/events/1063
DTSTART;TZID=Asia/Kolkata:20200609T140000
DTEND;TZID=Asia/Kolkata:20200609T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR