Single source - all sinks max flows in planar digraphs

TY - GEN

T1 - Single source - all sinks max flows in planar digraphs

AU - Lacki, Jakub

AU - Nussbaum, Yahav

AU - Sankowski, Piotr

AU - Wulff-Nilsen, Christian

N1 - Conference code: 53

PY - 2012

Y1 - 2012

N2 - Let G = (V, E) be a planar n-vertex digraph. Consider the problem of computing max st-flow values in G from a fixed source s to all sinks t ∈ V \ {s}. We show how to solve this problem in near-linear O(n log3 n) time. Previously, nothing better was known than running a single-source single-sink max flow algorithm n-1 times, giving a total time bound of O(n 2 log n) with the algorithm of Borradaile and Klein. An important implication is that all-pairs max st-flow values in G can be computed in near-quadratic time. This is close to optimal as the output size is Θ(n2). We give a quadratic lower bound on the number of distinct max flow values and an Ω(n3) lower bound for the total size of all min cut-sets. This distinguishes the problem from the undirected case where the number of distinct max flow values is O(n). Previous to our result, no algorithm which could solve the all-pairs max flow values problem faster than the time of Θ(n2) max-flow computations for every planar digraph was known. This result is accompanied with a data structure that reports min cut-sets. For fixed s and all t, after O(n1.5 log 2 n) preprocessing time, it can report the set of arcs C crossing a min st-cut in O(|C|) time.

AB - Let G = (V, E) be a planar n-vertex digraph. Consider the problem of computing max st-flow values in G from a fixed source s to all sinks t ∈ V \ {s}. We show how to solve this problem in near-linear O(n log3 n) time. Previously, nothing better was known than running a single-source single-sink max flow algorithm n-1 times, giving a total time bound of O(n 2 log n) with the algorithm of Borradaile and Klein. An important implication is that all-pairs max st-flow values in G can be computed in near-quadratic time. This is close to optimal as the output size is Θ(n2). We give a quadratic lower bound on the number of distinct max flow values and an Ω(n3) lower bound for the total size of all min cut-sets. This distinguishes the problem from the undirected case where the number of distinct max flow values is O(n). Previous to our result, no algorithm which could solve the all-pairs max flow values problem faster than the time of Θ(n2) max-flow computations for every planar digraph was known. This result is accompanied with a data structure that reports min cut-sets. For fixed s and all t, after O(n1.5 log 2 n) preprocessing time, it can report the set of arcs C crossing a min st-cut in O(|C|) time.

KW - computational complexity

KW - directed graphs

KW - Borradaile-Klein algorithm

KW - all-pairs max how values problem

KW - data structure

KW - max st-flow values

KW - min cut-sets

KW - near-linear time

KW - near-quadratic time

KW - planar n-vertex digraph

KW - single-source single sink max how algorithm

KW - Computer science

KW - Data structures

KW - Educational institutions

KW - Electronic mail

KW - Informatics

KW - Partitioning algorithms

KW - Standards

KW - all pairs

KW - maximum flow

KW - minimum cut

KW - planar graph

U2 - 10.1109/FOCS.2012.66

DO - 10.1109/FOCS.2012.66

M3 - Article in proceedings

SN - 978-0-7685-4874-6

SP - 599

EP - 608

BT - 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE

T2 - IEEE 53rd Annual Symposium on Foundations of Computer Science

Y2 - 20 October 2012 through 23 October 2012

ER -