Given a graph G and a parameter δ, we want to decompose the graph into clusters of diameter δ without cutting too many edges. For any graph that excludes a K_(r,r) minor, Klein, Plotkin and Rao showed that this can be done while cutting only O(r~3/δ) fraction of the edges. This implies a bound on multicommodity max-flow min-cut ratio for such graphs. This result as well as the decomposition theorem have found numerous applications to approximation algorithms and metric embeddings for such graphs. In this paper, we improve the above decomposition results from O(r~3) to O(r~2). This shows that for graphs excluding any minor of size r, the multicommodity max-flow min-cut ratio is at most O(r~2) (for the uniform demand case). This also improves the performance guarantees of several applications of the decomposition theorem.
展开▼
