Excluded minors, network decomposition, and multicommodity flow

Abstract

In this paper we show that, given a graph and parameters ffi and r, we can find either a Kr;r minor or an edge-cut of size O(mr=ffi) whose removal yields components of weak diameter O(r 2 ffi); i.e., every pair of nodes in such a component are at distance O(r 2 ffi) in the original graph. Using this lemma, we improve the best known bounds for the min-cut max-flow ratio for multicommodity flows in graphs with forbidden small minors. In general graphs, it was known that the ratio is O(log k) for the uniform-demand case (the case where there is a unit-demand commodity between every pair of nodes), and that the ratio is O(log 2 k) for arbitrary demands, where k is the number of commodities. In this paper we show that for graphs excluding any fixed graph as a minor (e.g. planar graphs or bounded-genus graphs), the ratio is O(1) for the uniform-demand case and O(log k) for the arbitrary demand case. For such graphs, our method yields min-ratio cut approximation algorithms wit...