SPEAKER: Eden Chlamtac, University
TITLE: Approximating Sparsest Cut in Graphs of Bounded
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.