Universal Traversal on the Clique?
Consider a -regular undirected graph. A walk from a vertex
is a sequence of edge labels in
, which corresponds to a path on the graph that starts at
and at step
follows the edge labeled by
out of the current vertex, where
is the
‘s element of the sequence. Random walks (where the edge labels are random) have lots of very useful properties. In particular, with very high probability, a polynomially-long (in the size of the graph) random walk visits each one of the vertices of the graph (i.e. “covers” the graph). There are many ways in which one may try to derandomize a random walk, one of which was introduced by Stephen Cook in the late 70’s and is known as a Universal Traversal Sequence (UTS). This is quite an incredible notion when you think of it: one fixed polynomially long (in
) walk that covers every graph (on
vertices). The probabilistic-method shows that a polynommially-long UTS exists. Unfortunately, while almost every walk of the appropriate size is a UTS, we do not know of any explicit one (i.e., any algorithm that produces a polynomially-long UTS). The shortest UTS we know is based on Nisan’s pseudorandom generators that fool small space computations and is
long.
As a first post in what may (or may not) turn out to be a new sequence titled “questions we should have solved by now,” lets see how far we can simplify the problem of explicit UTS and still not solve it. Specifically, what if our graph has a small diameter. For example, expander graphs have logarithmic diameter, which should make the problem much easier shouldn’t it? Well, the shortest UTS for expanders is still the -long one based on Nisan’s generators. Well, if logarithmic diameter doesn’t save us, perhaps constant diameter? How about diameter one? Yes, can we have a UTS for a clique? You may be thinking – the clique on $n$ vertices is a single graph, how hard can it be to come up with a UTS for a single graph? Turns out that it is not that easy. The shortest explicit UTS we know for the clique is … wait for it, wait for it … still the
-long one based on Nisan’s generators! How come? There is indeed only one clique, but the there can be many possible ways to label the edges of the clique and the UTS should cover the clique for all such labellings.
Of course, we all know how difficult simple-looking problems can really be, but please share with us your favorite problems that “should have been solved by now.”
A simple problem that really bugs me for years.
Label the vertices of an n vertex unit disk graph so that adjacency can be determined by the labels alone, where the metric is to minimise the largest label size of the family (adjacency labeling scheme for unit disk graphs in the literature).
I have nothing better than the one for general graphs (label size n/2+4 explicit, n/2-1 possible).
In the other direction- show a lower bound, again, I have nothing better than log n +O(1).
The same situation occurs in segment intersection graphs.
LikeLike
Worth pointing out: If the graph is consistently labelled — that is, if the index of each edge is the same going in both directions — then we do know explicit (log-space constructible) universal traversal sequences.
The fact that the labelling of the edges is so important to this problem has always confused me, especially as I intuitively do not think of the neighbors of a vertex being as an ordered set.
LikeLike
Thanks Thomas. At this point there is an explicit UTS for general graphs with consistent labelling. Also, there is a related notion of universal exploration sequence that also exist for general graphs (and is trivial for the clique).
LikeLike
Great problem! Indeed embarrassing we don’t know the answer yet.
LikeLike
Btw, do you have any applications in mind for the clique version?
LikeLike
Sorry for missing your question! More than an application its the hope it will require some useful new techniques that will be useful more generally.
LikeLike