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 n. The integrality gap result above is essentially tight since there exist (planar) instances on which the gap is n. 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.