Discrete Mathematics and Optimization Seminar

---

SANJEEV KHANNA
University of Pennsylvania
Monday October 15th at 4.30pm
Burnside 1205



Title. Cuts and Flows in Directed Graphs

Abstract. Cuts and flows are among the most well-studied concepts in combinatorial optimization. The duality
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).