Good and Efficient Approximation for the Sparsest Cut Problem in Bounded-Treewidth Graphs

Speaker: Daniel Vaz, LAMSADE

Room: B507

Date: 18/12/2023 14:00

Abstract:

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 it, 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 it. 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 Õ((log n)^0.5), and the problem is known to have no constant-approximation under the unique games conjecture.

In this talk, we focus on the simpler setting of bounded-treewidth graphs, and present new constant-factor approximation algorithms. Known algorithms in this setting are either inefficient or have large approximation factors. We will see that these algorithms can be framed as specific cases of a general algorithm with uses beyond sparsest cut, and then show how to combine the best of both approaches to obtain efficient and good approximations to the problem. As a result, we give the first constant-factor approximation algorithm running in FPT time.