6 Cover Times (October 31, 1994)

6.8 Algorithmic aspects

Many of the mathematical results in this chapter arose originally from algorithmic questions, so let me briefly describe the questions and their relation to the mathematical results.

6.8.1 Universal traversal sequences

This was one motivation for the seminal paper [25]. Consider an nn-vertex dd-regular graph GG, with a distinguished vertex v0v_{0}, and where for each vertex vv the edges at vv are labeled as 1,2,,d1,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 𝐢=(i1,i2,,iL){1,,d}L{\bf i}=(i_{1},i_{2},\ldots,i_{L})\in\{1,\ldots,d\}^{L}. The sequence defines a deterministic walk (xi)(x_{i}) on the vertices of GG via


(xj-1,xj)(x_{j-1},x_{j}) is the edge at xj-1x_{j-1} labeled iji_{j}.

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

Proposition 6.34 (Aleliunas et al [25])

There exists a universal traversal sequence of length (6e+o(1))dn3log(nd)(6e+o(1))dn^{3}\log(nd) as nn\rightarrow\infty with dd varying arbitrarily.

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 GG is just simple random walk on the vertices of GG. Writing t0=6en2t_{0}=\lceil 6en^{2}\rceil, Theorem 6.4 implies

Pv(C>t0)EvCt06n2t0e-1 for all initial vP_{v}(C>t_{0})\leq\frac{E_{v}C}{t_{0}}\leq\frac{6n^{2}}{t_{0}}\leq e^{-1}\mbox% { for all initial }v

and so inductively (cf. Chapter 2 section yyy)

Pv0(C>Kt0)e-K,K1 integer .P_{v_{0}}(C>Kt_{0})\leq e^{-K},\ \ \ K\geq 1\mbox{ integer }.

Thus by taking KK sufficiently large that

e-K|𝒢n,d|<1e^{-K}|\mbox{${\cal G}$}_{n,d}|<1

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

6.8.2 Graph connectivity algorithms

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]

6.8.3 A computational question

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

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

Open Problem 6.35

Can EiCE_{i}C be deterministically calculated in a polynomial (in nn) number of steps?

It’s clear one can compute mean hitting times on a nn-step chain in polynomial time, but to set up the computation of EiCE_{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×2n-1n\times 2^{n-1}-state chain.