Speaker: Shuheng Zhou
Date: Friday, May 12
Time: 2:00-3:15pm
Place: WeH 7220
Title: Edge Disjoint Paths in Moderately Connected Graphs
Abstract:
We study the Edge Disjoint Paths (EDP) problem in undirected graphs:
Given a graph $G$ with $n$ nodes and a set $\T$ of
pairs of terminals, connect as many terminal pairs as possible
using paths that are mutually edge disjoint. This leads to a variety
of classic NP-complete problems, for which approximability is not
well understood.
We show a polylogarithmic approximation algorithm for the undirected
EDP problem in general graphs with a moderate restriction on graph
connectivity; we require the global minimum cut of $G$ to be
$\Omega(\log^5 n)$. Previously, constant or polylogarithmic
approximation algorithms were known for trees with parallel edges,
expanders, grids and grid-like graphs, and most recently, even-degree
planar graphs. These graphs either have special structure (e.g.,
they exclude minors) or there are large numbers of short disjoint
paths. Our algorithm extends previous techniques in that it applies
to graphs with high diameters and and asymptotically large minors.
This is joint work with Satish Rao.