Shortest Beer Path Queries in Outerplanar Graphs

Abstract

A \emph{beer graph} is an undirected graph $G$, in which each edge has a positive weight and some vertices have a beer store. A \emph{beer path} between two vertices $u$ and $v$ in $G$ is any path in $G$ between $u$ and $v$ that visits at least one beer store. We show that any outerplanar beer graph $G$ with $n$ vertices can be preprocessed in $O(n)$ time into a data structure of size $O(n)$, such that for any two query vertices $u$ and $v$, (i) the weight of the shortest beer path between $u$ and $v$ can be reported in $O(\alpha (n))$ time (where $\alpha (n)$ is the inverse Ackermann function), and (ii) the shortest beer path between $u$ and $v$ can be reported in $O(L)$ time, where $L$ is the number of vertices on this path. Both results are optimal, even when $G$ is a beer tree (i.e., a beer graph whose underlying graph is a tree).

ISAAC 2021