Access Restriction

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

   Open content in new tab
Source: ACM Digital Library