Multicommodity flow, well-linked terminals, and routing problems
Chandra Chekuri, Lucent Bell Labs
February 11, 2005

Abstract

A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a graph G=(V,E) and a set of pairs of vertices (s_1,t_1), (s_2,t_2), ..., (s_k,t_k). The objective is to decide if all the pairs can be connected by edge-disjoint paths. This problem is NP-Complete and we study approximation algorithms for the optimization problem where the goal is to maximize the number of pairs that can be connected (routed).

We focus on the natural multicommodity flow relaxation for EDP and its integrality gap. A simple example shows that the integrality gap of this relaxation is \Omega(\sqrt{n}) even in planar graphs. It has been conjectured that the integrality gap is much smaller if constant congestion is allowed - that is, paths for some c pairs can use an edge. Using randomized rounding, it can be shown that with O(\log n) congestion, the integrality gap is O(1). However, no sub-polynomial bound is known with constant congestion.

We will describe a new framework for undirected graphs that makes substantial progress towards the conjecture. For planar graphs we have shown that with congestion 2 the integrality gap is O(\log n). The key notion of the framework is that of a "well-linked" set of terminals. The talk will highlight the framework, its applications to EDP and other routing problems, and connections to treewidth and multicommodity maxflow-mincut theorems.

Joint work with Sanjeev Khanna (U. Penn) and Bruce Shepherd (Bell Labs).