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

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 n + O(n) + O(|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 3n + o(n) bits to support beer distance queries in O(f(n) log 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)n − o(n) (or about 2.9n) bits.

Paper link: https://arxiv.org/abs/2209.14401

To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/96257315410. You can also attend in person in DC 1304.