### Polynomial flow-cut gaps and hardness of directed cut problemsPolynomial flow-cut gaps and hardness of directed cut problems

Access Restriction
Subscribed

 Author Chuzhoy, Julia ♦ Khanna, Sanjeev Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Directed multicut ♦ Hardness of approximation ♦ Sparsest cut Abstract We study the multicut and the sparsest cut problems in directed graphs. In the multicut problem, we are a given an $\textit{n}-vertex$ graph $\textit{G}$ along with $\textit{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 $\textit{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 $\textit{n}).$ Our second result is that both directed multicut and sparsest cut are hard to approximate to within a factor of $2^{Ω(log^{1™&epsis;}$ $\textit{n})$ for any constant &epsis; > 0, unless NP ⊆ ZPP. This improves upon the recent Ω(log $\textit{n}/log$ log $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 2 Page Count 28 Starting Page 1 Ending Page 28

#### Open content in new tab

Source: ACM Digital Library