Pathwidth, trees, and random embeddings

Original · EN

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.