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.