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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

• People
  • Personnel
  • Guests
  • Alumni
• Reports
  • Current Report
  • Report for 2023
  • Report for 2022
  • Previous Reports
• Research
  • Grants
  • Dissertations
  • Master/Bachelor Theses
  • Current Publications
  • Previous Publications
• Mittagsseminar
• Courses
• Thesis Topics
• Events
  • Workshops
    • Current
    • Previous
  • Social
    • SOLA
    • GREBGE
• 

Towards The Peak - Problem Section

i-Niceness

presented by Emo Welzl

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

$$r(v)=s(v)\cup\bigcup\{r(w)\vert\mbox{$w$ successor of $v$}\}.$$

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 $r(w)\subsetneq r(v)$. 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ⁱ 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.

Imprint Disclaimer Copyright