<p>A hypercube has $O(n\log n)$ edges and satisfies your property for $k\leq\frac{\log_2 n+1}{2}$:</p>

<ul>
<li>S. Madhavapeddy, and I. H. Sudborough, "<a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=143599" rel="nofollow">A topological property of hypercubes: node disjoint paths</a>", Proc. IEEE SPDP, 532-539, 1990. </li>
</ul>

CC BY-SA 3.0
2013-11-13T17:54:43.243Z
Shouldn't $k$ be upper bounded by some function of $n$ and not the other way around?
Huck Bennett
CC BY-SA 3.0
2013-11-13T12:53:17.807Z
2013-11-14T23:54:53.757Z
2013-11-14T23:54:53.757Z
Colin McQuillan
<p>I think that what you are looking for may be here:</p>

<ul>
<li>Jon Kleinberg, "<a href="http://www.cs.cornell.edu/home/kleinber/focs96-exp.ps" rel="nofollow">Short Paths in Expander Graphs</a>", FOCS 1996.</li>
</ul>

<p>In particular they show that for any bounded-degree expander graph $G$ (hence answering your O(n) requirement on the edges) any graph $H$ on $O(n/log(n))$ vertices and edges appears in $G$ as a graph minor, i.e. the edges of $H$ translate into disjoint paths in $G$.
Hence your $k$ parameter can go as high as $n/log(n)$.</p>

CC BY-SA 3.0
2013-11-13T15:40:11.650Z
Yes, in general constant degree expanders are the "best" routers.  See also papers of Alan Frieze. Most of the work has been on edge-disjoint paths. Vertex disjoint paths are little trickier in the precise form you ask.
Chandra Chekuri
CC BY-SA 3.0
2013-11-13T11:43:41.817Z
2013-11-14T23:54:09.127Z
2013-11-14T23:54:09.127Z
Lior Eldar
<p><strong>Answer from Coding theory</strong></p>

<p>In case you are looking for bi-partite graphs, <a href="http://en.wikipedia.org/wiki/Tanner_graph" rel="nofollow">Tanner graphs</a> for <a href="http://en.wikipedia.org/wiki/Low-density_parity-check_code" rel="nofollow">LDPC codes</a> gives you $O(n)$ vertices with $O(n)$ edges. Lot of research has been done in this area of coding theory, therefore, you will be able to find various modifications of tanner graphs which might suit your need.</p>

CC BY-SA 3.0
2013-11-19T09:07:55.997Z
2013-11-19T09:07:55.997Z
Vivek Bagaria
<p>I'm looking for a graph $G$ on $n$ vertices with the following properties</p>

<ul>
<li>G doesn't have too many edges, $O(nlog(n))$ or $O(n)$ would be perfect</li>
<li>For <em>random</em> k disjoint pairs of vertices $(s_i,t_i)$ there is a path that links $s_i$ to $t_i$ for each $i$ such that all of these paths are vertex-disjoint. <em>This statement should be true with high probability p</em>.</li>
</ul>

<p>The goal is to find $G$ such that $k$ is maximal. I'm not very precise on $k$ and the number of edges <em>as well as on p (but let's say large constant p is fine or even better something that goes to 0 with n)</em> because I don't know what is possible.</p>

<p>EDIT: I rephrased the question in terms of average case instead of worst case since worst case won't give many vertex-independent paths as pointed out by Chandra Chekuri.</p>

<p>Thanks,
André.</p>

CC BY-SA 3.0
2013-11-13T15:42:40.037Z
A technical issue with vertex disjoint paths in the form you ask is the following. Suppose we have a node $v$ and its neighbors $N(v)$. If $v$ and $N(v)$ participate in the $k$ pairs then $v$ cannot have paths out of it without going through its  neighbors which severely limits $k$.
Chandra Chekuri
CC BY-SA 3.0
2013-11-14T10:33:37.180Z
Hmm, that's right. I should ask the question for random k pairs such that this happens with small probability. I'll rephrase my question, thanks.
Andre Chailloux
CC BY-SA 3.0
2013-11-15T19:55:15.933Z
What can be said for constant degree expanders is that given any $n$ pairs that do not share end points, some $\Omega(n/\log^2 n)$ of the given pairs can be routed via node-disjoint paths. Whether this is good or not depends on your application. Stronger statements can be said for edge-disjoint paths as shown in papers of Frieze and others.
Chandra Chekuri
<graph-theory>
Vertex-disjoint paths in sparse graphs
Andre Chailloux
# Vertex-disjoint paths in sparse graphs

(Asked by: username_0 on 2013-11-13)

I'm looking for a graph $G$ on $n$ vertices with the following properties

* G doesn't have too many edges, $O(nlog(n))$ or $O(n)$ would be perfect
* For *random* k disjoint pairs of vertices $(s\_i,t\_i)$ there is a path that links $s\_i$ to $t\_i$ for each $i$ such that all of these paths are vertex-disjoint. *This statement should be true with high probability p*.

The goal is to find $G$ such that $k$ is maximal. I'm not very precise on $k$ and the number of edges *as well as on p (but let's say large constant p is fine or even better something that goes to 0 with n)* because I don't know what is possible.

EDIT: I rephrased the question in terms of average case instead of worst case since worst case won't give many vertex-independent paths as pointed out by Chandra Chekuri.

Thanks,
André.

**Tags:** graph-theory
> **Comments:**
> **username_1**: A technical issue with vertex disjoint paths in the form you ask is the following. Suppose we have a node $v$ and its neighbors $N(v)$. If $v$ and $N(v)$ participate in the $k$ pairs then $v$ cannot have paths out of it without going through its  neighbors which severely limits $k$.  
> **username_0**: Hmm, that's right. I should ask the question for random k pairs such that this happens with small probability. I'll rephrase my question, thanks.  
> **username_1**: What can be said for constant degree expanders is that given any $n$ pairs that do not share end points, some $\Omega(n/\log^2 n)$ of the given pairs can be routed via node-disjoint paths. Whether this is good or not depends on your application. Stronger statements can be said for edge-disjoint paths as shown in papers of Frieze and others.  

---

## 3 answers

### Answer by username_2 on 2013-11-13. Score: 4

A hypercube has $O(n\log n)$ edges and satisfies your property for $k\leq\frac{\log\_2 n+1}{2}$:

* S. Madhavapeddy, and I. H. Sudborough, "[A topological property of hypercubes: node disjoint paths](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=143599)", Proc. IEEE SPDP, 532-539, 1990.

> **Comments:**
> **username_3**: Shouldn't $k$ be upper bounded by some function of $n$ and not the other way around?  

---

### Answer by username_4 on 2013-11-13. Score: 3

I think that what you are looking for may be here:

* Jon Kleinberg, "[Short Paths in Expander Graphs](http://www.cs.cornell.edu/home/kleinber/focs96-exp.ps)", FOCS 1996.

In particular they show that for any bounded-degree expander graph $G$ (hence answering your O(n) requirement on the edges) any graph $H$ on $O(n/log(n))$ vertices and edges appears in $G$ as a graph minor, i.e. the edges of $H$ translate into disjoint paths in $G$.
Hence your $k$ parameter can go as high as $n/log(n)$.

> **Comments:**
> **username_1**: Yes, in general constant degree expanders are the "best" routers.  See also papers of Alan Frieze. Most of the work has been on edge-disjoint paths. Vertex disjoint paths are little trickier in the precise form you ask.  

---

### Answer by username_5 on 2013-11-19. Score: 0

**Answer from Coding theory**

In case you are looking for bi-partite graphs, [Tanner graphs](http://en.wikipedia.org/wiki/Tanner_graph) for [LDPC codes](http://en.wikipedia.org/wiki/Low-density_parity-check_code) gives you $O(n)$ vertices with $O(n)$ edges. Lot of research has been done in this area of coding theory, therefore, you will be able to find various modifications of tanner graphs which might suit your need.


---

