Fast dynamic cuts, distances and effective resistances via vertex sparsifiers

Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. 2020. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. 61st Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 1135–1146.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Author
Chen, Li; Goranci, Gramoz; Henzinger, MonikaISTA ; Peng, Richard; Saranurak, Thatchaphol
Abstract
We present a general framework of designing efficient dynamic approximate algorithms for optimization problems on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1)A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in O~(n2/3) 11The O~(⋅) notation is used in this paper to hide poly-logarithmic factors. amortized time against an oblivious adversary, and O~(m3/4) time against an adaptive adversary. (2)An incremental data structure that maintains O(1) - approximate shortest path in no(1) time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in O~(n2/3+o(1)) amortized time per operation. (3)A fully-dynamic algorithm that approximates all-pair effective resistance up to an (1+ϵ) factor in O~(n2/3+o(1)ϵ−O(1)) amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as j-trees) and approximately captures the cut-flow and metric structure of the graph. The O(1)-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. See https://arxiv.org/pdf/2005.02368.pdf for the full version of this paper.
Publishing Year
Date Published
2020-11-01
Proceedings Title
61st Annual Symposium on Foundations of Computer Science
Publisher
Institute of Electrical and Electronics Engineers
Page
1135-1146
Conference
FOCS: Annual Symposium on Foundations of Computer Science
Conference Location
Durham, NC, United States
Conference Date
2020-11-16 – 2020-11-19
eISSN
IST-REx-ID

Cite this

Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In: 61st Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2020:1135-1146. doi:10.1109/focs46700.2020.00109
Chen, L., Goranci, G., Henzinger, M. H., Peng, R., & Saranurak, T. (2020). Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In 61st Annual Symposium on Foundations of Computer Science (pp. 1135–1146). Durham, NC, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/focs46700.2020.00109
Chen, Li, Gramoz Goranci, Monika H Henzinger, Richard Peng, and Thatchaphol Saranurak. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” In 61st Annual Symposium on Foundations of Computer Science, 1135–46. Institute of Electrical and Electronics Engineers, 2020. https://doi.org/10.1109/focs46700.2020.00109.
L. Chen, G. Goranci, M. H. Henzinger, R. Peng, and T. Saranurak, “Fast dynamic cuts, distances and effective resistances via vertex sparsifiers,” in 61st Annual Symposium on Foundations of Computer Science, Durham, NC, United States, 2020, pp. 1135–1146.
Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. 2020. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. 61st Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 1135–1146.
Chen, Li, et al. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” 61st Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2020, pp. 1135–46, doi:10.1109/focs46700.2020.00109.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2005.02368

Search this title in

Google Scholar
ISBN Search