Thursday, July 10th, 2008

A small graph-theory puzzle

Filed under: Science and Technology — Daniel Lemire @ 13:23

I like to think about graph theory problems these days. Here is one:

What type of graph has minimal diameter for a given number of vertices, given an upper bound on the in-degree and another upper bound on the out-degree?

I will give eternal fame (among the readership of this blog) to anyone who can provide a practical algorithm to construct such graphs. Pointing me to a reference counts.

(No, I have not even tried to solve the problem. I am just interested in the answer.)

6 Comments »

  1. So the graph is directed ? In that case, is the “distance” between a pair defined to be the shorter of uv and vu ? or is the diameter merely the max over u,v of d(uv) ?

    Comment by Suresh — 10/7/2008 @ 13:48

  2. In the undirected case, see Moore graphs for a lower bound on diameter that is achievable for some cases. The fact that we don’t know whether one of the possible cases of a Moore graph exists (the case with diameter 2, degree 57, and 3250 nodes) leads me to believe that there is no known efficient algorithm for constructing diameter-minimal graphs more generally.

    Comment by D. Eppstein — 10/7/2008 @ 13:59

  3. Suresh: I’d say “max over u,v of d(uv)”. But if it is easier to solve with an alternate definition of the diameter, I’d live with it.

    Comment by Daniel Lemire — 10/7/2008 @ 16:52

  4. Do I understand this correctly or am I being missing something ?

    Seems to me to be that for a diameter of i
    the max. number of nodes is
    (m+n)(m+n-1)^i

    So for a given number of vertices v
    the number of nodes remaining at any stage is

    v - (m+n)(m+n-1)^i

    for a diameter of i
    find the biggest i add 1 depending on the result pending.

    Comment by Anonymous — 12/7/2008 @ 18:28

  5. If you want the exactly minimum diameter, then that sounds like a hard combinatorial problem.

    But you can get within a constant factor (in degree and diameter) with expander graphs, specifically Ramanujan graphs. A lower bound on the diameter is log(n)/log(d), and Ramanujan graphs have diameter less than 2 log(n)/log(d/4) = O(log(n)/log(d)).

    The defining feature of Ramanujan graphs is that they have spectral expansion lambda

    Comment by Greg Price — 19/7/2008 @ 17:12

  6. [Your comment form eats < signs. Is it taking raw HTML? It'd be nice to know, to avoid formatting mishaps.]

    If you want the exactly minimum diameter, then that sounds like a hard combinatorial problem.

    But you can get within a constant factor (in degree and diameter) with expander graphs, specifically Ramanujan graphs. A lower bound on the diameter is log(n)/log(d), and Ramanujan graphs have diameter less than 2 log(n)/log(d/4) = O(log(n)/log(d)).

    The defining feature of Ramanujan graphs is that they have spectral expansion lambda < 2 srqt(d-1)/d. By considering a random walk starting from one vertex it’s not hard to show this implies a diameter at most log(n)/log(1/lambda) < 2 log(n)/log(d/4).

    The Wikipedia article has references.

    This is all in the undirected case, so it applies also when the in- and out-degrees are equal. Since the total in-degree equals the total out-degree, I expect it doesn’t help to allow higher in- than out-degrees or vice versa, but I don’t know.

    There’s a large body of work on expanders in general, and it’s possible someone has addressed diameter specifically and closed the constant-factor gap left by the spectral approach through Ramanujan graphs.

    Comment by Greg Price — 19/7/2008 @ 17:15

RSS feed for comments on this post.

Leave a comment

Warning: When entering a long comment, please ensure that you make copy of your text prior to submitting it. If the server should fail or if you hit a bug, you might lose your work. I am not responsible for your lost effort.

To spammers: I carefully review every single post and make sure that spam gets deleted. You are wasting your time if you are manually entering spam using this form. Read my terms of use to see what I consider to be abusive.

Example: I + II + IX= XII. Yes, you have to enter a roman numeral. (Answer must be in upper case.)

« Blog's main page

26 queries. 0.349 seconds. Valid XHTML

Powered by WordPress

Subscribe to this blog in a reader or by Email.