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.
In REF it is shown that unless NP ⊆ ZPP the Directed multicut problem admits no 2 log 1− n ratio for any constant .
Polynomial flow-cut gaps and hardness of directed cut problems
JACM
Mathematics Computer Science