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

Lower Bound For Finding The Sink

presented by Tibor Szabó

What is the minimal number of vertex evaluations a deterministic algorithm will need to find the sink of a unique sink orientation?

Let t(d) be the largest number such that for every unique sink orientation of dimension d and every deterministic algorithm the algorithm has to query at least t(d) vertices¹. It is know that t(1)=2, t(2)=3, t(3)=5 and t(4)=7.

To get an idea how a proof for a general bound could look like, we will study the case d=4. Given a deterministic algorithm (in the following called Al), we will construct a 4-dimensional cube on which Al will need 7 steps.

The first answer will always be the same. Al asks a vertex v₁ and we will tell it that this vertex is the source. If in the next step Al does not query the antipodal vertex of v₁, we are basically done: v₁ and the now queried vertex v₂ lie in a common 3-dimensional facet. We will now choose a unique sink orientation for this facet (with v₁ as source) and direct the edges between this and the opposite facet outwards. (See figure 1.) The global sink will now be in the opposite facet and to find that sink, Al needs at least 5 steps. So it needs 7 steps altogether.

  

Figure 1: Al does not choose an antipodal vertex

In the case Al's second query v₂ is antipodal to v₁ we have to be a bit more careful. The important observation is, that in dimension three Al needs five steps, even if we tell it that the vertex antipodal to his first query is not the sink.

We choose a direction i and split the cube in two subcubes. We will refer to the facet containing v₁ as upper and to the opposite one as lower subcube. We will now play the tree dimensional game in the lower subcube and direct the edges in direction i towards this facet.

It may be that Al queries a vertex in the upper cube before he found the sink in the lower cube. We will then give it an answer such that the edge in direction i is directed downwards. It will still need five steps to find the sink in the lower cube, which is now the global sink. Therefore Al needs 1+1+5=7 steps.

If Al does what we expect it to do and queries the next vertices in the lower cube, it will find the sink v₆ in this cube after at least 1+5=6 steps. Now we tell Al that this is only the local sink. Since every edge between upper and lower bound reported so far is directed downwards, we can place every unique sink orientation in the upper cube we like. By choosing an orientation with the sink above v₆ we can flip the edge between the two sinks. Therefore, v₆ is only the local sink and Al has to query the vertex above v₆ (see figure 2). Again, Al needs at least 7 steps.

  

Figure 2: Al chooses an antipodal vertex

Basically we force the algorithm to perform a one-dimensional search to identify the two three-dimensional cubes, then a three-dimensional search on one of the small cubes and again a one-dimensional search at the end by flipping an edge between two local sinks.

For a general lower bound one could try to force the algorithm in a k dimensional search for getting an idea in which d-k-dimensional subcube the sink may be, a d-k dimensional search for finding the sink in this subcube and after he found the local sink there we force him to search on a traversal k-dimensional cube. For that take k different d-k-dimensional cubes with the only condition that in every cube the sink is at the same position. Glue them together in a product construction. Since all sinks of the small cubes are at the same position, the cube consisting of all these sinks can be chosen arbitrarily. (See figure 3.) The problem is now to adapt the proof for the 4-dimensional case to get

t(d)=t(d-k)+2t(k)

for k as large as possible.

  

Figure 3: How to get better lower bounds?

At the moment the best known lower bound is $t(d)\geq 2d-3$ due to Tibor Szabó.

In the proof for dimension four our first answer is the source. This seems reasonable in general, since if the first answer has i incoming edges we exclude 2ⁱ vertices from being the sink. Anyhow, it is not clear if one could achieve the same (or even better) bounds by not starting with the source.

Imprint Disclaimer Copyright