Pathwidth, trees, and random embeddings

2009/10/08 by James R. Lee, Lee, James R., Anastasios Sidiropoulos +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Metric Geometry (math.MG)

paper · pdf · doi:10.48550/arxiv.0910.1409

openalex publication_date 2009/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that, for every k=1,2,..., every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c for some c=c(k). A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair 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.

Related

• Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families
• On constant multi-commodity flow-cut gaps for directed minor-free graphs
• Random embeddings of bounded degree trees with optimal spread
• Nearly Tight Low Stretch Spanning Trees
• Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1