On Fully Dynamic Graph Sparsifiers

Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Scopus citations

Abstract

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).

Original languageEnglish (US)
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE Computer Society
Pages335-344
Number of pages10
ISBN (Electronic)9781509039333
DOIs
StatePublished - Dec 14 2016
Externally publishedYes
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: Oct 9 2016Oct 11 2016

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2016-December
ISSN (Print)0272-5428

Other

Other57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Country/TerritoryUnited States
CityNew Brunswick
Period10/9/1610/11/16

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Dynamic Graph Algorithms
  • Sparsification

Cite this