Min st-cut oracle for planar graphs with near-linear preprocessing time

TY - JOUR

T1 - Min st-cut oracle for planar graphs with near-linear preprocessing time

AU - Borradaile, Glencora

AU - Sankowski, Piotr

AU - Wulff-Nilsen, Christian

PY - 2014/10/27

Y1 - 2014/10/27

N2 - For an undirected n-vertex planar graph G with nonnegative 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(n log4 n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since all-pairs min 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(n log4 n) time and O(n log n) space. Additionally, an explicit representation can be obtained in O(C) time and space where C is the size of the basis. These results require that shortest paths are unique. This can be guaranteed either by using randomization without overhead or deterministically with an additional log2 n factor in the preprocessing times.

AB - For an undirected n-vertex planar graph G with nonnegative 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(n log4 n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since all-pairs min 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(n log4 n) time and O(n log n) space. Additionally, an explicit representation can be obtained in O(C) time and space where C is the size of the basis. These results require that shortest paths are unique. This can be guaranteed either by using randomization without overhead or deterministically with an additional log2 n factor in the preprocessing times.

KW - Minimum cut, minimum cycle basis, planar graphs

U2 - 10.1145/2684068

DO - 10.1145/2684068

M3 - Journal article

SN - 1549-6325

VL - 11

SP - 16:1-16:29

JO - A C M Transactions on Algorithms

JF - A C M Transactions on Algorithms

IS - 3

M1 - 16

ER -