Universal Traversal on the Clique?

Consider a d-regular undirected graph. A walk from a vertex v is a sequence of edge labels in [d]=\{1,2,\ldots d\}, which corresponds to a path on the graph that starts at v and at step i follows the edge labeled by a_i out of the current vertex, where a_i is the i‘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 n) walk that covers every graph (on n 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 n^{O(\log n)} 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 n^{O(\log n)}-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 n^{O(\log n)}-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.”


6 Comments on Universal Traversal on the Clique?

  1. Noy Rotbart // July 11, 2017 at 2:55 pm // Reply

    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.


  2. 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.


    • 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).


  3. Great problem! Indeed embarrassing we don’t know the answer yet.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: