6.8 Algorithmic aspects

This was one motivation for the seminal paper [25]. Consider an $n$-vertex $d$-regular graph $G$, with a distinguished vertex $v_{0}$, and where for each vertex $v$ the edges at $v$ are labeled as $1,2,\ldots,d$ in some way – it is not required that the labels be the same at both ends of an edge. Now consider a sequence ${\bf i}=(i_{1},i_{2},\ldots,i_{L})\in\{1,\ldots,d\}^{L}$. The sequence defines a deterministic walk $(x_{i})$ on the vertices of $G$ via

$x_{0}=v_{0}$

$(x_{j-1},x_{j})$ is the edge at $x_{j-1}$ labeled $i_{j}$.

Say i is a traversal sequence for $G$ if the walk $(x_{i}:0\leq i\leq L)$ visits every vertex of $G$. Say i is a universal traversal sequence if it is a traversal sequence for every graph $G$ in the set $\mbox{${\cal G}$}_{n,d}$ of edge-labeled graphs with distinguished vertices.

Proof. It is enough to show that a uniform random sequence of that length has non-zero chance to be a universal traversal sequence. But for such a random sequence, the induced walk on a fixed $G$ is just simple random walk on the vertices of $G$. Writing $t_{0}=\lceil 6en^{2}\rceil$, Theorem 6.4 implies

and so inductively (cf. Chapter 2 section yyy)

Thus by taking $K$ sufficiently large that

there is non-zero chance that the induced walk on every $G$ covers before time $Kt_{0}$. The crude bound $|\mbox{${\cal G}$}_{n,d}|\leq(nd)^{nd}$ means we may take $K=\lceil nd\log(nd)\rceil$.

Another motivation for the seminal paper [25] was the time-space tradeoff in algorithms for determining connectivity in graphs. Here is a highly informal presentation, illustrated by the two Mathematician graphs. The vertices are all mathematicians (living or dead). In the first graph, there is an edge between two mathematicians if they have written a joint paper; in the second, there is an edge if they have written two or more joint papers. A well known Folk Theorem asserts that the first graph has a giant component containing most famous mathematicians; a lesser known and more cynical Folk Theorem asserts that the second graph doesn’t. Suppose we actually want to answer a question of that type – specifically, take two mathematicians (say, the reader and Paul Erdos) and ask if they are in the same component of the first graph. Suppose we have a database which, given a mathematician’s name, will tell us information about their papers and in particular will list all their co-authors.

xxx continue story

Broder et al [64]

Consider the question of getting a numerical value for $E_{i}C$ (up to error factor $1\pm\varepsilon$, for fixed $\varepsilon$) for random walk on a $n$-vertex graph. Using Theorem 6.1 it’s clear we can do this by Monte Carlo simulation in $O(n^{3})$ steps.

xxx technically, using s.d./mean bounded by submultiplicitivity.

It’s clear one can compute mean hitting times on a $n$-step chain in polynomial time, but to set up the computation of $E_{i}C$ as a hitting-time problem one has to incorporate the subset of already-visited states into the “current state”, and thus work with hitting times for a $n\times 2^{n-1}$-state chain.