Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems (Extended Abstract)

We study the multicut and the sparsest cut problems in directed graphs. In the multicut problem, we are a given an n-vertex graph G along with k source-sink pairs, and the goal is to nd the minimum cardinality subset of edges whose removal separates all source-sink pairs. The sparsest cut problem has the same input, but the goal is to nd a subset of edges to delete so as to minimize the ratio of deleted edges to the number of source-sink pairs that are separated by this deletion. The natural linear programming relaxation for multicut corresponds, by LP-duality, to the well-studied maximum (fractional) multicommodity flow problem, while the natural LP-relaxation for sparsest cut corresponds to maximum concurrent flow. Therefore, the integrality gap of the linear programming relaxation for multicut/sparsest cut is also the flow-cut gap: the maximum ratio, achievable for any graph, between the maximum flow value and the minimum cost solution for the corresponding cut problem. Starting with the celebrated max flow-min cut theorem of Ford and Fulkerson, flow-cut gaps have played a central role in combinatorial optimization. For many NP-hard network optimization problems, the best known approximation guarantee corresponds to our understanding of the appropriate flow-cut gap. Our rst result is that the flow-cut gap between maximum multicommodity flow and minimum multicut is ~ (n 1=7 )i n directed graphs. We show a similar result for the gap between maximum concurrent flow and sparsest cut in directed graphs. These results improve upon a long-standing lower bound of (logn) for both types of flow-cut gaps. We notice Supported by a grant of the state of New Jersey to the Institute for Advanced Study. y Supported in part by an NSF Career Award CCR-0093117