Abstract

Given a graph G (possibly directed) and set of pairs of vertices S the maximum edge disjoint paths problem (EDP) is the optimization problem of maximizing the number of pairs in S that can be connected by edge disjoint paths. EDP is NP-hard and in directed graphs also hard to approximate as shown by the result of Guruswami et al. Their result seemed to have settled the approximability of EDP in directed graphs. However we show that the problem remains open by suggesting that number of vertices (n) is a better measure to express approximability than the number of edges (m). We obtain the first "sub-linear" (in n) approximation factors for EDP in both directed and undirected graphs. Our analysis is based on an interesting question on the maximum multicommodity flow in simple unit-capacity graphs that is a generalization of the single source case considered by Even and Tarjan. Other related results will be discussed.
This is joint work with Sanjeev Khanna (U. Penn).

Dr. Chandra Chekuri is a Member of Technical Staff in the Computer Science Research Center at Bell Labs, Lucent Technologies. His research interests are broadly in the area of design and analysis algorithms, combinatorial optimization, and theoritcal computer science. His recent work has focussed on approximation algorithms.
He got his Phd in Computer Science from Stanford University in 1998 and his B.Tech from the Indian Institue of Technology, Madras (now Chennai) in 1993. He joined Bell Labs in 1998 where in addition to his research in algorithm design he was part of a team that developed the OCELOT tool for optimizing wireless network performance.