2
$\begingroup$

In the edge-disjoint paths (EDP) problem, we are given an undirected graph $G$, and a set $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$ of $k$ source-sink pairs. The objective is to maximize the number of pairs connected via edge-disjoint paths. In the bounded length edge disjoint paths (BLEDP) problem, we wish to route the maximum number of source-sink pairs such that each of the paths used is of length at most $L$, for some length bounded $L$ that is part of the input.

Guruswami et al. [1] showed that BLEDP can be approximated in polynomial time within a factor of $O(\sqrt{m})$. They also showed this is optimal with a matching hardness result of $m^{1/2-\epsilon}$, for any $\epsilon > 0$.

Do we have algorithms achieving better approximation ratios for BLEDP for some restricted graphs? For example, how about (undirected) planar graphs?


[1] Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., & Yannakakis, M. (2003). Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Journal of Computer and System Sciences, 67(3), 473-496.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.