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.
Similar content being viewed by others
References
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).
Yair Bartal: Probabilistic approximations of metric space and its algorithmic application, in: 37th Annual Symposium on Foundations of Computer Science, 183–193, October 1996.
Yair Bartal: On approximating arbitrary metrics by tree metrics, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 183–193, 1998.
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.
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).
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.
Eden Chlamtac, Robert Krauthgamer and Prasad Raghavendra: Approximating sparsest cut in graphs of bounded treewidth, in: APPROX-RANDOM, 124–137, 2010.
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.
Reinhard Diestel: Graph theory, volume 173 of Graduate Texts in Mathematics, Springer-Verlag, Berlin, third edition, 2005.
L. R. Ford and D. R. Fulkerson: Maximal flow through a network, Canadian Journal of Mathematics 8 (1956), 399–404.
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.
Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair: Cuts, trees and l 1-embeddings of graphs, Combinatorica 24(2) (2004), 233–269.
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.
R. M. Karp: A 2k-competitive algorithm for the circle, Manuscript, 1989.
N. Linial, E. London and Y. Rabinovich: The geometry of graphs and some of its algorithmic applications, Combinatorica 15(2) (1995), 215–245.
László Lovász: Graph minor theory, Bull. Amer. Math. Soc. (N.S.) 43(1) (2006), 75–86 (electronic).
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.
James R. Lee and Prasad Raghavendra: Coarse differentiation and multi-flows in planar graphs, Discrete Comput. Geom. 43(2) (2010), 346–362.
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.
Haruko Okamura and P. D. Seymour: Multicommodity flows in planar graphs, J. Combin. Theory Ser. B 31(1) (1981), 75–81.
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.
Neil Robertson and P. D. Seymour: Graph minors. I. Excluding a forest, J. Combin. Theory Ser. B 35(1) (1983), 39–61.
Author information
Authors and Affiliations
Corresponding author
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
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
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-013-2685-8