Hardness of Low Congestion Routing in Directed Graphs
Venkatesan Guruswami, Kunal Talwar · Electronic colloquium on computational complexity · 2006
We prove a strong inapproximability result for routing on directed graphs with low congestion. Given as input a directed graph on N vertices and a set of source-destination pairs that can be connected via edge-disjoint paths, we prove that it is hard, assuming NP doesn’t have