Max s, t-Flow Oracles and Negative Cycle Detection in Planar Digraphs

We study the maximum s, t-flow oracle problem on planar directed graphs where the goal is to design a data structure answering max s, t-flow value (or equivalently, min s, t-cut value) queries for arbitrary source-target pairs (s, t). For the case of polynomially bounded integer edge capacities, we describe an exact max s, t-flow oracle with truly subquadratic space and preprocessing, and sublinear query time. Moreover, if (1 -ϵ)-approximate answers are acceptable, we obtain a static oracle with near-linear preprocessing and O(n 3/4 ) query time and a dynamic oracle supporting edge capacity updates and queries in O(n 6/7 ) worst-case time.

To the best of our knowledge, for directed planar graphs, no (approximate) max s, t-flow oracles have been described even in the unweighted case, and only trivial tradeoffs involving either no preprocessing or precomputing all the n 2 possible answers have been known.

One key technical tool we develop on the way is a sublinear (in the number of edges) algorithm for finding a negative cycle in so-called dense distance graphs. By plugging it in earlier frameworks, we obtain improved bounds for other fundamental problems on planar digraphs. In particular, we show:

(1) a deterministic O(n log(nC)) time algorithm for negatively-weighted SSSP in planar digraphs with integer edge weights at least -C. This improves upon the previously known bounds in the important case of weights polynomial in n.

(2) an improved O(n log n) bound on finding a perfect matching in a bipartite planar graph.