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 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^{Ω(log1−&epsis; n)} for any constant &epsis; > 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.

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, Hardness of Approximating Problems on Cubic Graphs, Proceedings of the Third Italian Conference on Algorithms and Complexity, p.288-298, March 12-14, 1997
• 3: Christoph Ambuhl , Monaldo Mastrolilli , Ola Svensson, Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.329-337, October 21-23, 2007 [doi>10.1109/FOCS.2007.32]
• 4: 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]
• 5: 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]
• 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: 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]
• 8: 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]
• 9: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT, Computational Complexity, v.15 n.2, p.94-114, June 2006 [doi>10.1007/s00037-006-0210-9]
• 10: Joseph Cheriyan , Howard Karloff , Yuval Rabani†, Approximating Directed Multicuts, Combinatorica, v.25 n.3, p.251-269, May 2005 [doi>10.1007/s00493-005-0015-5]
• 11: 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]
• 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: Chuzhoy, J., and Khanna, S. 2006b. Hardness of directed routing with congestion. ECCC Technical Report TR06-109.
• 14: 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]
• 15: 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]
• 16: Uriel Feige, Relations between Average Case Complexity and Approximation Complexity, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.5, May 21-24, 2002
• 17: Feige, U., and Kogan, S. 2004. Hardness of approximation of the balanced complete bipartite subgraph problem. Tech. Rep. Technical Report MCS04-04, Department of Computer Science and Applied Math., The Weizmann Institute of Science, Haifa, Israel.
• 18: Ford, L., and Fulkerson, D. 1962. Flows in networks. Princeton University Press, Princeton, NJ.
• 19: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
• 20: Anupam Gupta, Improved results for directed multicut, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 21: Guruswami, V., and Talwar, K. 2006. Hardness of low congestion routing in directed graphs. ECCC Technical Report TR06-141.
• 22: 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]
• 23: 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]
• 24: 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]
• 25: Yana Kortsarts , Guy Kortsarz , Zeev Nutov, Greedy approximation algorithms for directed multicuts, Networks, v.45 n.4, p.214-217, July 2005 [doi>10.1002/net.v45:4]
• 26: 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]
• 27: 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

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Directed multicut, hardness of approximation, sparsest cut