Polynomial flow-cut gaps and hardness of directed cut problems

ABSTRACT

We study the multicut and the sparsest cut problems in directed graphs. In the multicut problem, we are a given an n-vertex graphG 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 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, whilethe natural 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 maximum ratio, achievable for any graph,between the maximum flow value and the minimum cost solution for the corresponding cut problem. Starting with the celebrated max flow-mincut theorem of Ford and Fulkerson, flow-cut gaps have played acentral role in combinatorial optimization. For many NP-hard network optimization problems, the best known approximation guarantee corresponds to our understanding of the appropriate flow-cut gap.

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 cutin directed graphs. These results improve upon a long-standing lowerbound of Ω(log n) for both types of flow-cut gaps. We notice that these polynomially large flow-cut gaps are in a sharp contrastto the undirected setting where both these flow-cut gaps are knownto be Θ(log n). Our second result is that both directed multicut and sparsest cut are hard to approximate to within a factor of 2^Ω(log1-ε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 showthat 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.

REFERENCES

• 1: Amit Agarwal , Noga Alon , Moses S. Charikar, Improved approximation for directed cut problems, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250888]
• 2: Paola Alimonti , Viggo Kann, Some APX-completeness results for cubic graphs, Theoretical Computer Science, v.237 n.1-2, p.123-134, April 28, 2000 [doi>10.1016/S0304-3975(98)00158-3]
• 3: Matthew Andrews , Lisa Zhang, Logarithmic hardness of the directed congestion minimization problem, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132592]
• 4: Sanjeev Arora , James R. Lee , Assaf Naor, Euclidean distortion and the sparsest cut, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060673]
• 5: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 6: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 7: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 8: M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
• 9: Moses Charikar , Konstantin Makarychev , Yury Makarychev, Directed metrics and directed graph partitioning problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.51-60, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109564]
• 10: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, On the Hardness of Approximating Multicut and Sparsest-Cut, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.144-153, June 11-15, 2005 [doi>10.1109/CCC.2005.20]
• 11: J. Cheriyan , H. Karloff , Y. Rabani, Approximating Directed Multicuts, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.320, October 14-17, 2001
• 12: Julia Chuzhoy , Sanjeev Khanna, Hardness of cut problems in directed graphs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132593]
• 13: [13] J. Chuzhoy and S. Khanna. Hardness of Directed Routing with Congestion. ECCC Technical Report TR06-109, August 2006. http://eccc.hpi-web.de/eccc-reports/2006/TR06-109/index.html.
• 14: Julia Chuzhoy , Venkatesan Guruswami , Sanjeev Khanna , Kunal Talwar, Hardness of routing with congestion in directed graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250816]
• 15: E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297]
• 16: Irit Dinur , Eldar Fischer , Guy Kindler , Ran Raz , Shmuel Safra, PCP characterizations of NP: towards a polynomially-small error-probability, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.29-40, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301265]
• 17: Irit Dinur , Shmuel Safra, On the hardness of approximating label-cover, Information Processing Letters, v.89 n.5, p.247-254, 16 March 2004 [doi>10.1016/j.ipl.2003.11.007]
• 18: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 19: [19] U. Feige and S. Kogan. Hardness of Approximation of the Balanced Complete Bipartite Subgraph Problem. Technical Report MCS04-04, Department of Computer Science and Applied Math., The Weizmann Institute of Science, 2004.
• 20: [20] L. R. Ford, D. R. Fulkerson, 1962. Flows in Networks. Princeton University Press, Princeton, NJ.
• 21: [21] V. Guruswami and K. Talwar. Hardness of Low Congestion Routing in Directed Graphs. ECCC Technical Report TR06-141, November 2006, http://eccc.hpi-web.de/eccc-reports/2006/TR06- 141/index.html.
• 22: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate max-flow min-(multi)cut theorems and their applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.698-707, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167266]
• 23: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.64-75, July 05-09, 1993
• 24: Anupam Gupta, Improved results for directed multicut, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 25: Mohammad Taghi Hajiaghayi , Harald Räcke, An O(√n)-approximation algorithm for directed sparsest cut, Information Processing Letters, v.97 n.4, p.156-160, 28 February 2006 [doi>10.1016/j.ipl.2005.10.005]
• 26: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 27: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 28: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 29: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 30: Michael Saks , Alex Samorodnitsky , Leonid Zosin, A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks, Combinatorica, v.24 n.3, p.525-530, July 2004 [doi>10.1007/s00493-004-0031-x]

INDEX TERMS

General Terms:
Algorithms, Theory

Keywords:
concurrent flow, directed multicut, directed sparsest cut, flow-cut gaps, hardness of approximation, multicommodity flow