Tree Search With Predictions

Algorithms with predictions, or learning-augmented algorithms, has proved to be an extremely useful paradigm for combining machine learning with traditional algorithms. One of the textbook settings for this is searching a sorted array. Without a prediction classical binary search takes $O(\log n)$ queries, while with a prediction we can use "doubling binary search" to find the target key using $O(\log \eta)$ queries, where $\eta$ is the error of the prediction measured as the absolute value of the difference between the true location and the predicted location. Since an array is just a path graph, in this paper we ask whether similar bounds can be achieved for search on even slightly more general graphs: trees. We show first that the high-level answer is "no": there is no search algorithm that uses $O(\log \eta)$ queries, where now $\eta$ is the graph distance between the predicted location and the true location. However, as our main result, we show that such bounds can be achieved on trees which are "path-like" in that they have low pathwidth. In particular, we prove that there is a search algorithm which uses at most $O(k \log \eta)$ queries, where $k$ is the pathwidth of the tree. We also prove a lower bound showing that our algorithm has existentially optimal query complexity. Finally, we show experimentally, on real-life inputs, that our algorithm has query complexity which is notably better than the simple non-prediction based algorithm.