Approximability of the edge-disjoint shortest paths problem

Question

In the edge-disjoint paths problem (EDP), we are given a (possibly directed) graph $G=(V,E)$, and a set of distinct source-sink pairs $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$, and we want to maximize the number of pairs that can be simultaneously connected in an edge-disjoint manner. When we add the constraint that the paths need to be shortest paths, we get the edge-disjoint shortest paths (EDSP) problem.

According to [1], the EDSP problem is hard for a graph with unit edge lengths, even when the graph is planar. Furthermore, it claims this is so for both directed and undirected graphs.

What is known about the approximability of the EDSP problem?

I'm especially interested in results for undirected graphs. In [2], the authors seem to only consider variants of the EDP problem, but not the EDSP problem. Further following the references, it seems like the EDP problem has been studied extensively.

---

[1] Eilam-Tzoreff, Tali. "The disjoint shortest paths problem." Discrete applied mathematics 85.2 (1998): 113-138.

[2] Guruswami, Venkatesan, et al. "Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems." Journal of Computer and System Sciences 67.3 (2003): 473-496.

Answer 1

Below, we will assume there is exactly one shortest path between every pair of vertices. The following will also work for the case where $O(\log n)$ pairs of vertices have $O(1)$ shortest paths between them.

For each pair $\{s_i , t_i\}$ let the shortest path be $P_i$, $\forall i \in \{0,1\ldots k\}$. The shortest path can be found in polynomial time. Let us number the edges $e_1, e_2, \ldots e_q$. Let the maximum number of pairs $\{s_i , t_i\}$ for which there exist disjoint-shortest paths be $\text{OPT}$.

Now, we reduce this problem to an optimization problem.

Define a matrix $A_{k\times q}$ such that $A_{ij} = 1 \text{ if } e_j \in P_i$.

$$ \text{OPT} = \max \sum_{i=1}^k x_i \quad \\ \text{s.t } Ax \leq \mathbf{1}_{n\times 1} \\ x \in \{0,1\} $$

Let the optimal fractional solution for the above problem be $\text{OPT}_{\text{LP}}$ and $\text{OPT}_{\text{LP}} \geq \text{OPT}$. The above LP has an integrality gap of $O(\log k)$. Therefore, $O(\log k) \cdot \text{OPT}_{\text{IP}} \geq \text{OPT}_{\text{LP}}$. Thus $ O(\log k) \cdot \text{OPT}_{\text{IP}} \geq \text{OPT}$. Hence we obtain a $O(\log k)$ approximation algorithm.

The proof for the integrality gap result can be found in Vazirani's "Approximation Algorithms", chapter 20. Multicut in General Graphs.