Pathwidth, trees, and random embeddings. (English) Zbl 1349.05091
Summary: We prove that, for every integer \(k\geq 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 A. Gupta et al. [Combinatorica 24, No. 2, 233–269 (2004; Zbl 1056.05040)] states that for every minor-closed family of graphs \(\mathcal F\), there is a constant \(c(\mathcal F)\) such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from \(\mathcal F\) is at most \(c(\mathcal F)\). The preceding embedding theorem is used to prove this conjecture whenever the family \(\mathcal F\) does not contain all trees.
MSC:
| 05C12 | Distance in graphs |
| 05C21 | Flows in graphs |
| 05C05 | Trees |
| 05C80 | Random graphs (graph-theoretic aspects) |
Citations:
Zbl 1056.05040References:
| [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). · Zbl 0910.05038 · doi:10.1137/S0097539794285983 |
| [2] | Bartal, Y., Probabilistic approximations of metric space and its algorithmic application, 183-193 (1996) |
| [3] | Bartal, Y., On approximating arbitrary metrics by tree metrics, 183-193 (1998) · Zbl 1029.68951 |
| [4] | Carroll, D.; Goel, A., Lower bounds for embedding into distributions over excluded minor graph families (2004) · Zbl 1111.68457 |
| [5] | Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair: Embedding k-outerplanar graphs into l1, SIAM J. Discrete Math. 20(1) (2006), 119-136 (electronic). · Zbl 1111.05022 · doi:10.1137/S0895480102417379 |
| [6] | Chakrabarti, A.; Jaffe, A.; Lee, J. R.; Vincent, J., Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums (2008) |
| [7] | Chlamtac, E.; Krauthgamer, R.; Raghavendra, P., Approximating sparsest cut in graphs of bounded treewidth, 124-137 (2010) · Zbl 1304.68213 |
| [8] | Chekuri, C.; Shepherd, F. B.; Weibel, C., Flow-cut gaps for integer and fractional multiflows, 1198-1208 (2010) · Zbl 1288.05119 |
| [9] | Reinhard Diestel: Graph theory, volume 173 of Graduate Texts in Mathematics, Springer-Verlag, Berlin, third edition, 2005. · Zbl 1074.05001 |
| [10] | L. R. Ford and D. R. Fulkerson: Maximal flow through a network, Canadian Journal of Mathematics8 (1956), 399-404. · Zbl 0073.40203 · doi:10.4153/CJM-1956-045-5 |
| [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. · Zbl 1071.68082 · doi:10.1016/j.jcss.2004.04.011 |
| [12] | Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair: Cuts, trees and l1-embeddings of graphs, Combinatorica24(2) (2004), 233-269. · Zbl 1056.05040 · doi:10.1007/s00493-004-0015-x |
| [13] | Indyk, P.; Sidiropoulos, A., Probabilistic embeddings of bounded genus graphs into planar graphs (2007) · Zbl 1207.05040 |
| [14] | R. M. Karp: A 2k-competitive algorithm for the circle, Manuscript, 1989. |
| [15] | N. Linial, E. London and Y. Rabinovich: The geometry of graphs and some of its algorithmic applications, Combinatorica15(2) (1995), 215-245. · Zbl 0827.05021 · doi:10.1007/BF01200757 |
| [16] | László Lovász: Graph minor theory, Bull. Amer. Math. Soc. (N.S.)43(1) (2006), 75-86 (electronic). · Zbl 1082.05082 · doi:10.1090/S0273-0979-05-01088-8 |
| [17] | Tom Leighton and Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM46(6) (1999), 787-832. · Zbl 1065.68666 · doi:10.1145/331524.331526 |
| [18] | James R. Lee and Prasad Raghavendra: Coarse differentiation and multi-flows in planar graphs, Discrete Comput. Geom. 43(2) (2010), 346-362. · Zbl 1213.05056 · doi:10.1007/s00454-009-9172-4 |
| [19] | Lee, J. R.; Sidiropoulos, A., On the geometry of graphs with a forbidden minor (2009) · Zbl 1304.05137 |
| [20] | Haruko Okamura and P. D. Seymour: Multicommodity flows in planar graphs, J. Combin. Theory Ser. B31(1) (1981), 75-81. · Zbl 0465.90029 · doi:10.1016/S0095-8956(81)80012-3 |
| [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. · Zbl 0890.05021 · doi:10.1007/PL00009336 |
| [22] | Neil Robertson and P. D. Seymour: Graph minors. I. Excluding a forest, J. Combin. Theory Ser. B35(1) (1983), 39-61. · Zbl 0521.05062 · doi:10.1016/0095-8956(83)90079-5 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
