PhD Seminar • Algorithms and Complexity • Shortest Beer Path Queries in Interval Graphs

Friday, December 2, 2022 2:00 pm - 3:00 pm EST (GMT -05:00)

Please note: This PhD seminar will take place in DC 1304 and online.

Kevin Wu, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Ian Munro

Our interest is in paths between pairs of vertices that go through at least one of a subset of the vertices known as beer vertices. Such a path is called a beer path, and the beer distance between two vertices is the length of the shortest beer path.

We show that we can represent unweighted interval graphs using 2n log O(nO(|B|log n) bits where |B| is the number of beer vertices. This data structure answers beer distance queries in O(logε n) time for any constant ε 0 and shortest beer path queries in O(logε n+d) time, where d is the beer distance between the two nodes. We also show that proper interval graphs may be represented using 3o(n) bits to support beer distance queries in O(f(nlog n) time for any f(n∈ ω(1) and shortest beer path queries in O(d) time. All of these results also have time-space trade-offs.

Lastly we show that the information theoretic lower bound for beer proper interval graphs is very close to the space of our structure, namely log(4+2√3)− o(n) (or about 2.9n) bits.

Paper link