Sanjeev Khanna, Disjoint Paths in Networks

Abstract:
A fundamental problem in combinatorial optimization is the
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.