Cuts and flows are among the most basic graph theoretic notions.
Applications that require solving graph cut or flow problems
arise in almost every area of computer science. The study of the
connection between flows and cuts dates back to the late fifties when
Ford and Fulkerson proved that in the single-commodity environment,
minimum cut equals maximum flow in any graph. A natural generalization
of this result would be establishing the relationship between flows
and cuts in the presence of multiple commodities. This relationship is
usually expressed via the notion of flow-cut gap: the maximum ratio,
achievable for any graph, between the maximum multi-commodity flow and
the corresponding cut value, called minimum multicut.

Flow-cut gaps have been extensively studied for more than five decades
now, and they are widely used in the design and the analysis of
algorithms. One of the major breakthroughs in this area is a complete
understanding of the flow-cut gap in undirected graphs, which was
proved to be logarithmic. In spite of this success, the flow-cut gaps
have remained poorly understood in directed graphs. In particular, it
has remained an open question whether the flow-cut gap in directed
graphs is also logarithmic. In this talk we will answer this question
in the negative by showing that, in sharp contrast to the undirected
case, the flow-cut gap in directed graphs is polynomial.