## Abstract

We study multicommodity routing problems in both edge and node capacitated undirected graphs. The input to each problem is a capacitated graph G = (V, E) and a set Τ of node pairs. In the simplest setting, the goal is to route a unit of flow for as many pairs as possible subject to the edge (node) capacity constraints. If the flow for a routed pair is required to be along a single path, it is the well-studied disjoint paths problem. If we allow fractional routings of the flow, it is known as the all-or-nothing flow problem, The nodes in Τ are referred to as terminals. In recent work [8, 9], the authors obtained the first polylogarithmic approximation algorithms for some edge routing problems. A key idea in these algorithms is to decompose an instance into a collection of instances in which the terminals are well-linked. Informally speaking, a set of nodes is well-linked in a graph if it does not have small separators. A decomposition into well-linked instances was previously achieved in [8] via Räcke's hierarchical graph decomposition for oblivious routing [32]. In this paper, we design a simple new decomposition algorithm that is based on computing sparse cuts in a graph. Our new algorithm improves the earlier results for edge routing problems. Another important advantage of the algorithm is that it also applies to node-capacitated problems. We note that for oblivious routing with node capacities, an Ω(√n) lower bound is known on the congestion [18], and hence the oblivious routing approach cannot yield poly-logarithmic bounds for well-linked decompositions. Using the new decomposition, we obtain a poly-logarithmic approximation for the node capacitated allor-nothing flow problem in general graphs and node-disjoint path problem in planar graphs with O(1) congestion. We also show that the flow-cut gap for product multicommodity flows in node capacitated planar graphs is O(1), improving upon the O(log n) bound from [28].

Original language | English (US) |
---|---|

Pages (from-to) | 183-192 |

Number of pages | 10 |

Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - 2005 |

Externally published | Yes |

Event | 13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States Duration: Nov 7 2005 → Nov 11 2005 |

## Keywords

- All-or-Nothing Plow
- Disjoint Paths
- Flow-Cut Gaps
- Multicommodity Flow
- Network Routing

## ASJC Scopus subject areas

- Software