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 route as many pairs as possible such that the
paths assigned to the routed pairs do not share any network links.
EDP and its variants have numerous applications including network
routing, bandwidth allocation, and VLSI design. Not surprisingly,
it is one of the most extensively studied optimization problems and
is connected to major developments in algorithms and graph theory.
We will describe a new framework for undirected graphs that provides
substantially improved algorithms for several routing problems. 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. We will also describe some recent progress
on hardness of EDP which gives polylogarithmic hardness results even
when congestion is allowed.
This is based on joint works with Chandra Chekuri, Julia Chuzhoy, and
Bruce Shepherd.