Finding all min st-cuts in planar graphs

Опубликовано 17 августа 2016, 21:56

In 1961, Gomory and Hu observed that the minimum st-cuts in an edge-weighted, undirected graph, for all pairs of vertices, can be represented compactly by a tree: the GH-tree. Not only that, they showed that one can find this tree with only n-1 minimum cut computations. Besides improvements to max flow/min cut algorithms, not much progress has been made on the all-pairs min-cut problem: Gusfield ('90) simplified Gomory and Hu's algorithm (without improvements the asymptotic running time) and Balghat et. al. ('07) showed how to find a GH-tree for unweighted graphs in time faster than required for n-1 min cut computations. Here we study the problem in planar graphs. Using the duality of cuts and cycles and small, balanced separators, we show how to find a GH-tree for weighted, undirected planar graphs in O(n polylog n) time. To appear in FOCS'10. Joint work with Piotr Sankowski and Christian Wulff-Nilsen