Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

摘要

For an undirected $n$-vertex planar graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a min $st$-cut in $G$? We show how to answer such queries in constant time with $O(nlog^5n)$ preprocessing time and $O(nlog n)$ space. We use a Gomory-Hu tree to represent all the pair wise min $st$-cuts implicitly. Previously, no sub quadratic time algorithm was known for this problem. Our oracle can be extended to report the min $st$-cuts in time proportional to their size. Since all-pairs min $st$-cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in $O(nlog^5n)$ time and $O(nlog n)$ space and an explicit representation with additional $O(C)$ time and space where $C$ is the size of the basis. To obtain our results, we require that shortest paths be unique, this assumption can be removed deterministically with an additional $O(log^2 n)$ running-time factor.