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

Bounds For Random Edge in 3-Polytopes

presented by Micha Sharir

Let P be a simple 3-Polytope n facets. Order the vertices according to their height³. There is one vertex with updegree 3 at the beginning of our list and one with updegree 0 at the end of the list. All vertices in-between have either updegree 1 (1-vertices) or updegree 2 (2-vertices). For a vertex v, denote by h₁(v) the number of 1-vertices and by h₂(v) the number of 2-vertices above v (including v itself). Let E(v) be the expected number of steps for RANDOM EDGE to reach the sink starting from vand F(a,b) be the maximal expected number of steps for RANDOM EDGE starting from a vertex v with h₁(v)=a and h₂(v)=b. We will sketch a proof for

$$F(a,b)\leq a+\frac 59 b.$$

This gives an upper bound of $\frac{13}9n$.

Let u be a vertex with h₁(u)=a and h₂(u)=b. If u is a 1-vertex the expected cost E(u) is the expected cost of its only successor v plus 1 (see fig. 4). Since $h_1(v)\leq h_1(u)-1$ we get

$$E(u)=1+E(v)\leq 1+F(a-1,b)=1+a-1+\frac59 b=a+\frac59 b.$$

  

Figure 4: u is a 1-vertex

For u being a 2-vertex there are several cases. Let v₁,v₂ be the two higher neighbors of u, v₁ lower than v₂. Then $E(u)=1+\frac12(E(v_1)+E(v_2))$ and $h_2(v_1),h_2(v_2)\leq h_2(u)=b$.

If between u and v₂ is a second vertex, h₁(v₂)+h₂(v₂) looses two additional vertices (see fig. 5). Therefore $E(v_2)\leq F(h_1(v_2),h_2(v_2))\leq h_1(v_2)+\frac59 h_2(v_2)\leq a+\frac59b - 3\cdot\frac59$ and

$$E(u)\leq 1+\frac12(a+\frac59b-\frac59+a+\frac59b-\frac{15}9)=a+\frac59b - \frac19\leq a+\frac59b$$

  

Figure 5: Both neighbors are far away

For the rest of the proof we have to deal with the cases that v₁ is directly above u and v₂ directly above v₁. If v₁ is a 1-vertex (see fig. 6) we get $E(v_1)\leq F(a,b-1)\leq a+\frac59 b - \frac59$ and $E(v_2)\leq F(a-1,b-1)\leq a-1+\frac59 b-\frac59$. This gives

$$E(u)\leq 1+\frac12(a+\frac59 b - \frac59+a-1+\frac59 b-\frac59)= a+\frac59 b -\frac1{18}.$$

  

Figure 6: v₁ is a 1-vertex

Let now v₁ be a 2-vertex. If we have no edge between v₁ and v₂ (see fig. 7) we get $E(v_1)\leq 1+\frac12(a+\frac59 b - 3\cdot\frac59 + a +\frac59 b -4\cdot\frac59)=a+\frac59 b-3$ and therefore

$$E(u)\leq 1+\frac12(a+\frac59 b-3+a\frac59b -\frac{10}9)=a+\frac59 b -\frac{23}9.$$

  

Figure 7: There is no edge between v₁ and v₂.

If there is an edge from v₁ to v₂ denote by w₁ the second successor of v₁ and by w₂ the successor of v₂. If w₁=w₂, the edge graph of P would be only 2-connected, a contradiction (see fig. 8).

  

Figure 8: Cannot be realized

Therefore we have $w_1\neq w_2$ (see fig. 9). With probability $\frac14$ we will go $u\to v_1\to w_1$, with probability $\frac14$ we have $u\to v_1\to v_2\to w_2$ and in all other cases we get $u\to v_2\to w_2$. Therefore

$$E(u)=\frac14(2+E(w_1))+\frac14(3+E(w_2))+\frac12(2+E(w_2)).$$

For both w₁ and w₂ we loose at least two 2-vertices and one 1-vertex, so $E(w_1),E(w_2)\leq F(a-1,b-2)\leq a-1+\frac59 b-\frac{10}9$. If w₁ is before w₂ we loose additional $\frac59$ for E(w₂) and if w₂ is before w₁ we loose $\frac59$ for E(w₁). In the first case we get

$$E(u)\leq\frac14(1+a+\frac59 b-\frac{10}9)+\frac14(2+a+\frac59... ...5}9)+\frac12(1+a+\frac59b-\frac{15}9)=a+\frac59b -\frac{95}{36}$$

and in the second case

$$E(u)\leq\frac14(1+a+\frac59 b-\frac{15}9)+\frac14(2+a+\frac59 b-\frac{10}9)+\frac12(1+a+\frac59b-\frac{10}9)=a+\frac59b.$$

  

Figure 9: The bottleneck

Imprint Disclaimer Copyright