IMPROVED BOUNDS FOR THE MAX-FLOW MIN-MULTICUT RATIO FOR PLANAR AND K(R,R)-FREE GRAPHS

We consider the version of the multicommodity flow problem in which th e objective is to maximize the sum of commodities routed. Garg, Vazira ni and Yannakakis proved that the minimum multicut and maximum flow ra tio for this problem can be bounded by O(log k), where k is the number of commodities. In this note we improve this ratio to O(1) for planar graphs, and more generally to O(r3) for graphs with an excluded K(r,r ) minor. The proof is based on the network decomposition theorem of Kl ein, Plotkin and Rao. Our proof is constructive and yields approximati on algorithms, with the same factors, for the minimum multicut problem on such networks.