Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

**presented by Emo Welzl**

Given a unique sink orientation
and a vertex *v*, the *reachmap
**r*(*v*)* of **v* is the set of all edge-labels such that for every there is a directed path starting in *v* and containing an edge of label
*i*. More formally,

Call a unique sink orientation *i**-nice*, if for every vertex *v* there
is a vertex *w* with distance at most *i* from *v* and
.
Since there is always a path from a vertex *v* to the sink of the
cube, the sink is in the subcube generated by *v* and the directions in
*r*(*v*). Therefore RANDOM EDGE on an *i*-nice unique sink orientation
will take an expected number of at most *d*^{i} steps.

Clearly every unique sink orientation of dimension *d* is *d*-nice. Can we
do better? In particular what is the general niceness of acyclic unique sink
orientations?

In dimension three every acyclic unique sink orientation is 1-nice except the orientation one gets by reorienting the cyclic unique sink orientation, which is 2-nice.

Ingo Schurr and Uli Wagner ({schurr,uli}@inf.ethz.ch)