SPEAKER: Eden Chlamtac, University
of Toronto

TITLE: Approximating Sparsest Cut in Graphs of Bounded
Treewidth

ABSTRACT:

We examine the Sparsest Cut problem. This is a
fundamental NP-hard problem which is intimately related to several graph
parameters, such as edge-expansion, minimum balanced cut and conductance, and
has surprising connections to the theory of Metric Embeddings.

We consider this problem on graphs of bounded treewidth.
This is a well-studied class of graphs, and many problems that are generally
NP-hard can be solved efficiently on these graphs; for example, uniform-demand
Sparsest Cut, where every pair of vertices has unit demand.

We give a constant-factor approximation algorithm for
Sparsest Cut with general demands in bounded treewidth graphs. Our algorithm
relies crucially on the Sherali-Adams hierarchy of LP relaxations.

This talk is based on joint work with Robert Krauthgamer
and Prasad Raghavendra.