Hardness of cut problems in directed graphs

ABSTRACT

We study the approximability of the multicut and the (non-bipartite) sparsest cut problems in directed graphs. In the multicut problem, we are a given a graph G along with k source-sink pairs, and the goal is to find a smallest subset of edges whose deletion 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. Study of algorithms for cut problems is intimately connected to the dual notion of flows in networks, and many approximation algorithms for cut problems use a flow solution as a starting point. The best known approximation algorithm for directed multicut is based on this approach and gives an O(√n)-approximation. On the other hand, the gap between the maximum multicommodity flow and the minimum multicut is known to be Ω(min(k , log n)). While this flow-cut gap may be interpreted as an evidence of inherent difficulty in designing good approximation algorithms for directed multicut, the strongest hardness result known is an APX-hardness. Even assuming the Unique Games Conjecture, only an ω(1)-hardness is known. Similar bounds hold for the directed sparsest cut problem.Our main result is that directed multicut is Ω(log n / log log n)-hard to approximate unless NP ⊆ DTIME (n^{polylog n}). We show that this hardness result holds even when we allow a bicriteria relaxation, where the approximate solution is required to separate only a constant fraction of the pairs. This bicriteria hardness allows us to infer an Ω(log n / log log n)-hardness for the directed (non-bipartite) sparsest cut problem.

REFERENCES

• 1: 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 ]
• 2: 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]
• 3: 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]
• 4: 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]
• 5: 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]
• 6: 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]
• 7: 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]
• 8: 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
• 9: 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]
• 10: 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]
• 11: 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.
• 12: L. R. Ford, D. R. Fulkerson, 1962. Flows in Networks. Princeton University Press, Princeton, NJ.
• 13: 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]
• 14: 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
• 15: Anupam Gupta, Improved results for directed multicut, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 16: 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]
• 17: 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]
• 18: 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]
• 19: 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]
• 20: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 21: 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