Abstract:

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 establishing 
the flow-cut gap in undirected graphs, which was shown 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.

Joint work with Sanjeev Khanna.