# Vertex-disjoint paths in sparse graphs

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é.

• 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$. Nov 13, 2013 at 15:42
• 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. Nov 14, 2013 at 10:33
• 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. Nov 15, 2013 at 19:55

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

• Shouldn't $k$ be upper bounded by some function of $n$ and not the other way around? Nov 13, 2013 at 17:54

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

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)$.

• 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. Nov 13, 2013 at 15:40

In case you are looking for bi-partite graphs, Tanner graphs for LDPC codes 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.