Cut Problems in Graphs: Algorithms and Complexity

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Cut Problems in Graphs: Algorithms and Complexity
Speaker:Julia Chuzhoy
Affiliation:Massachusetts Institute of Technology and Member, School of Mathematics
Date:Tuesday, November 14
Time/Room:10:30am - 12:30pm/S-101

Cut problems are fundamental to combinatorial optimization, and they naturally arise as intermediate problems in algorithm design. The study of cut problems is inherently connected to the dual notion of flows. In particular, starting with the celebrated max flow-min cut theorem, flow-cut gaps have been extensively studied and are the basis for many graph partitioning and routing algorithms. In this talk we will focus on several well-known cut problems in graphs, including multicut and sparsest cut. We will survey some existing algorithmic techniques and also present some new hardness of approximation results. In particular, we will show that the worst case flow-cut gap in directed graphs is polynomial. This is in sharp contrast to undirected graphs, where the gap is known to be only logarithmic. Based on joint work with Sanjeev Khanna.