BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1801
DTSTAMP:20261118T091521Z
SUMMARY:All-Pairs kth Mincuts: Combinatorial and Structural Results
DESCRIPTION:Speaker: Anupam Roy (IIT Kanpur)\n\nAbstract: \nMinimum cuts ar
 e fundamental objects in graph theory. They often admit interesting combin
 atorial results like the Maxflow-Mincut Theorem and compact representation
 s like the Gomory-Hu tree. The classical Gomory-Hu tree shows that althoug
 h there are overall $\\Omega(n^2)$ pairs of vertices\, a single spanning t
 ree compactly preserves all of their mincut values. But does any such stru
 cture survive when we move beyond the optimum? \nWe study this question f
 or $k^{th}$ minimum value cuts\, in short\, \\emph{$k^{th}$-mincuts}\, for
  all pairs of vertices. We show that the Gomory–Hu phenomenon interestin
 gly extends beyond minimum cuts: the $k^{th}$-mincut values between all pa
 irs of vertices can be preserved by storing only $k$ spanning trees. This 
 yields a tight bound of $O(\\min\\{kn\,n^2\\})$ on the number of distinct 
 values. Going beyond values\, we show that the cuts themselves also admit
  a compact representation: a collection of only $O(k\\log n)$ tree-like st
 ructures suffices to store a $k^{th}$ mincut for each pair of vertices. Th
 ese structural results further lead to compact data structures that given 
 any pair of vertices $(u\,v)$\, can report a $k^{th}$ $(u\,v)$-mincut and 
 its value efficiently.\nOverall\, in this talk\, we show that the strong r
 edundancies that exist among all-pairs mincuts does not disappear beyond t
 he optimum -- it continues to exists for all-pairs $k^{th}$ mincuts\, even
  for $k>1$.\n
URL:https://www.tcs.tifr.res.in/web/events/1801
DTSTART;TZID=Asia/Kolkata:20261120T160000
DTEND;TZID=Asia/Kolkata:20261120T170000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR
