Computer Science/Discrete Mathematics Seminar I

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.