### DIMACS Theoretical Computer Science Seminar

Title: Hardness of Undirected Edge Disjoint Path and Congestion Minimization

Speaker: **Lisa Zhang**, Bell Labs.

Date: November 15, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We study the edge disjoint problem on an undirected graph (EDP).
Given a set of demands with specified source-destination pairs on a
graph, we aim to maximize the number of demands that can be routed on
edge disjoint paths. The best known approximation ratio is O(M^{1/2})
where M is the number of edges in the graph. For directed graphs, an
almost matching lower bound of M^{1/2-epsilon} is known. In this talk
we concentrate on undirected graphs. We show a hardness of
(log M)^{1/3-epsilon} unless NP is in ZPTIME(n^polylog n). This lower
bound relies on a reduction from the hardness of max independent set.
The same hardness also applies to node-disjoint paths.

Time permitting we will also discuss congestion minimization on
undirected graphs. In this problem we aim to route all demands while
minimizing the maximum number of demands per link.

Joint work with Matthew Andrews.