2
$\begingroup$

Hi. I have a problem but not sure if there is some literature on it or whether it has a standard name. Please let me know some reference from where I can begin.

Given undirected graph along with some pairs of nodes $s_i$ and $t_i$, we want to connect as many pairs in the graph as possible such that paths are edge disjoint.

Please comment on approximation and hardness results if any.

$\endgroup$
8
$\begingroup$

Maximize Edge Disjoint Paths (EDP)

The problem is NP Hard and here are some results:

1) It accepts $O(\sqrt{m})$ approximation by Kleinberg in 96 in general graphs.

2) The above is tight for directed graphs (Guruswami et. al.).

3) Inapproximation result by Andrews, Zhang : O($log ^{\frac{1}{2}-\epsilon}n$).

4) For planar graphs, Chekuri et. al. has found a O(1) approx with any edge being in O(1) paths.

I will update with references later but you can google out.

EDIT: There is a recent paper by Chekuri in 06 which has improvised it to $O(\sqrt(n))$ in undirected graphs. You will get the above references in that paper. The paper is at

theoryofcomputing.org/articles/v002a007/v002a007.ps.gz

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.