Bottleneck Paths and Trees and Deterministic Graphical Games

EADS talk by Or Zamir, Dept. of Computer Science, Tel Aviv University


Gabow and Tarjan showed that the \emph{Bottleneck Path} (BP) problem, i.e., finding a path between a given source and a given target in a weighted directed graph whose largest edge weight is minimized, as well as the \emph{Bottleneck spanning tree} (BST) problem, i.e., finding a directed spanning tree rooted at a given vertex whose largest edge weight is minimized, can both be solved deterministically in $O(m\log^*n)$ time, where~$m$ is the number of edges and~$n$ is the number of vertices in the graph. We present a slightly improved randomized algorithm for these problems with an expected running time of $O(m\beta(m,n))$, where $\beta(m,n)=\log^*n - \log^*({m}/{n})$. This is the first improvement for these problems in over~25 years. In particular, if $m\ge n\log^{(k)}n$, for any constant~$k$, the expected running time of the new algorithm is $O(m)$. Our algorithm, as that of Gabow and Tarjan, work in the \emph{comparison model}. We also observe that in the word-RAM model, both problems can be solved deterministically in $O(m)$ time. Finally, we solve an open problem of Andersson et al., giving a deterministic $O(m)$-time comparison-based algorithm for solving deterministic 2-player turn-based zero-sum terminal payoff games, also known as \emph{Deterministic Graphical Games} (DGG).

Joint work with Shiri Chechik, Haim Kaplan, Mikkel Thorup and Uri Zwick.