Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs (Q653831): Difference between revisions

In the edge-disjoint paths (EDPs) problem, a graph \(G\) and a set of pairs of vertices, called terminals, are given. The objective is to connect as many pairs as possible via edge-disjoint paths. Even highly restricted cases of EDPs correspond to well-studied important optimization problems. In this paper, undirected EDPs are studied, together with a natural generalization known as edge-disjoint paths with congestion (EDPwC), in which the goal is to route as many terminal pairs as possible subject to the constraint that at most \(c\) paths are routed through any edge. For \(c = 1\), the problem is simply the EDPs problem. In this paper, the hardness of EDPwC in undirected graphs is studied. The main result is that, for every \(\epsilon > 0\), there exists an \(\alpha > 0\) such that, for \(1\leq c \leq \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 fraction \(1/(\log V )^{(1-\varepsilon)/(c+2)}\) of the terminal pairs, even if we allow for a congestion \(c\). This implies a hardness of approximation of \( (\log V )^{(1-\varepsilon)/(c+2)}\) for EDPwC and a hardness of approximation of \(\Omega (\log \log V/\log \log \log V )\) for the undirected congestion minimization problem. Another related problem is the all-or-nothing (ANF) flow problem where each routed demand is allowed to be routed on fractional paths. ANF is a relaxation of EDPs. The last problem discussed in this paper is the congestion minimization problem in which the goal is to find the minimum value of the congestion \(c\) such that all terminal pairs can be routed. An \(\Omega ((\log V)^{1/2-\varepsilon} )\) inapproximability result for EDPs, ANF, and node-disjoint paths on undirected graphs is shown for any constant \(\varepsilon>0\). If a congestion \(c\), \(1\leq c \leq O( \log \log V/\log \log \log V)\), is allowed in the routing, a hardness factor of \( (\log V)^{(1-\varepsilon)/(c+1)} \) is obtained (and a slightly weaker \((\log V)^{(1-\varepsilon)/(c+2)} \) factor with perfect completeness, i.e., when it is ensured that the instance has an edge-disjoint routing for all the source-destination pairs). Using standard reductions, these results are extended to the node disjoint versions of these problems as well as to the directed setting. A \( (\log V )^{(1-\varepsilon)/(c+1)}\) inapproximability ratio is proved for the all-or-nothing flow with congestion, a relaxation of EDPwC, in which the flow unit routed between the source-sink pairs does not have to follow a single path, and the resulting flow is not necessarily integral.