**Sanjeev Khanna, Disjoint Paths in Networks
**

edge-disjoint paths problem (EDP). We are given a network

and a collection of source-destination pairs in the network.

The goal is to maximize the number of pairs that can be

connected by edge-disjoint paths. Even special cases of EDP

correspond to non-trivial optimization problems, and the

problem becomes NP-hard in very restricted settings. For

instance, EDP on star graphs is equivalent to the general

matching problem, and EDP on trees is NP-hard.

In this talk, we will survey some recent progress on understanding

the approximability threshold of EDP and its variants. While the

recent developments have essentially resolved the approximability

of EDP and related problems in directed graphs, the status of the

undirected case remains wide open. We will describe a promising

framework for getting much improved algorithms for undirected

EDP when some congestion is allowed. In particular, we will

highlight a conjecture whose resolution is strongly tied to the

approximability of the undirected case, and describe some results

that lend support to this conjecture.