Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems

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 ow problem, while the standard LP-relaxation for sparsest cut corresponds to maximum concurrent ow. Therefore, the integrality gap of the linear programming relaxation for multicut/sparsest cut is also the ow-cut gap: the maximum ratio, achievable for any graph, between the maximum ow value and the minimum cost solution for the corresponding cut problem. Starting with the celebrated max ow-min cut theorem of Ford and Fulkerson, ow-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 ow-cut gap