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 find 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 find a subset of edges to delete so as to minimize the ratio of the number 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 standard 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 largest gap, achievable for any graph, between the maximum flow value and the minimum cost solution for the corresponding cut problem. Our first result is that the flow-cut gap between maximum multicommodity flow and minimum multicut is˜ (n 1/7 ) in 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 (log n) for both types of flow-cut gaps. We notice that these polynomially large flow-cut gaps are in a sharp contrast to the undirected setting where both these flow-cut gaps are known to be (log n). Our second result is that both directed multicut and sparsest cut are hard to approximate to within a factor of 2 (log 1− n) for any constant > 0, unless NP ⊆ ZPP. This improves upon the recent (log n/ log log n)-hardness result for these problems. We also show that existence of PCP's for NP with perfect completeness, polynomially small soundness, and constant number of queries would imply a polynomial factor hardness of approximation for both these problems. All our results hold for directed acyclic graphs.
Moreover, it is known from the work of Chuzhoy and Khanna REF that the problem in directed graphs is inapproximable to a factor better thanΩ(2 log 1−ε n ).
Polynomial flow-cut gaps and hardness of directed cut problems
JACM
Mathematics Computer Science