Excluded minors, network decomposition, and multicommodity flow
Philip N. Klein, Serge A. Plotkin, Satish S. Rao · 1993
In this paper we show that, given a graph and parameters 6 and r, we can find either a K,,.minor or an edge-cut of size O(mT/6) whose removal yields components of weak diameter O(T-26); i.e., every pair of nodes in such a component are at distance 0(r26) in the original graph.Using this lemma, we improve the best known bounds for the rein-cut max-flow ratio for mukicommodity 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 0(log2 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 boundedgenus 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 rein-ratio cut approximation algorithms with performance bounds that match the above ratios.Computation of such cuts is a basic step for a variety of approximation algorithms for NP-complete problems.