Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:

  • We take a random walk starting at $v_0$.
  • Along the way, we can collect local information such as the degrees of vertices visited. We can also make local modifications to $G$, e.g. by deleting vertices and edges adjacent to where we've been.
  • At the end of the walk (triggered by some event such as having no remaining moves), we use the collected information to compute an unbiased estimator for the number of vertices in $G$.

Specifically, I'm interested in such methods that may be feasible in some cases (all would be too much to ask) where generating $G$ in its entirety is not feasible.

The inspiration for this question is a paper of Donald Knuth that does precisely the above for trees. Applying Knuth's method to a more general graph produces an estimate of the number of possible walks, not the number of vertices.

Ideas?

share|improve this question
    
Move from $v_0$ to $v_1$, remove $v_0$ and connect all the vertices which were connected to $v_0$ by edges; move from $v_1$ to $v_2$ and so on as far as you can walk. The number of steps gives you the number of vertices in a connected graph. –  Anton Petrunin Aug 16 '13 at 0:21
    
@Anton: I guess those are local modifications! But I'm looking for a method that will work when $G$ is too big to do, say, a number of operations as large as the number of vertices of $G$. –  Tino Aug 16 '13 at 0:33
    
I'd guess that what you're asking is too difficult, unless we have a DAG. One intuition is that, if we cannot remember which vertices we've visited, then it will be difficult to distinguish between a small cycle and a very long line. –  usul Aug 16 '13 at 1:39
    
@usul: Remember that we can modify the graph locally, for example by deleting vertices we've visited. –  Tino Aug 16 '13 at 5:37
    
@Tino, ok, but if you are visiting $o(n)$ vertices and making $o(n)$ modifications (where $n$ is the number of vertices), it still seems very unlikely to me. –  usul Aug 16 '13 at 16:26
show 1 more comment

2 Answers 2

Unless you use some exhaustive criterion for stopping, such as Anton Petrunin's suggestion of deleting vertices while maintaining connectivity and not stopping until all vertices are gone, I do not see what class of graphs you hope will yield to such a process. The example below highlights my pessimism.

Take a graph G you wish to reveal. I will pick a large positive integer k. Pick your v_0. I will construct k copies of G, and pick random pairs of vertices to use to add a single edge between two copies. I will attach my connected construct to your copy at a single vertex, perhaps even at v_0. I do not see how you will determine k, much less the size of either G or my construct, without visiting all the vertices.

I think you will need something like knowing G has a nontrivial automorphism group as well as what that group is, and use that with your locally connected information, to say much about G.

share|improve this answer
    
This kind of example is an Achilles' heel for Knuth's method, too. What happens (I think) is that the expected value of his estimator is still the number of vertices, but the second and third moments may be very large, making it infeasible to get a good estimate. That doesn't stop Knuth's method from being useful for trees which are sufficiently "balanced" (in a fuzzier way than having an actual automorphism). That's why I still hold out hope of an extension to graphs that are not trees. –  Tino Aug 16 '13 at 20:38
add comment

Giving appropriate meaning to "generating $G$", here is one thing that could give some information: start from $v_0$ and walk until the walk has come back $k$ times to $v_0$; or possibly, instead, walk for a deterministic time $N$ and count how many times the walk visits $v_0$ during this time. This gives you, as $k$ or $N$ goes to infinity, enough information on the distribution of the return times to in particular deduce the size of the graph.

Admittedly the time needed for the algorithm will be quite a bit larger than the number of vertices. But OTOH, maybe $G$ is given implicitly as the set of states of some process, with edges given by transitions of that process, in such a way that storing the current state is (very) cheap and running the walk is easy. So, it can work with $o(n)$ memory requirement if not $o(n)$ time...

Here is a nice paper going into exactly what kind of info can on $G$ be reconstructed that way: Waiting for a bat to fly by (in polynomial time).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.