27 listopada 2023 10:15
[Seminarium ZOK] Daniel Vaz: Good and Efficient Approximation for the Sparsest Cut Problem in Bounded-Treewidth Graphs
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 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.