Skip to main content
Springer Nature Link
Log in

Pathwidth, trees, and random embeddings

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

We prove that, for every integer k≥1, every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c=c(k), independent of the graph size. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair [12] states that for every minor-closed family of graphs F, there is a constant c(F) such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from F is at most c(F). The preceding embedding theorem is used to prove this conjecture whenever the family F does not contain all trees.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Yonatan Aumann and Yuval Rabani: An O(logk) approximate min-cut max-flow theorem and approximation algorithm, SIAM J. Comput. 27(1) (1998), 291–301 (electronic).

    Article  MATH  MathSciNet  Google Scholar 

  2. Yair Bartal: Probabilistic approximations of metric space and its algorithmic application, in: 37th Annual Symposium on Foundations of Computer Science, 183–193, October 1996.

    Google Scholar 

  3. Yair Bartal: On approximating arbitrary metrics by tree metrics, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 183–193, 1998.

    Google Scholar 

  4. D. Carroll and A. Goel: Lower bounds for embedding into distributions over excluded minor graph families, in: Proceedings of the 12th European Symposium on Algorithms, 2004.

    Google Scholar 

  5. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair: Embedding k-outerplanar graphs into l 1, SIAM J. Discrete Math. 20(1) (2006), 119–136 (electronic).

    Article  MATH  MathSciNet  Google Scholar 

  6. Amit Chakrabarti, Alexander Jaffe, James R. Lee and Justin Vincent: Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums, in: IEEE Symposium on Foundations of Computer Science, 2008.

    Google Scholar 

  7. Eden Chlamtac, Robert Krauthgamer and Prasad Raghavendra: Approximating sparsest cut in graphs of bounded treewidth, in: APPROX-RANDOM, 124–137, 2010.

    Google Scholar 

  8. Chandra Chekuri, F. Bruce Shepherd and Christophe Weibel: Flow-cut gaps for integer and fractional multiflows, in: Proceedings of the 21st Annual ACMSIAM Symposium on Discrete Algorithms, 1198–1208, 2010.

    Google Scholar 

  9. Reinhard Diestel: Graph theory, volume 173 of Graduate Texts in Mathematics, Springer-Verlag, Berlin, third edition, 2005.

    Google Scholar 

  10. L. R. Ford and D. R. Fulkerson: Maximal flow through a network, Canadian Journal of Mathematics 8 (1956), 399–404.

    Article  MATH  MathSciNet  Google Scholar 

  11. Jittat Fakcharoenphol, Satish Rao and Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics, J. Comput. Syst. Sci. 69(3) (2004), 485–497.

    Article  MATH  MathSciNet  Google Scholar 

  12. Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair: Cuts, trees and l 1-embeddings of graphs, Combinatorica 24(2) (2004), 233–269.

    Article  MATH  MathSciNet  Google Scholar 

  13. Piotr Indyk and Anastasios Sidiropoulos: Probabilistic embeddings of bounded genus graphs into planar graphs, in: Proceedings of the 23rd Annual Symposium on Computational Geometry ACM, 2007.

    Google Scholar 

  14. R. M. Karp: A 2k-competitive algorithm for the circle, Manuscript, 1989.

    Google Scholar 

  15. N. Linial, E. London and Y. Rabinovich: The geometry of graphs and some of its algorithmic applications, Combinatorica 15(2) (1995), 215–245.

    Article  MATH  MathSciNet  Google Scholar 

  16. László Lovász: Graph minor theory, Bull. Amer. Math. Soc. (N.S.) 43(1) (2006), 75–86 (electronic).

    Article  MATH  MathSciNet  Google Scholar 

  17. Tom Leighton and Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46(6) (1999), 787–832.

    Article  MATH  MathSciNet  Google Scholar 

  18. James R. Lee and Prasad Raghavendra: Coarse differentiation and multi-flows in planar graphs, Discrete Comput. Geom. 43(2) (2010), 346–362.

    Article  MATH  MathSciNet  Google Scholar 

  19. J. R. Lee and A. Sidiropoulos: On the geometry of graphs with a forbidden minor, in: 41st Annual Symposium on the Theory of Computing, 2009.

    Google Scholar 

  20. Haruko Okamura and P. D. Seymour: Multicommodity flows in planar graphs, J. Combin. Theory Ser. B 31(1) (1981), 75–81.

    Article  MATH  MathSciNet  Google Scholar 

  21. Y. Rabinovich and R. Raz: Lower bounds on the distortion of embedding finite metric spaces in graphs, Discrete Comput. Geom. 19(1) (1998), 79–94.

    Article  MATH  MathSciNet  Google Scholar 

  22. Neil Robertson and P. D. Seymour: Graph minors. I. Excluding a forest, J. Combin. Theory Ser. B 35(1) (1983), 39–61.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science & Engineering, University of Washington, Washington, USA

    James R. Lee

  2. Toyota Technological Institute at Chicago, Chicago, USA

    Anastasios Sidiropoulos

Authors
  1. James R. Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anastasios Sidiropoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to James R. Lee.

Additional information

A portion of the results in this paper were announced at the 41st Annual Symposium on the Theory of Computing [19].

Research partially supported by NSF grant CCF-0644037 and a Sloan Research Fellowship.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lee, J.R., Sidiropoulos, A. Pathwidth, trees, and random embeddings. Combinatorica 33, 349–374 (2013). https://doi.org/10.1007/s00493-013-2685-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-013-2685-8

Mathematics Subject Classification (2010)

Search

Navigation