BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T090228Z
UID:Seminar-dept-1314@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260217T130000
DTEND:20260217T140000
SUMMARY:School Seminar Series
DESCRIPTION:Daniel Vaz: Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs\n\nGraph compression or sparsification is a fundamental question in information theory and computer science. Given a graph with a special set of vertices called terminals, we ask if it is possible to find a smaller graph, named sparsifier, which preserves some property of the graph with respect to the terminals.\n\nWhen considering flows in a graph, two types of sparsifiers are particularly important: cut sparsifiers, which preserve the minimum cuts separating sets of terminals; and flow sparsifiers, a more powerful version which preserves the every multicommodity flow between terminals.\n\nThe goal is to obtain sparsifiers that are of small size as a function of the number of terminals, and independent of the size of the graph.\n\n\n\nIn this talk, we look at known results for cut and flow sparsifiers, including best-known techniques for cut sparsifiers and lower bounds for both cut and flow sparsifiers.\n\nWe then move on to some recent work on cut and flow sparsifiers on graphs with simple structure, focusing on quasi-bipartite graphs, which are used in lower bounds for cut sparsifiers. Our main contribution is a new technique to construct sparsifiers that exploits connections to polyhedral geometry, and that can be generalized to graphs with a small separator that separates the graph into small components.\n\nAt the end of the talk, we explore results for sparsifiers in parameterized settings, as well as future directions of research.\n\n\n\nBased on joint work with Syamantak Das and Nikhil Kumar\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1314
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR