Directed metrics and directed graph partitioning problems

ABSTRACT

The theory of embeddings of finite metrics has provided a powerful toolkit for graph partitioning problems in undirected graphs. The connection comes from the fact that the integrality gaps of mathematical programming relaxations for sparsest cut in undirected graphs is exactly equal to the minimum distortion required to embed certain metrics into l1. No analog of this metric embedding theory exists for directed (asymmetric) metrics, the natural distance functions that arise in considering mathematical relaxations for directed graph partioning problems. We initiate a study of metric embeddings for directed metrics, motivated by understanding directed variants of sparsest cut.It turns out that there are two different ways to formulate sparsest cut in directed graphs (depending on whether one insists on partitioning the graph into two pieces or not). Different subclasses of directed metrics arise in the consideration of mathematical relaxations for these two formulations and the embedding questions that result are quite different. Unlike in the undirected case, where the natural host space is l1, the host space in the directed case is not obvious and depends on the problem formulation. Our work is a first step at understanding this space of directed metrics, the resulting embedding questions and their relationships to directed graph partitioning problems.

REFERENCES

• 1: Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060675]
• 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 , 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]
• 4: J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52:46--52, 1985.
• 5: Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 6: 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
• 7: 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]
• 8: Uriel Feige and Shimon Kogan, Hardness of approximation of the Balanced Complete Bipartite Subgraph problem. Technical Report MCS04-04, Department of Computer Science and Applied Math., Weizmann Institute.
• 9: P. Frankl and V. Rödl, Forbidden intersections. Trans. Amer. Math. Soc., 300:259--286, 1987.
• 10: Anupam Gupta, Improved results for directed multicut, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: M. Hajiaghayi and F. Leighton, On the max-flow min-cut ratio for directed multicommodity flows. Tech Report MIT-LCS-TR-910, 2003.
• 12: Mohammad T. Hajiaghayi and Harald Räcke, An O(√n)-Approximation Algorithm For Directed Sparsest Cut. To appear in IPL.
• 13: P. Indyk and J. Matousek, Low Distortion Embeddings of Finite Metric Spaces, to appear in Handbook of Discrete and Computational Geometry (2nd edition) J. E. Goodman and J. O'Rourke, editors. CRC Press LLC.
• 14: 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]
• 15: F. T. Leighton and S. Rao, An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms. In Proc. 29th FOCS, pages 422--431, 1988.
• 16: N. Linial, E. London and Yu. Rabinovich, The geometry of graphs and some of its algorithmic applications Combinatorica (1995) 15, pp. 215--245
• 17: J. Matousek. Embedding finite metric spaces into Euclidean spaces, chapter in Lectures on discrete geometry. Graduate Texts in Mathematics, Vol. 212, Springer Verlag, 2002.
• 18: Paolo Vitolo, The representation of weighted quasimetric spaces. Rend. Istit. Mat. Univ. Trieste 31 (1999), no. 1--2, 95--100.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems; Combinatorial algorithms

General Terms:
Algorithms, Measurement, Theory