Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs

17^th February 2026, 13:00 Ashton Lecture Theatre
Daniel Vaz
ESIEE Paris, Université Gustave Eiffel

Abstract

Graph 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.
When 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.
The 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.

In 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.
We 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.
At the end of the talk, we explore results for sparsifiers in parameterized settings, as well as future directions of research.

Based on joint work with Syamantak Das and Nikhil Kumar

Additional Materials

• https://dx.doi.org/10.4230/LIPICS.MFCS.2024.45