TY - GEN

T1 - On Fully Dynamic Graph Sparsifiers

AU - Abraham, Ittai

AU - Durfee, David

AU - Koutis, Ioannis

AU - Krinninger, Sebastian

AU - Peng, Richard

N1 - Publisher Copyright:
© 2016 IEEE.

PY - 2016/12/14

Y1 - 2016/12/14

N2 - We initiate the study of fast dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-spectral sparsifier with amortized update time poly(log n, ϵ-1). Second, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-cut sparsifier with worst-case update time poly(log n, ϵ-1). Both sparsifiers have size n · poly(log n, ϵ-1). Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a (1 - ϵ)-approximation to the value of the maximum flow in an unweighted, undirected, bipartite graph with amortized update time poly(log n, ϵ-1).

AB - We initiate the study of fast dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-spectral sparsifier with amortized update time poly(log n, ϵ-1). Second, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-cut sparsifier with worst-case update time poly(log n, ϵ-1). Both sparsifiers have size n · poly(log n, ϵ-1). Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a (1 - ϵ)-approximation to the value of the maximum flow in an unweighted, undirected, bipartite graph with amortized update time poly(log n, ϵ-1).

KW - Dynamic Graph Algorithms

KW - Sparsification

UR - http://www.scopus.com/inward/record.url?scp=85009380250&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85009380250&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2016.44

DO - 10.1109/FOCS.2016.44

M3 - Conference contribution

AN - SCOPUS:85009380250

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 335

EP - 344

BT - Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016

PB - IEEE Computer Society

T2 - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016

Y2 - 9 October 2016 through 11 October 2016

ER -