Discrete Mathematics and Optimization Seminar

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).