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