On Fully Dynamic Graph Sparsifiers

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

Authors

• Ittai Abraham
• David Durfee
• Ioannis Koutis
• Sebastian Forster
• Richard Peng

Keywords

• Heuristic algorithms
• Approximation algorithms
• Data structures
• Laplace equations
• Bipartite graph
• Clustering algorithms
• Algorithm design and analysis
• Dynamic Graph
• Undirected
• Algorithm For Problem
• Dynamic Algorithm
• Update Time
• Sparse Graph
• Worst-case Time
• Polylogarithmic
• Data Structure
• Running Time
• Edge Weights
• Linear Time
• Head And Tail
• Laplacian Matrix
• Graph Laplacian
• Indicator Vector
• Original Graph
• Spanning Tree
• Edge Connectivity
• Static Set
• Minimum Cut
• Peeling Off
• Single Update
• Vertex Cover
• Sparse Algorithm
• Dynamic Step
• Graph Algorithms
• Subset Of Edges
• Black Box
• Dynamic Graph Algorithms
• Sparsification