Sparsest cut is a fundamental graph problem, which models a general notion of balanced separator of a graph, and has uses in graph theory and divide-and-conquer approaches. In this problem, we are given an edge-capacitated graph, together with demands over pairs of vertices, and we want to find a cut that minimizes the ratio between the capacities and demands across the cut. In other words, we aim to separate as much demand as possible using little cut capacity. For general graphs, the best known approximation factor is Õ(sqrt(log n)), and the problem is known to have no constant-approximation under the unique games conjecture.
In this talk, we look at the problem from the point of view of parameterized complexity, by studying the approximability of the problem in the simpler setting of bounded-treewidth graphs (a common structural constraint on the input graph). Previous algorithms in this setting either have large approximation factors (exponential in the treewidth) or are inefficient. We propose a new algorithm framework which unifies all known algorithms for sparsest cut in bounded treewidth, and then show how to obtain improved approximations to the problem. As a result, we give the first efficient (FPT) constant-factor approximation algorithm.
Joint work with P. Chalermsook, M. Kaul, M. Mnich, J. Spoerhase and S. Uniyal, titled « Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter », published in ACM Transactions on Algorithms (2024).
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne