[{"conference":{"end_date":"2020-11-19","location":"Durham, NC, United States","start_date":"2020-11-16","name":"FOCS: Annual Symposium on Foundations of Computer Science"},"language":[{"iso":"eng"}],"oa_version":"Preprint","month":"11","publication":"61st Annual Symposium on Foundations of Computer Science","main_file_link":[{"url":"https://arxiv.org/abs/2005.02368","open_access":"1"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"eisbn":["978-1-7281-9621-3"],"eissn":["2575-8454"],"isbn":["978-1-7281-9622-0"]},"oa":1,"date_published":"2020-11-01T00:00:00Z","type":"conference","publisher":"Institute of Electrical and Electronics Engineers","page":"1135-1146","quality_controlled":"1","publication_status":"published","article_processing_charge":"No","date_created":"2022-08-16T07:33:12Z","title":"Fast dynamic cuts, distances and effective resistances via vertex sparsifiers","_id":"11852","scopus_import":"1","author":[{"first_name":"Li","last_name":"Chen","full_name":"Chen, Li"},{"first_name":"Gramoz","last_name":"Goranci","full_name":"Goranci, Gramoz"},{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Richard","last_name":"Peng","full_name":"Peng, Richard"},{"full_name":"Saranurak, Thatchaphol","last_name":"Saranurak","first_name":"Thatchaphol"}],"extern":"1","arxiv":1,"doi":"10.1109/focs46700.2020.00109","day":"01","abstract":[{"text":"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.","lang":"eng"}],"date_updated":"2023-02-17T09:47:36Z","citation":{"chicago":"Chen, Li, Gramoz Goranci, Monika H Henzinger, Richard Peng, and Thatchaphol Saranurak. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” In <i>61st Annual Symposium on Foundations of Computer Science</i>, 1135–46. Institute of Electrical and Electronics Engineers, 2020. <a href=\"https://doi.org/10.1109/focs46700.2020.00109\">https://doi.org/10.1109/focs46700.2020.00109</a>.","ieee":"L. Chen, G. Goranci, M. H. Henzinger, R. Peng, and T. Saranurak, “Fast dynamic cuts, distances and effective resistances via vertex sparsifiers,” in <i>61st Annual Symposium on Foundations of Computer Science</i>, Durham, NC, United States, 2020, pp. 1135–1146.","ama":"Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In: <i>61st Annual Symposium on Foundations of Computer Science</i>. Institute of Electrical and Electronics Engineers; 2020:1135-1146. doi:<a href=\"https://doi.org/10.1109/focs46700.2020.00109\">10.1109/focs46700.2020.00109</a>","apa":"Chen, L., Goranci, G., Henzinger, M. H., Peng, R., &#38; Saranurak, T. (2020). Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In <i>61st Annual Symposium on Foundations of Computer Science</i> (pp. 1135–1146). Durham, NC, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/focs46700.2020.00109\">https://doi.org/10.1109/focs46700.2020.00109</a>","ista":"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.","mla":"Chen, Li, et al. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” <i>61st Annual Symposium on Foundations of Computer Science</i>, Institute of Electrical and Electronics Engineers, 2020, pp. 1135–46, doi:<a href=\"https://doi.org/10.1109/focs46700.2020.00109\">10.1109/focs46700.2020.00109</a>.","short":"L. Chen, G. Goranci, M.H. Henzinger, R. Peng, T. Saranurak, in:, 61st Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2020, pp. 1135–1146."},"year":"2020","external_id":{"arxiv":["2005.02368"]}}]