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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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