A Note on Multiflows 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. Each terminal pair has a non-negative demand that is to be routed between the nodes in the pair. A class of optimization problems is obtained when the goal is to route a maximum number of the pairs in the graph subject to the capacity constraints on the edges. Depending on whether routings are fractional, integral or unsplittable, three different versions are obtained; these are commonly referred to respectively as maximum MCF, EDP (the demands are further constrained to be one) and UFP. We obtain the following results in such graphs.

•	An O(rlog rlog n) approximation for EDP and UFP.
•	The integrality gap of the multicommodity flow relaxation for EDP and UFP is .

The integrality gap result above is essentially tight since there exist (planar) instances on which the gap is . These results extend the rather limited number of graph classes that admit poly-logarithmic approximations for maximum EDP. Another related question is whether the cut-condition, a necessary condition for (fractionally) routing all pairs, is approximately sufficient. We show the following result in this context.

•	The flow-cut gap for product multicommodity flow instances is O(log r). This was shown earlier by Rabinovich; we obtain a different proof.