<p>Maximize Edge Disjoint Paths (EDP)</p>

<p>The problem is NP Hard and here are some results:</p>

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

<p>2) The above is tight for directed graphs (Guruswami et. al.).</p>

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

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

<p>I will update with references later but you can google out.</p>

<p>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 </p>

<p>theoryofcomputing.org/articles/v002a007/v002a007.ps.gz</p>

CC BY-SA 3.0
2011-06-11T18:12:50.487Z
2011-06-12T19:23:44.897Z
2011-06-12T19:23:44.897Z
singhsumit
<p>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.</p>

<p>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. </p>

<p>Please comment on approximation and hardness results if any.</p>

CC BY-SA 3.0
2011-06-11T21:18:33.390Z
I guess you are referring to the [Maximum Disjoint Connecting Paths](http://www.nada.kth.se/~viggo/wwwcompendium/node122.html) problem; see the link for references.
Jukka Suomela
<ds.algorithms><graph-algorithms><approximation-algorithms><approximation-hardness>
Connectivity Problem
user5153
# Connectivity Problem

(Asked by: username_0 on 2011-06-11)

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.

**Tags:** ds.algorithms, graph-algorithms, approximation-algorithms, approximation-hardness

> **Comments:**
> **username_1**: I guess you are referring to the [Maximum Disjoint Connecting Paths](http://www.nada.kth.se/~viggo/wwwcompendium/node122.html) problem; see the link for references.  

---

## 1 answers

### Answer by username_2 on 2011-06-11. Score: 8 | Accepted answer

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


---

