Multicommodity Flows and Treewidth

We consider multicommodity flow problems in capacitated graphs where the treewidth of the underlying graph is bounded by r. The parameter r is allowed to be a function of the input size. An instance of the problem consists of a capacitated graph and a collection of terminal pairs. The goal is to route a maximum number of the pairs in the graph. Depending on whether routings are fractional, integral or unsplittable we have three different version, commonly referred to as maximum MCF, EDP and UFP. We obtain the following results in such graphs. (a) The flow-cut gap for product multicommodity flow instances is $O(log r)$. This was shown earlier by Rabinovich; we obtain a different proof. (b) An $O(r log r log n)$ approximation for of EDP and UFP. (c) The integrality gap of the multicommodity flow relaxation for EDP and UFP is $O(min{rlog n, sqrt{n} })$. We note that the integrality gap result above is essentially tight since there exist (planar) instances on which the gap is $Omega(min{ r, sqrt{n} })$. These results extend the rather limited number of graph classes that admit polylogarithmic approximations for maximum EDP: trees, expanders and even degree planar graphs.