Hardness of routing with congestion in directed graphs
Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar · 2007
Given as input a directed graph on n vertices and a set ofsource-destination pairs, we study the problem of routing themaximum possible number of source-destination pairs on paths, suchthat at most c(N) paths go through any edge. We show that theproblem is hard to approximate within an NΩ(1/c(N)) factoreven when we compare to the optimal solution that routes pairs onedge-disjoint paths, assuming NP doesn't have NO(log logN)-time randomized algorithms. Here the congestion c(N) can beany function in the range 1 ≤ c(N) ≤ α log N/log log N for some absolute constant α > 0. The hardness result is in the right ballpark since a factor NO(1/c(N)) approximation algorithm is known for this problem, viarounding a natural multicommodity-flow relaxation. We also give asimple integrality gap construction that shows that themulticommodity-flow relaxation has an integrality gap of NΩ(1/c) for c ranging from 1 to Θ((log n)/(log log n)).