TR07-113 Authors: Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

Publication: 15th November 2007 14:33

Downloads: 819

Keywords:

In the undirected Edge-Disjoint Paths problem with Congestion

(EDPwC), we are given an undirected graph with $V$ nodes, a set of

terminal pairs and an integer $c$. The objective is to route as many

terminal pairs as possible, subject to the constraint that at most

$c$ demands can be routed through any edge in the graph. When $c=1$,

the problem is simply referred to as the Edge-Disjoint Paths (EDP)

problem. In this paper, we study the hardness of EDPwC in undirected

graphs.

Our main result is that for every $\ve>0$ there exists an

$\alpha>0$ such that for $1\le c\le \frac{\alpha\log\log

V}{\log\log\log V}$, it is hard to distinguish between instances

where we can route all terminal pairs on edge-disjoint paths, and

instances where we can route at most a $1/(\log

V)^{\frac{1-\ve}{c+2}}$ fraction of the terminal pairs, even if we

allow congestion $c$. This implies a $(\log

V)^{\frac{1-\ve}{c+2}}$ hardness of approximation for EDPwC and an

$\Omega(\log\log V/\log\log\log V)$ hardness of approximation for

the undirected congestion minimization problem. These results hold

assuming ${\rm NP} \not\subseteq \cup_d {\rm ZPTIME}(2^{\log^d n})$.

In the case that we do not require perfect completeness, i.e.\ we do

not require that all terminal pairs are routed for

``yes-instances'', we can obtain a slightly better inapproximability

ratio of $(\log V)^{\frac{1-\ve}{c+1}}$. Note that by setting $c=1$

this implies that the regular EDP problem is $(\log

V)^{\frac{1}{2}-\ve}$ hard to approximate.

Using standard reductions, our results extend to the node-disjoint

versions of these problems as well as to the directed setting. We

also show a $(\log V)^{\frac{1-\ve}{c+1}}$ inapproximability ratio

for the All-or-Nothing Flow with Congestion (ANFwC) problem, a

relaxation of EDPwC, in which the flow unit routed between the

source-sink pairs does not have to follow a single path, so the

resulting flow is not necessarily integral.