An O(sqrt{n}) approximation and integrality gap for EDP and UFP in undirected graphs and DAGs

An O(sqrt{n}) approximation and integrality gap for EDP and UFP in undirected graphs and DAGs. We consider the maximization version of the edge disjoint path problem (EDP). In undirected graphs and directed acyclic graphs, we obtain an O(sqrt{n})upper bound on the approximation ratio where an is the number of nodes in the graph. We show this by establishing the upper bound on the integrality gap of the natural multicommodity flow based relaxation. Our upper bound matches to within a constant factor the known lower bound of Omega (sqrt{n}). The best previous upper bounds known were O(min{n^{2/3}, sqrt{m}}) for undirected graphs and O(min{sqrt{n log n}, sqrt{m}}) for directed acyclic graphs. Here m is the number of edges in the graph. Our bound extends to the unsplittable flow problem (UFP) when the maximum demand is at most the minimum capacity.