Abstract
We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound (Chakrabarti et al. in 49th Annual Symposium on Foundations of Computer Science, pp. 761–770, 2008) for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair.
This also improves the largest known gap for planar graphs from \(\frac{3}{2}\) to 2, yielding the first lower bound that does not follow from elementary calculations. Our approach uses the coarse differentiation method of Eskin, Fisher, and Whyte in order to lower bound the distortion for embedding a particular family of shortest-path metrics into L 1.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andoni, A., Deza, M., Gupta, A., Indyk, P., Raskhodnikova, S.: Lower bounds for embedding of edit distance into normed spaces. In: Proceedings of the 14th Annual ACM–SIAM Symposium on Discrete Algorithms (2003)
Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. J. Am. Math. Soc. 21(1), 1–21 (2008)
Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings, and graph partitionings. In: 36th Annual Symposium on the Theory of Computing, pp. 222–231 (2004). J. ACM, to appear
Aumann, Y., Rabani, Y.: An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1), 291–301 (1998)
Benyamini, Y., Lindenstrauss, J.: Geometric Nonlinear Functional Analysis, vol. 1. American Mathematical Society Colloquium Publications, vol. 48. American Mathematical Society, Providence (2000)
Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52(1–2), 46–52 (1985)
Brinkman, B., Karagiozova, A., Lee, J.R.: Vertex cuts, random walks, and dimension reduction in series-parallel graphs. In: 39th Annual Symposium on the Theory of Computing, pp. 621–630 (2007)
Chakrabarti, A., Jaffe, A., Lee, J.R., Vincent, J.: Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums. In: 49th Annual Symposium on Foundations of Computer Science, pp. 761–770 (2008)
Cheeger, J.: Differentiability of Lipschitz functions on metric measure spaces. Geom. Funct. Anal. 9(3), 428–517 (1999)
Cheeger, J., Kleiner, B.: Differentiating maps into l 1 and the geometry of bv functions. Preprint: math/0611954v3 (2006)
Cheeger, J., Kleiner, B.: Generalized differential and bi-Lipschitz nonembedding in L 1. C. R. Math. Acad. Sci. Paris 343(5), 297–301 (2006)
Chekuri, C., Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Embedding k-outerplanar graphs into l 1. SIAM J. Discrete Math. 20(1), 119–136 (2006)
Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Algorithms and Combinatorics, vol. 15. Springer, Berlin (1997)
Diestel, R.: Graph Theory, 3rd edn. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2005)
Eskin, A., Fisher, D., Whyte, K.: Quasi-isometries and rigidity of solvable groups. Preprint (2006)
Franchi, B., Serapioni, R., Serra Cassano, F.: Rectifiability and perimeter in the Heisenberg group. Math. Ann. 321(3), 479–531 (2001)
Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and l 1-embeddings of graphs. Combinatorica 24(2), 233–269 (2004)
Heinonen, J.: Lectures on Analysis on Metric Spaces. Universitext. Springer, New York (2001)
Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: 42nd Annual Symposium on Foundations of Computer Science, pp. 10–33. IEEE Computer Society, Los Alamitos (2001)
Khot, S., Naor, A.: Nonembeddability theorems via Fourier analysis. Math. Ann. 334(4), 821–852 (2006)
Khot, S., Vishnoi, N.: The unique games conjecture, integrability gap for cut problems and embeddability of negative type metrics into ℓ 1. In: 46th Annual Symposium on Foundations of Computer Science, pp. 53–62. IEEE Computer Society, Los Alamitos (2005)
Lee, J.R., Naor, A.: l p metrics on the Heisenberg group and the Goemans–Linial conjecture. In: 47th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos (2006)
Linial, N.: Finite metric-spaces—combinatorics, geometry and algorithms. In: Proceedings of the International Congress of Mathematicians, vol. III, Beijing, 2002, pp. 573–586. Higher Education Press, Beijing (2002)
Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215–245 (1995)
Matoušek, J.: Open problems on low-distortion embeddings of finite metric spaces. http://kam.mff.cuni.cz/~matousek/metrop.ps
Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)
Newman, I., Rabinovich, Y.: A lower bound on the distortion of embedding planar metrics into Euclidean space. Discrete Comput. Geom. 29(1), 77–81 (2003)
Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Comb. Theory Ser. B 31(1), 75–81 (1981)
Pansu, P.: Métriques de Carnot–Carathéodory et quasiisométries des espaces symétriques de rang un. Ann. Math. (2) 129(1), 1–60 (1989)
Author information
Authors and Affiliations
Corresponding author
Additional information
J.R. Lee’s research partially supported by NSF CAREER award CCF-0644037. Part of this research was completed while the author was a postdoctoral fellow at the Institute for Advanced Study, Princeton.
P. Raghavendra’s research supported in part by NSF grant CCF-0343672.
Rights and permissions
About this article
Cite this article
Lee, J.R., Raghavendra, P. Coarse Differentiation and Multi-flows in Planar Graphs. Discrete Comput Geom 43, 346–362 (2010). https://doi.org/10.1007/s00454-009-9172-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9172-4