7
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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, 2013 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, 2013 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, 2013 at 19:55

3 Answers 3

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Shouldn't $k$ be upper bounded by some function of $n$ and not the other way around? $\endgroup$
    – Huck Bennett
    Nov 13, 2013 at 17:54
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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, 2013 at 15:40
0
$\begingroup$

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.

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.