Max s , t -Flow Oracles and Negative Cycle Detection in Planar Digraphs
Adam Karczmarz · Society for Industrial and Applied Mathematics eBooks · 2024
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 Õ(n3/4) query time and a dynamic oracle supporting edge capacity updates and queries in Õ(n6/7) worst-case time.