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