Shortest Beer Path Queries in Interval Graphs

Abstract

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 }^{\epsilon }n)$ time for any constant $\epsilon >0$ and shortest beer path queries in $O({\log }^{\epsilon }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)\in \omega (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\sqrt{3})n-o(n)$ (or about $2.9n$) bits.

To appear in ISAAC 2022