Monday October 15th at 4.30pm

between cuts and flows plays a central role in many algorithms. The performance of several algorithms

is tied to the flow-cut gap: the worst-case ratio between multicommodity flow and multicut.

The flow-cut gap in undirected graphs is well-understood, and is known to be \Theta(log n). However,

so far, the question of flow-cut gap in directed graphs has remained wide open. The best known lower

bound is logarithmic while the best known upper bound is polynomial. In a sharp contrast to the

undirected case, we will show in this talk that the flow-cut gap in directed graphs can be

polynomially large. Based on our flow-cut gap construction, we will also briefly describe a strong

hardness of approximation result for the directed multicut and the directed sparsest cut problem.

This is joint work with Julia Chuzhoy (TTI).