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

  • 5
    $\begingroup$ 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$. $\endgroup$ – Chandra Chekuri Nov 13 '13 at 15:42
  • $\begingroup$ 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. $\endgroup$ – Andre Chailloux Nov 14 '13 at 10:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Nov 15 '13 at 19:55

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

  • 2
    $\begingroup$ Shouldn't $k$ be upper bounded by some function of $n$ and not the other way around? $\endgroup$ – Huck Bennett Nov 13 '13 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)$.

  • 2
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Nov 13 '13 at 15:40

Answer from Coding theory

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.


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.